开锁问题 --- 魔方最少覆盖问题

robbit521

<P>密码是1-9的话。太简单了9个里任取2个：9×8/2×1=36</P>
<P>密码是0-9的话。太简单了10个里任取2个：10×9/2×1=45</P>

ososo

最少试一次,恰好蒙对了，楼主说呢?

qiny1984

从000-099总共100次

xiaoye

假如密码锁有N个元素的话，那么不失一般性，题目要求的密码应该是在00——NN之间的一位，即我们如果放弃第三位的话，至少要试（N+1）×（N+1）次，不过由于还有一位，则我们可以这样设置：00N,01(N-1),02(N-2).......此时若N为奇数时，以9为例，要10×10%2=50,N为偶数时，以8为例，8×8%2+9=41～

咖啡味的茶

题目的问题是，至少多少步能保证开锁。这么考虑，题目也就是把不能开锁的所有都算出来，然后再试一次就可以了。所以应该是1.只对一个密码：3*9*9；2.一个都不对：9*9*9；一共是9*9*9+9*9*3+1=973次

咖啡味的茶

cube-master考虑错了啊，在试的过程是没有得考虑的，所以你不能说第三个键盘不转的，一定要考虑所有打不开的情况。

金眼睛

<P>答案已经有了，如下：</P>
<P>(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)</P>
<P>(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)</P>
<P>(2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3)<BR>(3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4)</P>
<P>(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)<BR>(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)</P>
<P>(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)</P>
<P>(7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8)<BR>(8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9)</P>
<P>(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)<BR>但答案不是唯一的，给出得到答案的一个思路吧，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> </P>
<P>&nbsp;</P>
<P>采用的数学原理是抽屉原理，因为密码有三位，所以要设置两个抽屉，也就是随机把0~9的数字分为两组，例如：0~5和6~9两组，则密码中的三位数字一定有两位落在同一个组内，我们就利用这两个同组数字来开锁。这两个数字的变化情况为5*5=25种，位置变化为ab*，a*b，*ab三种，共25*3=75种，如果加入第三位每一种可以代替三种，所以可以构造75/3=25种来代替全部变化。同理如果落入第二个抽屉，还需要25种情况，所以一共需要25*2=50种情况。</P>
<P>&nbsp;</P>
<P>看看上面的答案，可以发现就是两个抽屉的各25种情况。在每一种情况当中，先固定一位(上面的答案固定的是第二位)，然后让另一位在固定位的基础上轮换(即第一位在第二位基础上轮换)，最后一位在前两位的基础上进行轮换(即第三位在第一、二位的基础上轮换)。</P>
<P>&nbsp;</P>
<P>如果有人对此问题的数值解法感兴趣，可以参考<A href="http://lab.ntsec.gov.tw/activity/race-2/International2004/pdf/0104.pdf"><FONT color=blue>http://lab.ntsec.gov.tw/activity/race-2/International2004/pdf/0104.pdf</FONT></A></P>
<P>关于此问题，其中有详细的结论。<FONT color=red>N为偶数时，F(N)=(N/2)^2+(N/2)^2=N^2/2；N为奇数时，F(N)=(N^2+1)/2</FONT>。</P>
<P>&nbsp;</P>
<P>PS：55#的构造能不能多写点，看不出构造的规律。如果后面只是改变第一个数，第二个数总是小于第三个数且不变(如果不小于就100种了)，那么类似054这种组合怎么能试出来呢？也许是我理解得不对，o(∩_∩)o...</P>

[ 本帖最后由 金眼睛 于 2008-8-25 10:57 编辑 ]

psuynjw

123的锁,12*,13*,*23.首先要知道是哪个位置错了吧.个人觉得这和锁没坏一个样.
所以个人认为答案是10*10*10=1000.
前提,开锁数字是0-9这十个数

yushaolun2002

覆盖的问题没有介绍清楚，大家也都没有理解好！不是吗？你自己也搞清楚了吗？