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

金眼睛

<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 编辑 ]