39个硬币问题解答.doc

问题：怎么用一架天平称出13个硬币中唯一的然而未知轻重的假币（已知有标准的硬币）？解答：只用天平称3次便能够找到假币，具体的方法如下：（1） 对问题的描述每枚硬币可能为轻或者重，用q标记轻，用z标记重，（qz表示硬币可能轻或重）用t表示真币，13枚硬币的可能性空间为132=26，天平每次称时，左边和右边放相同数量的硬币，其余的硬币作为剩余的。因此能够用4元组来描述称的过程，（L，R，S，n），其中L表示天平左边放的硬币数量以及状态，R表示天平右边放的硬币数量以及状态，S表示剩余的硬币数量和状态，n表示天平称的次数。（2） 制定规则问题的关键是找出假币，由（1）中对问题的描述，可以通过硬币的轻重来确定假币，即如果能够知道所有硬币的轻重的状态便能够很容易的知道假币；也可以通过假币只有一枚，如果能够确定13枚硬币中的12枚硬币的重量是相等的，那么一定能够确定第13枚硬币时假币来解决问题，此时会不知道假币轻还是重了。天平没称一次有三种情况，左边重lz，右边重rz，水平sp，如果天平水平，那么可以得到放在左边和右边的硬币都是真币；如果天平不平衡，那么剩余部分硬币时真币。（3） 问题求解 -平衡时的解法 图（1）说明：椭圆中表示的是现在的状态，真币的数量没有给出，矩形中给出天平每次称的具体放法，向左下的箭头表示天平左边重，向下的箭头表示天平水平，向右下的箭头表示天平右边重，最后用不同颜色标记的是最后能确定的假币，红色表示的是能够确定轻重的，蓝色表示的不能确定轻重，但是能够确定该硬币时假的。（4） 问题求解 -左或右倾斜时的解法 图（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枚硬币是假币。并且从问题的求解过程可以看出，问题的关键是在有2枚不知轻重的硬币时，此时如果有一枚真币这个信息，从轻重分的状态空间考虑，此时的可能性状态空间大小为4，需要用天平两次才能确定没枚硬币的轻重，但是从找出假币的角度，如果此时2枚硬币中有一枚假币，那么使用天平一次便能够得知哪一枚是假币。下面给出基于控制论的求解大致思想设天平的左边和右边放置的硬币的数量都为x，剩余的硬币数量为y，硬币的状态有q，z，qz，开始硬币的状态都为qz，以13枚硬币为例，要使得接下来能够完成必须满足的关系为 式（7）求解得到此时有唯一解 。当硬币的状态不全是qz时，需要分别设出每个状态的硬币的数量，并设出天平左边，右边和剩余的状态，便能够用不等式组求解出不同的放置方案。验证当n 的取值为，此时用天平4次能够确定所有硬币的轻重，并找到假币；当n 的取值为，此时用天平4次能够找到假币，但在某些情况下不能确定每枚