密码问题

倪举鹏

某密码箱是000-999的三位数，现在只需要密码对两个数字就可以打开。问至少尝试几个数就一定能够打开，列出是哪几个数。
比如尝试000，如果密码是000  001  002  003  004  005  006  007  008  009  010  020   030  040  050  060  070  080  090  100  200  300  400  500  600 700  800  900都能打开

mathe

对于某个三位数密钥我们可以把它看成三维坐标中一个数(i,j,k)，其中$0<=i,j,k<=9$,我们把集合$F_{k_0}={(i,j,k)| k=k_0, 0<=i,j<=9}$称为密码空间中$k=k_0$的一个k-面
也就是这个密码空间中总共有10个k-面$F_0,F_1,...,F_9$，分别对应$k=0,k=1,...,k=9$。
而对于每个给定的k-面$F_{k_0}$，其子集$C_{k_0,j_0}={(i,j,k)| k=k_0,j=j_0, 0<=i<=9}$称为k-面$F_{k_0}$的一个j-列。
于是每个k-面$F_{k_0}$有10个j-列$C_{k_0,0},C_{k_0,1},...,C_{k_0,9}$
同样对于每个给定的k-面$F_{k_0}$，其子集$R_{k_0,i_0}={(i,j,k)| k=k_0,i=i_0, 0<=j<=9}$称为k-面$F_{k_0}$的一个i-行。
于是每个k-面$F_{k_0}$有10个i-列$R_{k_0,0},R_{k_0,1},...,R_{k_0,9}$

我们首先选择集合
$A={(i,j,k)| 5|i+j+k, 0<=i,j,k<=4}$
$B={(i,j,k)| 5|i+j+k, 5<=i,j,k<=9}$
于是$A \cup B$共包含50组密码。
那么对于任意一个三位密码，必然有两个数不超过4或两个数不小于5,于是总是可以在$A \cup B$中挑选出一个和它至少两位相同。
所以我们知道对于这种方案试50次足够了，现在唯一的问题就是50是否是最优解。

mathe

现在我们假设有一个最优密钥选择$X$包含不超过49个密码，如果在这种选择方案中，有一个k-面最多选择了三个密码，不妨设$|X \cap F_0|<=3$
那么在k-面$F_0$中，除去这不超过三个密钥所在的i-行和j-列，至少还有7*7=49个密码和这不超过三个密码至少两位不同，于是这不少于49个密码都只能通过$X - F_0$上的密码来覆盖。
而每个$X- F_0$中密码最多只能覆盖$F_0$中一个密码（因为k坐标不同，i,j坐标都必须相同），所以X中必须包含不在$F_0$中至少49个密码，得出$|X|>=49+3=52$，必然不是最好的选择（我们已经有只需要选50个密码的选择）。
也就是得出最好的选择每个k-面都至少选择了四个密码，由此我们可以先给出一个最好方案的密码数目下界4*10=40

mathe

