作业帮 > 数学 > 作业

一个保险箱有三位密码,每位有1-8八个数字.只要有两位密码正确就可以开锁,问至少要尝试多少次(一次同时输入三位密码)才能

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/11/05 23:39:38
一个保险箱有三位密码,每位有1-8八个数字.只要有两位密码正确就可以开锁,问至少要尝试多少次(一次同时输入三位密码)才能保证一定开锁?
答案是32,求证明
这个问题要分两步,一是证明32可行,二是证明31不可行.
第一步直接验证下面的策略一定可行
111,212,313,414
122,223,324,421
133,234,331,432
144,241,342,443
555,656,757,858
566,667,768,865
577,678,775,876
588,685,786,887
第二步用几何模型来叙述可以简洁一点,考察R^3中的格点{1,2,3,4,5,6,7,8}^3,每尝试一个点相当于验证了过该点且与坐标轴平行的三条直线上的点(22个).
如果只取了31个检验点,考察垂直于z轴的8个平面,不妨设z=1上检验点最少.
若z=1上只有不超过2个检验点,那么该平面上至少有64个点要由上面7层的点来覆盖,矛盾.所以该平面上有3个检验点.
z=1上至少还有25个点不在由这3个点(记为A类点)生成的直线上,需要由上面7层平面中的点来覆盖(取出满足条件的25个记为B类点),还余下3个自由的点记为C类点.
A类点生成的直线最多覆盖64-25+3*7=60个点;
B类点生成的直线最多覆盖25*(8+6)=350个点;
C类点生成的直线最多覆盖3*21=63个z=0平面以外的点(z=0上的点已经全部被统计过).
这些点加起来不足以覆盖所有的512个点.