稱球問題（2）

       榕城老應

在一堆等重的球中有一個重量不同的次品球，用天平稱k次找出來，問這堆球最多可以是多少？

經過前麵這些思考，發現也不難有一般性結果。

首先考慮一個簡單的情況，假如已知這個次品比正品重（或輕），把這堆球三等分，放兩堆上天平稱一次可以指出是在那堆。所以稱k次可以分辨3**k個球。

現在回來考慮原來問題，把球分三堆，放兩堆等數的球上天平，如果平衡，次品當然在外麵這一堆。如果不平衡，比如說左邊重，我們隻知道外邊的肯定是正品，但次品不知道是在天平的哪一邊。重的那一邊的球定義為“重次球”，如果在這邊，那次品一定是較重。輕的那一邊定義為“輕次球”，若是在這邊則次品較輕。所以天平上的這些球經過一次稱量之後已經被消除掉一部分的不確定性，稱為半確定的球。半確定的球集合中隻有兩類的球，重次球或輕次球。

我們現在證明。

引理1：稱k次可以並最多在3**k個半確定的球中找出次品，並且知道其輕重。

用數學歸納法，k=1。3個半確定的球，一定有至少有兩個屬於同一類，比如說重次球，將這兩個上天平，重的那個就是次品，如果平衡，外邊的那個就是次品，而且從它的類別知道這次品是較重還是較輕。驗證正確。

假設結論對k-1次正確。將3**k個半確定的球三等分，天平一邊各放3**(k-1)個球，使得兩邊共有偶數個重次球，記為2a個。這總是可以做到的。因為我們可以把“不齊整”數目的球放在外麵。這樣天平左右各有a個重次球和3**(k-1)-a個輕次球。這時如果左邊重，左邊的a個重次球和右邊的3**(k-1)-a個輕次球，共3**(k-1)個半確定球有嫌疑，其他都是正品。如果右邊重，同理將嫌疑縮小到3**(k-1)個半確定球。如果平衡，嫌疑在外麵的3**(k-1)個半確定球中。我們已知用k-1次可以解決3**(k-1)個半確定的球。證畢。

引理2：如果加一個已知的正品球稱k次，可以並最多在（3**k+1）/2個球中找出次品，但有且僅有一種情況不知其次品的輕重。

在k=1情況，有2個球，取一個與正品球上天平，如果平衡，次品在外麵，但不知它比正品輕還是重，注意這是歸納證明中僅有的情況。

假設結論對k-1次正確。考慮第一次天平稱量，一邊取（3**（k-1）-1）/2個加上一個正品球，另一邊取（3**（k-1）+1）/2個球。我們知道這次稱量以後，如果天平平衡，那麽嫌疑在外麵。餘下k-1次可以解決這裏的（3**（k-1）+1）/2個球，有且僅有一種情況不知其次品的輕重。如果天平不平衡，天平的兩邊都是半確定的球。由引理1知道，餘下k-1次可以解決這裏的3**(k-1)個球。因為這個數是奇數，所以我們必須在第一次天平稱量時再加上一個已知的正品球。因此稱k次，可以並最多解決3**（k-1）+（3**（k-1）+1）/2=（3**k+1）/2個球。證畢。

定理：在一堆等重球中有一個重量不同的次品球，用天平稱k次找出來，這堆球最多且可以是（3**k-1）/2個球。

在第一次稱量我們最多可以將3**(k-1)-1個球兩等分放在天平上，如果不平衡，由引理1，可以再稱k-1次解決。如果平衡，天平這裏都是已知球，由引理2，可以再稱k-1次解決外麵的（3**（k-1）+1）/2個球。所以總共可以解決（3**k-1）/2個球。證畢。

由這個定理我們可以知道稱2，3，4，5次，分別可以在4，13，40，121個球中找出那個次品，因為這個證明是構造性的，所以知道該怎麽稱量。

如果在稱球問題中不知道有沒有這個次品球存在，這和判別出嫌疑的次品球是較輕還是較重是同一個問題。在引理2證明中知道，隻有每次分堆時，天平都是平衡的，總是被分在外麵的那個球被認為是次品球時不知輕重。把這個球去掉，或者說要解決的問題少了一個球就行了。這也就是說，用天平稱k次可以在一堆（3**k-3）/2個球中確定有沒有一個重量不同的次品，如果有，是哪一個，是較輕還是較重。

有人問，如果我要解決問題那堆球比你構造性證明中的數量少，怎麽辦？你每次分堆時把不齊整的數擱在外邊那堆，不就行了？