Question

高中数学竞赛组合题

一个保险箱有三位密码，每位有1-8八个数字.只要有两位密码正确就可以开锁，问至少要尝试多少次（一次同时输入三位密码）才能保证一定开锁？
答案是32,求证明

Answer 1

这个问题要分两步，一是证明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个点。

Answer 2

我算出来的概率是22/512，也就是说，保证一定要开锁就是要占这512次当中的22次

Answer 3

相当于两位密码那就是8*8=64种但还有一位密码，就可以减少一位密码的一半尝试，所以除以2，为32