找回密码
 欢迎注册
查看: 28703|回复: 6

[转载] 密码问题

[复制链接]
发表于 2018-6-2 08:01:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
某密码箱是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都能打开
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-11 09:21:57 | 显示全部楼层
对于某个三位数密钥我们可以把它看成三维坐标中一个数(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是否是最优解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-11 09:27:16 | 显示全部楼层
现在我们假设有一个最优密钥选择$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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-11 09:53:19 | 显示全部楼层
我们现在假设某个最优方案$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$了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-11 11:43:45 | 显示全部楼层
现在我们查看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个密码已经是最好的结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-6-12 08:44:27 | 显示全部楼层
有没有一种遗传算法,筛的方法,1000个数,擦除部分,然后就会出现需要保留的数字,再一次擦除部分,留下要保留的,继续这样操作,直到剩下的数字都不能擦除了,剩下的数字最少,就是优胜的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-6-12 10:05:47 | 显示全部楼层
倪举鹏 发表于 2018-6-12 08:44
有没有一种遗传算法,筛的方法,1000个数,擦除部分,然后就会出现需要保留的数字,再一次擦除部分,留下要 ...

这个题目应该可以通过数学方法直接找出最优解为50个密钥,而不需要用计算机寻找
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-11 03:47 , Processed in 0.023721 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表