39个硬币问题解答.doc

解答:只用天平称3次便能够找到***,具体的方法如下:
对问题的描述
每枚硬币可能为轻或者重,用q标记轻,用z标记重,(qz表示硬币可能轻或重)用t表示真币,13枚硬币的可能性空间为13×2=26,天平每次称时,左边和右边放相同数量的硬币,其余的硬币作为剩余的。因此能够用4元组来描述称的过程,(L,R,S,n),其中L表示天平左边放的硬币数量以及状态,R表示天平右边放的硬币数量以及状态,S表示剩余的硬币数量和状态,n表示天平称的次数。
制定规则
问题的关键是找出***,由(1)中对问题的描述,可以通过硬币的轻重来确定***,即如果能够知道所有硬币的轻重的状态便能够很容易的知道***;也可以通过***只有一枚,如果能够确定13枚硬币中的12枚硬币的重量是相等的,那么一定能够确定第13枚硬币时***来解决问题,此时会不知道***轻还是重了。天平没称一次有三种情况,左边重——lz,右边重——rz,水平——sp,如果天平水平,那么可以得到放在左边和右边的硬币都是真币;如果天平不平衡,那么剩余部分硬币时真币。
问题求解---平衡时的解法
图(1)
说明:椭圆中表示的是现在的状态,真币的数量没有给出,矩形中给出天平每次称的具体放法,向左下的箭头表示天平左边重,向下的箭头表示天平水平,向右下的箭头表示天平右边重,最后用不同颜色标记的是最后能确定的***,红色表示的是能够确定轻重的,蓝色表示的不能确定轻重,但是能够确定该硬币时假的。
问题求解---左或右倾斜时的解法
图(1)
5q4z的具体称法如下:
图(2)
下面给出从控制论角度的分析
可能性空间:
事物发展变化中面临的各种可能性集合。
控制能力:
实行控制前后的可能性空间之比。
结论:使用天平k次可以从n个硬币中找出唯一的未知轻重的***需要满足条件
式(1)
硬币可能性空间:
设每枚硬币的可能有两种:轻或重,因此n枚硬币的可能性空间为2n。
天平的控制能力:
当硬币状态都是轻或重时,如果天平的左边,天平的右边和剩余的硬币的数量相等,可以很容易证明,每称一次硬币的可能性空间变成原来的1/3,即天平的控制能力达到3。即当不知道天平结果如何时,我们使用天平能够达到的最大控制能力为3。
根据控制论的理论知识,能够得到使用天平次数k和硬币数量n之间的满足如下关系时, 式(2)
能够得到每枚硬币的轻重状态。
由此公式能够计算使用天平k次能够确定轻重的硬币数量最大n值为
式(3)
很容易证明max(n)不能够被3整除,因此不能被正好分成3份,因此在具体的称的时候不能使得在所有的情况下,天平的控制能力达到3,例如对于13枚硬币,满足
式(4)
在具体的实施时存在不能够确定硬币的轻重。需要将上面的公式改一下,使用天平k次能够确定轻重的硬币数量的最大值为
式(5)
但在问题的求解中,可以得出此时在某些情况下不能确定所有硬币的轻重,但是能够找到***,因此有上面的结论,即使用天平k次能够从n枚硬币中找出唯一的不知轻重的***的n的最大值为
式(6)
分析不同得到
找出n枚硬币中唯一不知道轻重的***与通过确定n枚硬币的轻重状态来确定那枚假硬币是不等价的。对于13枚硬币,如果知道其中12枚硬币的重量相等,就可以得到第13枚硬币是***。并且从问题的求解过程可以看出,问题的