星星還是那顆星星，月亮還是那個月亮，問題也還是那個問題：有12個外表一模一樣的球，其中有一個壞球重量不同於其他11個。隻允許使用三次天平，如何找出壞球並弄清輕重？
為敘述方便，先給球用數字1，2，3，。。。，12標上號。
每用一次天平，就會有一個結果：左重，右重，或左右平衡。左重用L表示，右重用R表示，左右平衡就用B（BALANCED）表示。從左到右依次寫下三次結果。比方說，LBR表示第一次左重，第二次左右平衡和第三次右重。我們的目標是設計一種三次稱球的方案，使得從稱球的結果可以簡單判斷哪一個是壞球，是輕還是重。如何做到這一點呢？
我們知道，三次稱球，有27種可能的結果，因為每稱一次有三種可能結果。其中有三種結果，我們可設法排除。哪三種呢？就是LLL，RRR和BBB。結果BBB說明什麽？它說明壞球三次都沒有上天平。不上天平稱稱，如何能知道是輕還是重呢？所以每個球至少得用一次天平。另外，LLL和RRR表示壞球始終在天平的同一邊，我們也得排除。排除了這三種情況，還剩24種可能的結果。
另一方麵，壞球可以是12個中的任何一個，又有輕重兩種可能，所以也是24種可能。如果能夠找到一種方案，使得24種可能的結果分別對應24種可能，那就萬事大吉了。
有這樣的方案嗎？
為了方便，先假設壞球為重。結果LRB說明了什麽？它表示：壞球先在左邊，然後在右邊，最後不在天平上。用l，r，b分別表示某球在左邊，右邊和不在天平上。也就是說，如果壞球為重，稱球的結果可以跟蹤壞球三次分別在哪一組，所以LRB對應lrb了。
我們稱lrb為某球的軌跡。總共有12個球，所以有12個軌跡。自然，我們希望12個軌跡不同。
假如某球有軌跡lrb，也就是說，某球分別依次在左邊，右邊和不在天平上。如果它是壞球，會有什麽結果？如壞球為重，結果就是LRB，為輕則是RLB。所以同一個軌跡對應兩個可能的結果。
當然，軌跡rlb也對應兩個不同的結果LRB和RLB。所以我們希望軌跡rlb和lrb隻出現一次。類似，也希望rrb和llb隻出現一次。不難發現，可以把軌跡分成12類，我們希望每類中隻出現一次。這12分類別是：{llr,rrl} {llb,rrb} {lrb,rlb} {lrl,rlr} {lrr,rrl} {lbr,rbl} {lbb,rbb} {lbl,rbr} {bbl,bbr} {blr,brl} {blb,brb} {bll,brr}。
每用一次天平，相當於把球分成l，r，b三組。為了使每次獲得的信息量最大，我們希望三組都含同樣的球數，即每組4個。如何從12類中找出12個軌跡，使得每次三組都正好有4個球呢？
我們將軌跡按如下方法分成兩大類。先定義l->r->b->l為順時針變化。任何一個軌跡，都至少有一次變化（因為我們排除了lll，rrr和bbb），也就是從一組換到另一組。我們隻看第一次變化：如是順時針變化，就將它歸為順時針類，否則歸為逆時針類。比如lrb屬順時針類，因為它的第一次變化是l->r，為順時針變化。軌跡bbl也屬順時針類，因為它的第一次變化b->l為順時針變化。
從12個軌跡類中找出順時針類，我們不妨稱之為重球類，也稱逆時針類為輕球類。重球類為：llr，lrb，lrl，lrr，rrb，rbl，rbb，rbr，bbl，bll，blb，blr。
我們隨便給重球類分派球號。比如：
球號 重球類 輕球類
----- --------- ----------
1 llr rrl
2 lrb rlb
3 lrl rlr
4 lrr rll
5 rrb llb
6 rbl lbr
7 rbb lbb
8 rbr lbl
9 bbl bbr
10 bll brr
11 blb brb
12 blr brl
然後再根據球號所對應的重球類軌跡製定稱球方案如下：
天平左邊 天平右邊
----------------- -----------------
1，2，3，4 5，6，7，8
1，10，11,12 2，3，4，5
3，6，9，10 1，4，8，12
這樣一來，就很容易根據結果找出答案了。將結果中的L變成l，R變成r以及B變成b，也即將結果變成軌跡。如果軌跡在重球類，則壞球為重，否則為輕。它所對應的球號就是壞球。比如結果是RRL，其軌跡為rrl，屬輕球類，對應1號球，所以壞球為1號球並且輕。
有興趣的朋友不妨試試其它結果。HAVE FUN！
請閱讀更多我的博客文章>>>
