2008 (4)
有12个外表一模一样的球，其中有一个坏球重量不同于其他11个。只允许使用三次天平，如何找出坏球并弄清是轻是重？
这是一个广为人知的问题，网上应有不少答案。现在要介绍的，是利用信息论里的熵来帮忙找出坏球。
信息论里最重要的概念就是熵。如果一个概率分布为 (P)=(p_1,p_2,...,p_n),则其熵为H(P)=-(p_1log(p_1)+p_2log(p_2)+...+p_nlog(p_n))。它是一个非负值，可用来度量一个概率分布的不确定性，也就是信息量。这句话可以这么理解：当一个随机事件的结果未知以前，它具有不确定性，但当结果已知以后，不确定性便转化为信息量了。
信息论里一个重要的结论是，一个概率分布如有n个可能的结果，则当n个结果概率等可能时，信息量最大。比方说，下面两个分布： (1/3,1/3,1/3)和(3/8,3/8,2/8)，前者的信息量更大。
我们用天平称球的过程，就是获取信息的过程，所以要尽可能获得大的信息量，而这又依赖于我们如何使用天平。一次使用天平的结果，有三种可能，就是左轻右重，左右相等和左重右轻。如果能够合理使用，使三种结果的概率尽可能相等，所获的信息量就尽可能大了。
如果三个球中只有一个坏球且知其轻重，称一次就可轻易找到坏球；而如果九个球中只有一个坏球且知其轻重，则称二次也可轻易找到坏球。类似的，如果二十七个球中只有一个坏球且知其轻重，则称三次也可轻易找到坏球。
我们的问题难在不知坏球是轻还是重，否则就轻而易举了。解法如下：
先用从1到12给球标上号并将它们分为三组：{1,2,3,4},{5,6,7,8}和{9,10,11,12}。坏球在三组中的概率是一样的，都是1/3。取出两组分别放在天平的两端，比如{1,2,3,4}放左端，{5,6,7,8}放右端。这样获得的信息量最大，因为左右相等，左轻右重和左重右轻的概率均是1/3。
如果左右相等，坏球就在第三组中。将{1,2,3}放在左边，{10,11,12}放在右边称第二次。如两边相等，9号就是坏球，再称一次就能确定轻重，否则，坏球必在{10,11,12}中且轻重已知，再称一次也可找到答案。
如左轻右重，这时坏球要么在{1,2,3,4}中且为轻, 要么在{5,6,7,8}中且为重。然后考虑下面的分组：{1,2,9},{5,6,7}和{3,4,8}，并将{1,2,9}和{3,4,8}分别放在天平的左右两端称第二次。这样做是因为坏球在三组中的概率最为接近，分别是2/8，3/8和3/8，而且称球后三种结果的概率也尽可能相等。如两边相等，则坏球必在{5,6,7}中且为重，再称一次就可找到答案了。现假设两边不等。如左轻则坏球必在{1,2}和8中，1和2再称一次便可得答案。如左重则坏球在3和4号球中，再称一次也可知结果。
（还有其它不同称法，比如：如左轻右重，这时坏球要么在{1，2，3，4}中且为轻, 要么在{5，6，7，8}中且为重。接下来如何使用天平呢？我们考虑下面的称法：{1，2，5}放左边，{3，4，6}放右边。如两边平衡，坏球就在7号或8号球中且为重，再称一次就知答案了。如左轻右重，则表示坏球在1，2，6中；如左重右轻，则坏球必在3，4，5中。不管哪种情形，再称一次都可找到答案。）
左重右轻的情形可同法处理，就不赘述了。
大家不妨试试看。祝你成功！
