- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 40131
- 在线时间
- 小时
|
发表于 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个密码已经是最好的结果 |
|