趣味數學（五）再論稱球

趣味數學（五）再論稱球

2013-03-21 13:33:19

還是那個老問題：有12個外表一模一樣的球，其中有一個壞球重量不同於其他11個。隻允許使用三次天平，如何找出壞球並弄清是輕是重？

上一文已經提過，利用信息論裏的結論，已有可行的解法。但是，那個解法有個缺陷：就是下一次如何稱，依賴於上一次的結果。你沒法偷閑，得盯著天平等結果，再設計下一步的方案。這樣不好，你總得抽點時間上上網，瞅瞅熱鬧，對不？有沒有更好的方法呢？

有的。

先談談想法：

每用一次天平，就會有一個結果：左重，右重，或左右平衡。左重用L表示，右重用R表示，左右平衡就用B（BALANCED）表示。從左到右依次寫下三次結果。比方說，LBR表示第一次左重，第二次左右平衡和第三次右重。

總共會有多少個不同的組合呢？因為每一個位置有三種可能，不難算出，答案是27。在這27種可能中，包括了LLL，BBB和RRR。

結果BBB是什麽意思？它表示，三次稱球，壞球都不在天平上。所以我們可以要求，每一個球至少得上一次天平，這樣可避免BBB的出現。再看LLL又是什麽意思。它表示，壞球要麽三次都在左邊，或三次都在右邊，如何排除這種可能？隻需不讓同一個球每次都在同一邊即可，這通時也排除了RRR的可能。

好了，這樣就隻有24種可能了。

再來看看LBR和RBL分別代表什麽意思。假設我們先得出LBR，那麽如果每次都把天平兩邊的球互換一下，結果就自然成了RBL了。所以這本質上代表同一種方案，隻不過是將天平左右的球互換了一下而已。如果從LBR得出某號球是壞球並且重，那麽RBL自然就得出該號球為壞球並且輕了。類似，LLR和RRL表應該揭示同一個壞球，隻不過輕重互換。依此類推，24種可能就分成了12組，代表本質上12種不同的方案。每組各含兩種可能，揭示了同一個壞球，其中一個揭示壞球為重，另一個揭示壞球為輕。

這12組分別是：{LLB,RRB}, {LLR,RRL}, {LBL,RBR}, {LBB, RBB}, {LBR,RBL}, {LRL,RLR}, {LRB,RLB}, {LRR,RLL}, {BLL,BRR}, {BLB,BRB}, {BLR, BRL}, {BBL, BBR}。

那麽，LLB和RRB哪一個表示壞球為重呢？這個可由我們自定。假設LLB表示某號球為壞球且重，它又是什麽意思？它表示該號球第一次第二次均在天平的左邊，第三次不在天平上了。如果這樣的球隻有一個，那它一定就是壞球了。我們的目標是，設計一種方案，使得每一個結果組合對應著唯一一個球，從而把壞球找到並知輕重。再看LLB，從第二次到第三次結果發生了變化，這又說明壞球就在變換了的那些球中，而且是從天平上換到了比方是桌子上。

為方便起見，根據第一次變化來給每個結果組合分組。先定義L->B->R->L為順時針方向，則L->R->B->L為逆時針方向。

如果第一次變化是順時針方向，則將該接果組合歸為重球組，否則歸為輕球組。比如LLB，它的第一次變化是從L變為B，是順時針方向，所以歸為重球組。反之，RRB的第一次變化是從R變為B，所以歸為輕球組。大家不難發現，12組中，每一組中的兩個結果隻有一個歸為重球組，另一個歸為輕球組。

同樣為了方便，把上述12組分別標上從1到12個號碼，於是有下麵的結果。

組號　重球組　輕球組
1     LLB     RRB
2   RRL   LLR
3     LBL   RBR
4   LBB   RBB
5     LBR   RBL
6     RLR     LRL
7   RLB   LRB
8     RLL     LRR
9     BRR     BLL
10 BRB     BLB
11 BRL     BLR
12 BBR     BBL

現在我們來設計天平的用法。將組號和球號對應起來，也就是組號代表球號。

將重球組中第一個字母為L的球放到天平左邊，第一個字母為R的球放到天平右邊，這樣稱第一次。所以，第一次左邊是1，3，4，5四個球，而右邊是2，6，7，8四個球。類似，將重球組中第二個字母為L的球放到天平左邊，第二個字母為R的球放到天平右邊，這樣稱第二次。第二次左邊有1，6，7，8四個球，右邊有2，9，10，11四個球。接下去，將重球組中第三個字母為L的球放到天平左邊，第三個字母為R的球放到天平右邊，這樣稱第三次。第三次左邊有2，3，8，11四個球，右邊有5，6，9，12四個球。

所以三次稱球方案如下：

左邊        右邊
1，3，4，5    2，6，7， 8
1，6，7，8    2，9，10，11
2，3，8，11   5，6，9， 12

從左到右依次寫下三次稱出的結果。

如果最後的結果是LBB，我們有什麽結論？首先，LBB對應4號球，其次，它屬重球組，所以結論是：4號球是壞球並且重。為什麽是這樣？該結果表示壞球一開始在天平上，後兩次都不在天平上了，隻有4號球符合這個條件，而從第一次稱球結果就知4號球重。

再看最後的結果是LRB的情形：它對應7號球，屬輕球組，所以7號球為壞球並且輕。其它情形可以此類推，讀者自己試試看。

當然，我們也可如下推理。

1）假設已知壞球較重，如1號球為壞球時，三次稱出的結果應該是LLB。同樣，如2號球為壞球，三次稱出的結果就是RRL了。以此類推我們可以得出下麵的重球表：

球號   結果
1      LLB
2      RRL
3     LBL
4      LBB
5        LBR
6        RLR
7        RLB
8      RLL
9      BRR
10     BRB
11     BRL
12       BBR

由於表上的對應關係，如果反過來知道三次的稱球結果在右邊，我們就很容易找到對應的壞球並且能判斷為重了。

2）同理，如果已知壞球為輕，又可得出下麵的輕球表。

球號結果
1 RRB
2    LLR
3    RBR
4    RBB
5 RBL
6    LRL
7    LRB
8 LRR
9 BLL
10   BLB
11   BLR