2008 (4)
帶信息的球
先複習一下帶顏色球的含意：綠球表示已知該球是好球，白球表示可能是好球，也可能是壞球，但如是壞球則輕；黑球表示可能是好球，也可能是壞球，但如是壞球則重；灰球則無任何信息，即便知其是壞球，還是不知（較好球而言）是輕還是重。換言之，黑球和白球已有部分信息，綠球則有完全信息，而灰球不含任何信息。
我們可以證明如下的結論：
引理一：如果n個帶部分信息的球中恰有一個壞球，而且 3^(k-1) < n <= 3^k, 則用k次天平就能找出壞球並知其輕重。除了一個例外，就是k=1時，如果2個球1白1黑，則多少次都沒法找到壞球。
引理二：如果n個灰色球中恰有一個是壞球，但有好球（綠色球）可以借用，且 {3^(k-1)-1}/2 < n <= (3^k-1)/2, 則用k次天平就能找出壞球並知輕重。
什麽是有好球可以借用？以k=3為例說明一下。在n=13的情況下，如何隻用3次天平就找出壞球並知輕重？先借用9個好球放在天平的一邊，另一邊放9個灰色球。如兩邊持平，則9個灰色球為好球，塗上綠顏色。壞球在剩下的4個灰球中，因為有好球可以借用，再用兩次天平就可找出壞球並知輕重了（請讀者仔細想想）。如兩邊不平，灰球輕則將其塗上白色，重則塗上黑色，壞球必在這9個球中。因為有部分信息，用引理一，用兩次天平就可找出壞球並知輕重了。如無好球借用，3次是不可能一定從13個灰色球中找出壞球並知輕重的。當然，可以找出其中的壞球，但有可能不知輕重，讀者不妨仔細想想。
兩個引理都可以用數學歸納法證明，這裏從略。
有了這兩個引理，就不難證明下麵的定理了：
定理：如果n=(3^k-3)/2個不含任何信息（灰色球）的球中恰有一個壞球，則用k次天平就能找出壞球並知輕重。
證明如下：令x={3^(k-1)-1}/2, 則n=3x。天平兩邊各放x個球，稱過之後有兩種可能。
情形1， 天平持平：這時天平上的球都是好球，塗上綠色。剩下的x個灰球還是不帶任何信息，但已有好球可以借用。引用引理二，剩下的x個球再用k-1次天平就能找出壞球並知輕重。
情形2，天平不平 : 將輕的那邊的球塗上白色，重的那邊塗上黑色，剩下的是好球，塗上綠色。現在2x個球已有部分信息，由引理一可知再用k-1次天平便可找到壞球並知輕重。
在定理中令k=3，就是著名的12球問題了。
