魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: hw294

开锁问题 --- 魔方最少覆盖问题 [复制链接]

Rank: 10Rank: 10Rank: 10

积分
19773
帖子
4673
精华
33
UID
3
性别
兴趣爱好
结构
发表于 2005-4-27 21:46:20 |显示全部楼层
以下是引用hw294在2005-4-27 18:04:06的发言:

另外,答案没那么多的,假如固定只试前两个,则需要10*10=100次就够了,而这还未考虑后一位的情况,所以说,只能比100少,不会比100多。[em12]

假定只有两个转盘,也要试10*10=100次,但现在有三个转盘,怎么还会少于100

-,'''╭⌒╮⌒╮.',''',,',.'',,','',.,,'
.╱◥██◣''o┈ 魔方吧 ┄o.'',,',.
︱田︱田田︱ '',,',.o┈ 欢迎您光临 ┄o
╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬

使用道具 举报

Rank: 8Rank: 8

积分
17508
帖子
16321
精华
9
UID
449
性别

魔方理论探索者 论坛建设奖 爱心大使 十年元老

发表于 2005-4-27 22:20:11 |显示全部楼层
题目条件说只要(任意某)2位数字对,就能打开。故另一位是形同虚设呀!

使用道具 举报

Rank: 10Rank: 10Rank: 10

积分
19773
帖子
4673
精华
33
UID
3
性别
兴趣爱好
结构
发表于 2005-4-28 13:08:20 |显示全部楼层

假设你已经知道那个转盘已经不起作用,只用试其余两个数字,那么肯定能打开的最少试开数也是102,怎么会比100少呢?

-,'''╭⌒╮⌒╮.',''',,',.'',,','',.,,'
.╱◥██◣''o┈ 魔方吧 ┄o.'',,',.
︱田︱田田︱ '',,',.o┈ 欢迎您光临 ┄o
╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬

使用道具 举报

Rank: 4

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2005-4-28 13:56:04 |显示全部楼层

先从最简单的考虑,比如说每个转盘只有0和1两个数字,那么密码共有以下8种可能:000,001,010,011,100,101,110,111。而只用001和110,只试两次就可打开,因为001管000,001,011,101这4种可能,而110管010,100,110,111剩下的这4种可能,所以只试两次就已打开锁了,而并非2*2=4次。[em05][em05]

使用道具 举报

Rank: 10Rank: 10Rank: 10

积分
19773
帖子
4673
精华
33
UID
3
性别
兴趣爱好
结构
发表于 2005-4-28 15:46:43 |显示全部楼层

哈哈,再细看你的题目“一把密码锁,有3位数字,现已损坏,只要2位数字对,就能打开。如密码为123,只要12*、1*3、*23,就能打开锁。现在,密码忘记了,问:最少试多少次,就肯定能打开锁?”原来你的题目是只要求任意“两位数字对”就可以开锁。

-,'''╭⌒╮⌒╮.',''',,',.'',,','',.,,'
.╱◥██◣''o┈ 魔方吧 ┄o.'',,',.
︱田︱田田︱ '',,',.o┈ 欢迎您光临 ┄o
╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2005-4-29 12:08:42 |显示全部楼层
看样子是不太容易呀! 初步结论:最小值下界大于 N*N/3 。 我暂时找到最小值为 N*N-N 的方案!
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 4

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2005-5-7 11:54:47 |显示全部楼层

能否先说说N*N-N的方案呢?另外5搂的10^10-3*10-1不知怎么做的,是否是10*10-3*10-1呢?这样的话少一些。我想N=2时为2,是否都能找到N*N/2的答案呢?这样,转盘为10个数,即N=10时答案就是50了。

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2005-5-7 12:08:25 |显示全部楼层

比如:

001 110 002 220 ... ... 00N NN0

112 221 113 331 ... ... 11N NN1

... ... ... ...

(N-1)(N-1)N NN(N-1)

不知你现在能给出最优解吗?具体到某一个 N ,应该可以找出更优的解吧!

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 4

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2005-5-13 13:44:25 |显示全部楼层

只试下面的50次,就一定打开锁了。做小偷也要想着办法省力点嘛![em07]

(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1) (1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2) (2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3) (3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4) (4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)

(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6) (6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7) (7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8) (8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9) (9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)

使用道具 举报

Rank: 4

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2005-5-13 13:58:10 |显示全部楼层

上面的我是看了答案,答案的思路和我们不大一样,确实比较奇特。其中牵涉到魔方,建议魔友都看一下。到这儿,我也卖个关子:


以下内容只有回复后才可以浏览
将组合(a,b,c)看成空间中的一个整点,则开锁的问题,便成了
整点之间的覆盖问题--如果一个整点的坐标至少有两位和(a,b,c)相同,
则称被(a,b,c)覆盖。
显然,所有组合构成了10*10*10的一个立方体,也可看做10*10*10的魔方,我们的问题,就是从中选出最少个数的整点(可看做魔块)集合,使其能够覆盖整个立方体(魔方)。
下面这个50个整点的集合,易证可以覆盖整个立方体:
(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)
(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)
(2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3)
(3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4)
(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)
(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)
(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)
(7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8)
(8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9)
(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)
接下来,我们用反证法证明50次是最少次数,否则
假设存在49个整点的覆盖集合F,由于立方体共有10层,因此至少有一层
当中包含的F中的点少于5个。不妨设这一层是最下层z=0.
若z=0中含有的个数<4个,那么这一层至少还有7*7=49个格点不能被这一层
F中的整点覆盖,而这至少49个格点只能被来自它们上方的不同的格点覆盖
也就是F当中至少还有49个格点,矛盾。因此z=0中应该恰含有F中的4个格点。
那么z=0中至少还有6*6=36个格点不能被这一层F中的整点覆盖,它们只能
被来自它们上方的不同的格点覆盖,也就是说在这36个格点的上方,至少还
有36个F中的格点,现在至多有49-4-36=9个F中的格点还没涉及到,我们计
算一下至少还有多少个格点还没有被覆盖:
z=0中的4个格点至多覆盖4*28-C(4,2)*2=100个格点;
上面所说的36个格点至多覆盖36*10+36*4*2=648个格点;
至少还有1000-100-648=252个格点还没有被覆盖。
剩下的至多9个F中的格点,至多能覆盖9*27=243个(不包含z=0)格点,
因此至少还有252-243=9个格点没有被覆盖,矛盾。
这说明,不存在49个格点的覆盖集合。

进一步,我们可以考虑本问题的更一般的推广形式:
一把密码锁,有n位数字,现已损坏,只要k位数字对,就能打开。现在,
密码忘记了,问:最少试多少次,就肯定能打开锁?[em06]

将回复可见去掉,以便让没空回复的朋友看到

[此贴子已经被作者于2005-5-23 18:50:44编辑过]

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2019-1-19 04:55

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部