有趣的找怪球问题 (1)

1. 12球问题

一般的 $n$ 球问题是指下面的问题：有 $n$个外表一模一样的球，其中有一个球是怪球，它和其它的正常球重量不同。现在只有一个天平可用，请问至少要用多少次天平才可把怪球找出来，并告知它比正常球是轻还是重？当 $n=12$ 时，就是著名的12球问题，它的表述如下：有12个外表一模一样的球，其中有一个怪球重量不同于其他11个正常球。只允许使用三次天平，如何找出怪球并弄清它比正常球是轻还是重？

据说12球问题最早出现在“Grossman, Howward(1945). Scripta Mathematica XL” 一文中，真的是历史悠久了。在给出12球问题解答之前，我们先定义带信息的球。我们的球有灰白黑绿四种颜色，它们的具体含义是：绿色代表正常球，白色球表示它可能是正常球也可能是怪球，但如知道它是怪球则它比正常球轻，黑色球表示它可能是正常球也可能是怪球，但如知道它是怪球则它比正常球重。换句话说，白色黑色球含有部份信息，如果知道它是怪球，就知道它是轻还是重了。灰色球则没有任何信息，即便我们知道它是怪球，它是轻是重还得进一步确定。

一开始12个球都是灰色球。

各取4球分别放在天平的两侧。分两种情况分析。

第一种情况，两边相等，天平上8个球均是正常球，涂上绿色，还剩4个灰色球。取3个绿色球放天平一边，3个灰色球放另一边。如两边相等，将3个灰色球涂上绿色，剩下一个灰色球（和一个绿色球）再称一次便知轻重了。如两边不等，给3个灰球涂上颜色：灰球重则涂黑，轻则涂白。剩下的灰球是是正常球，涂绿。最后三个白球或者黑球，再称一次可找到坏球。如坏球为白则轻，为黑则重，无需再称了。以白球为例，天平两边各放一个白球，如两边相等则为正常球，都涂绿，最后的白球是怪球并且较轻；如两边不等则轻的为怪球，其它的白球涂绿。

第二种情况，两边不等，未称的4个灰球为正常球，涂上绿色。剩下的8个球，分别涂上白色黑色：重的那边为黑，轻的那边为白。取两个白球放天平左边，两个白球放天平右边，天平左右各加一个黑球。如两边相等，天平上的球全部正常，涂上绿色，剩下的两个黑球分放天平两侧再称一次可知重的那个为怪球。如两边不等，说明怪球要么在轻的那边两个白球之中，要么是重的那边的黑球，如何确定是哪种呢？将怀疑中的白球分放在天平两边再称一次便知。