趣味數學(五)再論稱球

本文內容已被 [ 朝霞滿天 ] 在 2013-03-23 06:24:32 編輯過。如有問題,請報告版主或論壇管理刪除.
趣味數學(五)再論稱球 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
12   BBL

同樣,如果結果在上表中,也很容易找到對應的壞球了並知其為輕了。

今天先談到這裏,以後再試圖給出更通俗易懂的解釋。有興趣的同學,請等著下一隻鞋子落地。



請閱讀更多我的博客文章>>>

 
  • 羊崽
  • 疑問
  • 舅公祖祖
  • 原創記事
  • 小故事
  • 所有跟帖: 

    完全繞暈了。:)這篇沒有上一篇好懂。多謝! -水寧- 給 水寧 發送悄悄話 水寧 的博客首頁 (0 bytes) () 03/21/2013 postreply 21:03:57

    多謝水寧,這篇是不好懂,容我慢慢改。 -朝霞滿天- 給 朝霞滿天 發送悄悄話 朝霞滿天 的博客首頁 (0 bytes) () 03/22/2013 postreply 05:14:09

    請您先登陸,再發跟帖!