我们现在假设某个最优方案$X$中正好有h个k-面里选择了4个密钥(于是有10-h个k-面都选择了不小于5个密钥）
于是对于这h个k-面中每个$F_{k_0}$, $|F_{k_0} \cap X|=4$， 那么$F_{k_0} \cap X$最多可以覆盖$F_{k_0}$的4个j-列，所有至少6个j-列没有被$F_{k_0} \cap X$覆盖。同样由于最多4个i-行被覆盖，所以其中任意一个没有被覆盖的j-列中，至少有6个密钥没有被$F_{k_0} \cap X$覆盖，所以需要$X-F_{k_0}$中至少6个元素覆盖这个j-列余下的密钥。
我们假设有s个j值$j_0$，存在一个k-面$F_{k_0}$使得$|F_{k_0} \cap X|=4$使得k-面$F_{k_0}$的j-列$C_{k_0,j_0}$不被$F_{k_0} \cap X$覆盖，于是$6<=s<=10$。我们已经知道其中每个这样的j-列需要至少$X$中6个j坐标等于$j_0$的元素覆盖，也就是$X$中至少包含6个$j=j_0$的点。
而余下的10-s个j值由于对于每个正好包含X中4个密钥的k-面$F_{k_0}$, $F_{k_0} \cap X$都有一个坐标为$j_0$的密码，所以$X$中至少有$h$个j坐标为$j_0$的密码，所以$X$总共至少包含$h xx (10-s)+6s=10h+(6-h)s$个不同的密钥
在$h<=6$时，$|X|>=10h+(6-h)*6=36+4h$个密钥,所以在$4<=h<=6$时$|X|>=52$，必然不是最优秀的方案。
而在$h>=7$时，$|X|>=10h+(6-h)s>=10h+10(6-h)=60$个不同的密钥，也必然不是最优的选择。
所以最优方案中$h<=3$,而这时我们知道最优解的下界已经是$7*5+3*4=47$了

mathe

现在我们查看h=3的情况，对应$|X|>=3*(10-s)+6s=30+3s$,于是对于$s>=7$都有$|X|>=51$不是最优结果，所以我们只需要再查看$s=6$的情况.
也就是这3个只有4个密钥的k-面所覆盖的4个j-列的j值都是相同的，不妨设为j=0,1,2,3这4列。
如果这种方案有优于50的方案，除掉这3个4个密码的k-面中的12个密钥以外，余下7个k面包含最多49-12=37个密钥，其中至少36个密钥的所有j值都不小于4（因为覆盖其余6个j-列至少需要36个密钥）,也就是最多还有一个密钥的j值可以是0,1,2,3中的一个.
同样对于i坐标应该也有类似的结果，我们同样不妨设i=0,1,2,3这4行被包含4个密钥的k-面覆盖了，那么余下37个密钥至少36个密钥的所有i值也都不小于4.
现在我们看不在3个只有4密钥的k-面上的37个密钥被余下7个k-面使用情况，其中必然有一个k面使用了不超过5个密钥（于是只能正好5个密钥），于是4,5,6,7,8,9这6个i值和j值中都必然有一个没被这个k-面使用，不妨设i=4和j=4都没有被这个k-面使用。于是在这个k面上，坐标点$(i \in {0,1,2,3}, j=4)$和$(i=4,j \in {0,1,2,3,4})$都只能被其它k面上的$X$中密码所覆盖，由于它们k值不同，要求i和j都相等。于是这些被选中的点都要求i,j坐标中一个小于4，一个等于4，但是前面分析中这样的密码$X$中最多1个，不可能将它们全部覆盖，所以h=3情况没有优于50的解

h=2和h=1的情况也可以类似分析，它们只能对应$6<=s<=7$,而且分别会有很多个使用5个密钥的k-面，只是分析过程会很麻烦，不知道是否可以有更简洁的能够证明50是最优解的方法
比如$h=2$时对于j-列可以$s=6$或$s=7$,但是相应的对应i-行也可以有对应的$s'=6$或$s'=7$,总共会构成4种不同的情况，但是每种情况都可以用和上面类似方法分析
在$s=7$或$s'=7$的情况下，两个特殊k-面使用了6个i,j坐标都在一个$3 xx 3$或$3 xx 4$矩形内部的点，另外至少有42个点在互补的$7 xx 7$或$7 xx 6$的矩形内部，于是余下最多一个点不在这两个矩形区域内部。而最多43个点8个余下k-面分配至少有某个面不超过5个点，类似前面可以得出矛盾。
而在$s=6,s'=6$的情况，两个特殊k-面使用了8个i,j坐标都在$4 xx 4$矩形内部的点（假设$0<=i,j<=3$），余下最多41个点中至少36个点在互补的$6 xx 6$的矩形内部(假设$4<=i,j<=9$)。所以最多5个点在两个矩形外部。
同样类似前面我们可以找到一个使用了5个密钥的k-面，假设其中$i=4$这一行和$j=4$这一列没有被使用，那么$(i \in {0,1,2,3}, j=4)$和$(i=4,j \in {0,1,2,3,4})$这8个点要被5个不在两矩形内部的点覆盖，不可能也淘汰。
最后还有$h=1$的情况，那么也有$s=6$。由于只要一个k-面使用了4个密码，余下的k-面都至少使用5个密码。如果要求总密码数不超过49，那么余下的9个k-面只能正好每个都5个密码。其中4个在一个k-面，3
同样假设那个4个密码的k-面是$F_0$,其中$i=0,1,2,3$行,$j=0,1,2,3$列被这4个密码覆盖。而余下不超过45个密码中，至少有36个i,j坐标都不小于4，所以最多9个密码的i,j坐标一个小于4，另外一个不小于4.
现在查看k-面$F_1$，它上面5个密钥，那么$i>=4,j>=4$的各行各列中至少一行一列没有被这5个密码覆盖，不妨设$i=4$和$j=4$对应的行列没有被覆盖。于是$F_1$中8个点$(i \in {0,1,2,3}, j=4)$和$(i=4,j \in {0,1,2,3,4})$都只能被那不超过9个的i,j坐标一个小于4，另外一个不小于4的点覆盖。也就是这不超过9个点中至少有8个i坐标或j坐标等于4，其中4个i坐标等于4，j坐标小于4，另外4个j坐标等于4，i坐标小于4。
同样现在查看k-面$F_2$,那么会有和$F_1$类似的结果，也就是它没有被其上面5个密码覆盖的那$i>=4,j>=4$的行列必须也是第4行和第4列，不然那9个点就不够用了。
最后我们可以得出所有9个k-面都没有密码覆盖第4行和第4列，于是$F_0$的第4行和第4列就没有密码能够完全覆盖了。
所以我们最终可以得出50个密码已经是最好的结果

倪举鹏

有没有一种遗传算法，筛的方法，1000个数，擦除部分，然后就会出现需要保留的数字，再一次擦除部分，留下要保留的，继续这样操作，直到剩下的数字都不能擦除了，剩下的数字最少，就是优胜的

mathe

倪举鹏 发表于 2018-6-12 08:44
有没有一种遗传算法，筛的方法，1000个数，擦除部分，然后就会出现需要保留的数字，再一次擦除部分，留下要 ...

这个题目应该可以通过数学方法直接找出最优解为50个密钥，而不需要用计算机寻找