放下無價值的砝碼

中年男子在一家公司任職，原本他有很大的希望被晉升為業(yè)務(wù)部主管。

然而，一個與他暗中競爭的同事，竟然將他以前工作中所出現(xiàn)的失誤全部羅列出來，遞交給了董事長。

于是，他升職的希望便在對方的嫉妒和攻擊下暫時擱淺。

當(dāng)他把這一切告訴他的妻子后，他的妻子卻一點(diǎn)都不理解，這令他十分沮喪。

男子來到山上找到大師，希望幫忙解除內(nèi)心的痛苦。

大師笑著問他：“在你身邊一定有另外一個女人理解你，是嗎 ”

男子坦誠地點(diǎn)了點(diǎn)頭。

大師并沒有過多解釋，而是起身出去了一會兒。

回來時，他手中多了一個細(xì)細(xì)的橡皮圈兒和兩個帶掛鉤的砝碼。

當(dāng)著男子的面，大師把那兩個砝碼掛在了橡皮圈兒上面。

那兩個砝碼的重量，幾乎把橡皮圈兒繃緊到了極限，如果稍一用力，就會有斷裂的可能。

中年男子疑惑地看著大師怪異的舉動。

大師問道：“那個陷害你的同事升職了嗎 ”

他搖了搖頭。

大師繼續(xù)問：“那么，請你如實告訴我，你的那個同事所說的事情是否真實 ”

他思忖了一會兒，回答說：“應(yīng)該有一半是事實吧。”

聽了之后，大師就笑了，說：“既然他也沒有升職，而且還給你指出了那么多的不足，那么你不但不該仇視他，還應(yīng)該感謝他。如果你今后把自己出現(xiàn)失誤的地方全部做好，他還會說什么呢 ”

中年男子贊同地點(diǎn)了點(diǎn)頭。大師隨手摘下一個砝碼，橡皮圈兒頓時彈回去大半。

接著，大師又問：“你的妻子雖然一時不理解你，但是你們之間感情的裂痕已到了無可挽救的地步了嗎 ”

他又搖了搖頭，回答說：“感情上還算過得去，至少我還有一個很乖很爭氣的女兒。”

大師問：“也就是說，即使另外一個女人再理解你，你暫時也不可能下定決心和她生活在一起，是嗎 ”

沉默了一會兒，中年男子如實地點(diǎn)了點(diǎn)頭。

大師暢然大笑起來，又把另一個砝碼從橡皮圈兒上摘了下來。

然后，大師將那個恢復(fù)原狀的橡皮圈兒遞給了他，并解釋道：“現(xiàn)在，你已經(jīng)沒有一點(diǎn)兒負(fù)擔(dān)了，又恢復(fù)了先前的彈性，你還是那個完整無缺的‘橡皮圈兒’呀?！?/p>

聽到這兒，中年男子才恍然大悟。

是啊，只要摘下生活中那些缺少價值的砝碼，我們的生命又會恢復(fù)先前的彈性！

有12枚硬幣,其中有一顆是假幣,和一架無砝碼和刻度的天平,稱3次,找出假幣并且算出比真幣重還?C

稱球問題——經(jīng)典智力題推而廣之三

異調(diào)

說明

這篇文章試圖給出稱球問題的一個一般
的和嚴(yán)格的解答。正因為需要做到一般和嚴(yán)
格，就要考慮許多平時遇不到的特別情形，
所以敘述比較繁瑣。如果對讀者對嚴(yán)格的證
明沒有興趣，可以只閱讀介紹問題和約定記
號的第一、第二節(jié)，以及第三節(jié)末尾27個球
的例子，和第五節(jié)13個球和40個球的解法。
事實上所有的技巧都已經(jīng)表現(xiàn)在這幾個例子
里了。

一、問題

稱球問題的經(jīng)典形式是這樣的：

“有十二個外表相同的球，其中有一個壞球，它的重量和其它十
一個有輕微的（但是可以測量出來的）差別?，F(xiàn)在有一架沒有砝碼的
很靈敏的天平，問如何稱三次就保證找出那個壞球，并知道它比標(biāo)準(zhǔn)
球重還是輕?！?

這可能是網(wǎng)上被做過次數(shù)最多的一道智力題了。它的一種解法如
下：

將十二個球編號為1-12。

第一次，先將1-4號放在左邊，5-8號放在右邊。
1.如果右重則壞球在1-8號。
第二次將2-4號拿掉，將6-8號從右邊移到左邊，把9-11號放
在右邊。就是說，把1,6,7,8放在左邊，5,9,10,11放在右邊。
1.如果右重則壞球在沒有被觸動的1,5號。如果是1號，
則它比標(biāo)準(zhǔn)球輕；如果是5號，則它比標(biāo)準(zhǔn)球重。
第三次將1號放在左邊，2號放在右邊。
1.如果右重則1號是壞球且比標(biāo)準(zhǔn)球輕；
2.如果平衡則5號是壞球且比標(biāo)準(zhǔn)球重；
3.這次不可能左重。
2.如果平衡則壞球在被拿掉的2-4號，且比標(biāo)準(zhǔn)球輕。
第三次將2號放在左邊，3號放在右邊。
1.如果右重則2號是壞球且比標(biāo)準(zhǔn)球輕；
2.如果平衡則4號是壞球且比標(biāo)準(zhǔn)球輕；
3.如果左重則3號是壞球且比標(biāo)準(zhǔn)球輕。
3.如果左重則壞球在拿到左邊的6-8號，且比標(biāo)準(zhǔn)球重。
第三次將6號放在左邊，7號放在右邊。
1.如果右重則7號是壞球且比標(biāo)準(zhǔn)球重；
2.如果平衡則8號是壞球且比標(biāo)準(zhǔn)球重；
3.如果左重則6號是壞球且比標(biāo)準(zhǔn)球重。
2.如果天平平衡，則壞球在9-12號。
第二次將1-3號放在左邊，9-11號放在右邊。
1.如果右重則壞球在9-11號且壞球較重。
第三次將9號放在左邊，10號放在右邊。
1.如果右重則10號是壞球且比標(biāo)準(zhǔn)球重；
2.如果平衡則11號是壞球且比標(biāo)準(zhǔn)球重；
3.如果左重則9號是壞球且比標(biāo)準(zhǔn)球重。
2.如果平衡則壞球為12號。
第三次將1號放在左邊，12號放在右邊。
1.如果右重則12號是壞球且比標(biāo)準(zhǔn)球重；
2.這次不可能平衡；
3.如果左重則12號是壞球且比標(biāo)準(zhǔn)球輕。
3.如果左重則壞球在9-11號且壞球較輕。
第三次將9號放在左邊，10號放在右邊。
1.如果右重則9號是壞球且比標(biāo)準(zhǔn)球輕；
2.如果平衡則11號是壞球且比標(biāo)準(zhǔn)球輕；
3.如果左重則10號是壞球且比標(biāo)準(zhǔn)球輕。
3.如果左重則壞球在1-8號。
第二次將2-4號拿掉，將6-8號從右邊移到左邊，把9-11號放
在右邊。就是說，把1,6,7,8放在左邊，5,9,10,11放在右邊。
1.如果右重則壞球在拿到左邊的6-8號，且比標(biāo)準(zhǔn)球輕。
第三次將6號放在左邊，7號放在右邊。
1.如果右重則6號是壞球且比標(biāo)準(zhǔn)球輕；
2.如果平衡則8號是壞球且比標(biāo)準(zhǔn)球輕；
3.如果左重則7號是壞球且比標(biāo)準(zhǔn)球輕。
2.如果平衡則壞球在被拿掉的2-4號，且比標(biāo)準(zhǔn)球重。
第三次將2號放在左邊，3號放在右邊。
1.如果右重則3號是壞球且比標(biāo)準(zhǔn)球重；
2.如果平衡則4號是壞球且比標(biāo)準(zhǔn)球重；
3.如果左重則2號是壞球且比標(biāo)準(zhǔn)球重。
3.如果左重則壞球在沒有被觸動的1,5號。如果是1號，
則它比標(biāo)準(zhǔn)球重；如果是5號，則它比標(biāo)準(zhǔn)球輕。
第三次將1號放在左邊，2號放在右邊。
1.這次不可能右重。
2.如果平衡則5號是壞球且比標(biāo)準(zhǔn)球輕；
3.如果左重則1號是壞球且比標(biāo)準(zhǔn)球重；

夠麻煩的吧。其實里面有許多情況是對稱的，比如第一次稱時的
右重和右輕，只需考慮一種就可以了，另一種完全可以比照執(zhí)行。我
把整個過程寫下來，只是想嚇唬嚇唬大家。

稍微試一下，就可以知道只稱兩次是不可能保證找到壞球的。如
果給的是十三個球，以上的解法也基本有效，只是要有個小小的改動，
就是在這種情況下，在第一第二次都平衡的時候，第三次還是有可能
平衡（就是上面的第2.2.2步），那么我們可以肯定壞球是13號球，可
是我們沒法知道它到底是比標(biāo)準(zhǔn)球輕，還是比標(biāo)準(zhǔn)球重。如果給的是
十四個球，我們會發(fā)現(xiàn)無論如何也不可能只稱三次，就保證找出壞球。

一個自然而然的問題就是：對于給定的自然數(shù)N，我們怎么來解有
N個球的稱球問題？

在下面的討論中，給定任一自然數(shù)N，我們要解決以下問題：
⑴找出N球稱球問題所需的最小次數(shù)，并證明以上所給的最小次數(shù)的確
是最小的；
⑵給出最小次數(shù)稱球的具體方法；
⑶如果只要求找出壞球而不要求知道壞球的輕重，對N球稱球問題解決
以上兩個問題；

還有一個我們并不是那么感興趣，但是作為副產(chǎn)品的問題是：
⑷如果除了所給的N個球外，另外還給一標(biāo)準(zhǔn)球，解決以上三個問題。
二、記號

我們先不忙著馬上著手解決上述問題。先得給出幾個定義，尤其
是，要給出比較簡單的符號和記法。大家看到上面給出的解法寫起來
實在麻煩——想象一下如果我們要用這種方法來描述稱40個或1000個
球的問題！

仍舊考慮十二個球的情況和上面舉的解法。在還沒有開始稱第一
次時，我們對這十二個球所知的信息就是其中有一或較輕，或較重的
壞球，所以以下24種情況都是可能的：
1. 1號是壞球，且較重；
2. 2號是壞球，且較重；
……
12. 12號是壞球，且較重；
13. 1號是壞球，且較輕；
14. 2號是壞球，且較輕；
……
24. 12號是壞球，且較輕。
沒有其他的可能性，比如說“1、2號都是壞球，且都較重”之類。當(dāng)
我們按上面解法“先將1-4號放在左邊，5-8號放在右邊”稱過第一次
以后，假設(shè)結(jié)果是右重，稍微分析一下，就會知道上面的24種情況中，
現(xiàn)在只有8種是可能的，就是
1. 1號是壞球，且較輕；
2. 2號是壞球，且較輕；
3. 3號是壞球，且較輕；
4. 4號是壞球，且較輕；
5. 5號是壞球，且較重；
6. 6號是壞球，且較重；
7. 7號是壞球，且較重；
8. 8號是壞球，且較重。
我們把諸如“1號是壞球，且較重，其他球都正?！焙汀?號是壞球，
且較輕，其他球都正?！边@樣的情況，稱為一種“布局”，并記為：
(1重) 和 (2輕)
我們把“先將1-4號放在左邊，5-8號放在右邊”這樣的步驟，稱為一
次“稱量”。我們把上面這次稱量記為
(1,2,3,4; 5,6,7,8)
或
(1-4; 5-8)
也就是在括號內(nèi)寫出參加稱量的球的號碼，并且以分號分開放在左邊
和放在右邊的球號。在最一開始，我們有24種可能的布局，而在經(jīng)過
一次稱量(1-4; 5-8)后，如果結(jié)果是右重，我們就剩下上述8種可能
的布局。我們的目的，就是要使用盡量少的稱量，而獲得唯一一種可
能的布局——這樣我們就知道哪個球是壞球，它是比較重還是比較輕。

這里我們注意到?jīng)]有必要去考慮兩邊球數(shù)不相等的稱量。因為壞
球和標(biāo)準(zhǔn)球重量之間的差別很小，小于標(biāo)準(zhǔn)球的重量，所以當(dāng)天平兩
邊球數(shù)不一樣時，天平一定向球比較多的那邊傾斜。所以在進(jìn)行這樣
一次稱量之前，它的的結(jié)果就可以被預(yù)料到，它不能給我們帶來任何
新的信息。事實上在看完本文以后大家就很容易明白，即使壞球和標(biāo)
準(zhǔn)球重量之間的差別很大，也不會影響本文的結(jié)論。因為考慮這種情
況會使問題變麻煩，而并不能帶來有趣的結(jié)果，我們就省略對此的考
慮。

現(xiàn)在我們看到，上面關(guān)于十二個球問題的解法，其實就是由一系
列稱量組成的——可不是隨隨便便的組合，而是以這樣的形式構(gòu)成的：
稱量1
如果右重，則
稱量3
……
如果平衡，則
稱量2
……
如果左重，則
稱量4
……
省略號部分則又是差不多的“如果右重，則……”等等。所以這就提
示我們用樹的形式來表示上面的解法：樹的根是第一次稱量，它有三
個分支（即三棵子樹，于是根有三個子節(jié)點(diǎn)），分別對應(yīng)著在這個稱
量下的右重、平衡、左重三種情況。在根的三個子節(jié)點(diǎn)上，又分別有
相應(yīng)的稱量，和它們的三個分支……如果具體地寫出來，就是

|--右--( 1輕)
|--右--(1 ; 2)|--平--( 5重)
| |--左--( )
|
| |--右--( 2輕)
|--右--(1,6-8; |--平--(2 ; 3)|--平--( 4輕)
| 5,9-11)| |--左--( 3輕)
| |
| | |--右--( 7重)
| |--左--(6 ; 7)|--平--( 8重)
| |--左--( 6重)
|
| |--右--(10重)
| |--右--(9 ;10)|--平--(11重)
| | |--左--( 9重)
| |
| | |--右--(12重)
(1-4;5-8)|--平--(1-3; |--平--(1 ;12)|--平--(13輕, 13重)*
| 9-11)| |--左--(12輕)
| |
| | |--右--( 9輕)
| |--左--(9 ;10)|--平--(11輕)
| |--左--(10輕)
|
| |--右--( 6輕)
| |--右--(6 ; 7)|--平--( 8輕)
| | |--左--( 7輕)
| |
| | |--右--( 3重)
|--左--(1,6-8; |--平--(2 ; 3)|--平--( 4重)
5,9-11)| |--左--( 2重)
|
| |--右--( )
|--左--(1 ; 2)|--平--( 5輕)
|--左--( 1重)
（*：對應(yīng)十三個球的情形。）
這里“右”、“平”和“左”分別表示稱量的結(jié)果為“右重”、“平
衡”和“左重”所對應(yīng)的分支。在樹的葉子（就是最右邊沒有子節(jié)點(diǎn)
的那些節(jié)點(diǎn)）部分，我們標(biāo)出了“能夠到達(dá)”這些節(jié)點(diǎn)的布局，也就
是說在進(jìn)行每一節(jié)點(diǎn)上的稱量時，這個布局所給的結(jié)果和通往相對應(yīng)
的葉子的道路上所標(biāo)出的“右”、“平”和“左”相符合。從這個圖
我們也可以清楚地看到，根下的左分支和右分支是對稱的：只需要把
所有的“右”改成“左”，“左”改成“右”，“輕”改成“重”，
“重”改成“輕”；節(jié)點(diǎn)(1-3; 9-11)下的左分支和右分支也有這個
特點(diǎn)。

（如果有朋友對樹理論感興趣，可以參考隨便哪一本圖論或者離
散數(shù)學(xué)的書。在這里我們只用到樹理論里最基本的知識，所用的名詞
和結(jié)論都是相當(dāng)直觀的。所以如果你不知道樹理論，用不著特別去學(xué)
也可以看懂這里的論證。）

所以給定一棵三分樹（就是說除了葉子以外其他的節(jié)點(diǎn)都有三個
子節(jié)點(diǎn)的樹），在每個不是葉子的節(jié)點(diǎn)上給定一個稱量，并且規(guī)定這
個節(jié)點(diǎn)下的三個分支（子樹）分別對應(yīng)右重、平衡、左重的情況，我
們就得到了一種稱球的方法。我們把這樣一棵三分樹稱為一個“策略”
或一棵“策略樹”。你可以給出一個平凡的策略，比如說無論發(fā)生了
什么事總是把1號和2號球放在左右兩側(cè)來稱（在葉子上我們沒有寫出
相應(yīng)的布局，用@來代替）：

|--右--@A
|--右--(1; 2)|--平--@
| |--左--@
|
| |--右--@
(1; 2)|--平--(1; 2)|--平--@
| |--左--@
|
| |--右--@B
| |--右--(1; 2)|--平--@
| | |--左--@
| |
| | |--右--@
|--左--(1; 2)|--平--(1; 2)|--平--@
| |--左--@
|
| |--右--@
|--左--(1; 2)|--平--@
|--左--@

當(dāng)然這么個策略沒什么用場，只能讓我們知道1號球和2號球之間的輕
重關(guān)系。另外我們看到，每個分支不一定一樣長，上面這棵策略樹根
下面左分支就比較長。

一棵樹的高度是葉子到根之間的結(jié)點(diǎn)數(shù)的最大值加一。比如說上
面這個圖中，葉子A和根間有1個節(jié)點(diǎn)，而葉子B和根間有2個節(jié)點(diǎn)，沒
有和根之間的節(jié)點(diǎn)數(shù)超過2的葉子。所以它的高度是2+1=3。前面十二
球解法策略樹的高度也是3。一棵沒有任何分支，只有根節(jié)點(diǎn)的樹，我
們定義它的高度是0。

顯然，策略樹的高度就是實行這個策略所需要的稱量的次數(shù)。我
們的目的，就是找到一棵“好”的策略樹，使得它的高度最小。

什么是“好”策略？我們回過頭來再看十二球解法策略樹。我們
說過，葉子上的那些布局都是從根開始通向葉子的。比如說布局(7重)，
它之所以在那片葉子上是因為按照這個策略，三次稱量的結(jié)果是“右
左右”；又比如說布局(11重)，它之所以在那片葉子上是因為按照這
個策略，三次稱量的結(jié)果是“平右平”。如果兩個布局通向同一片葉
子，那么就是說按照這個策略，三次稱量的結(jié)果是完全一樣的，于是
我們就不能通過這個策略來把這兩種布局區(qū)分開來。比如說在十三個
球的情況下，(13輕)和(13重)都通向和“平平平”相對應(yīng)的葉子，這
兩個布局中13號球或者輕或者重，于是我們知道13號球一定是壞球，
但是通過這個策略我們不可能知道它到底是輕還是重。

所以對于標(biāo)準(zhǔn)的稱球問題（找出壞球并知其比標(biāo)準(zhǔn)球重或輕）的
“好”策略，就是那些能使不同的布局通向不同的葉子的策略。
三、每個球都已知可能為輕或可能為重的情況

先引入一個記號：對于任意實數(shù)a，我們用{a}表示大于等于a的最
小整數(shù)，比如說{2.5}=3，{4}=4；我們用[a]表示小于等于a的最大整
數(shù)，比如說[2.5]=2，[4]=4。

我們首先考慮這樣一種布局的集合。假設(shè)m，n為兩個非負(fù)實數(shù)，
不同時為0。在編號從1到m+n的m+n個球中，我們知道1到m號球要么是
標(biāo)準(zhǔn)球，要么比標(biāo)準(zhǔn)球重，而m+1到m+n號球要么是標(biāo)準(zhǔn)球，要么比標(biāo)
準(zhǔn)球輕；我們還知道其中有一個是壞球（但不知輕重）。換句話說，
我們知道真實的情況是以下m+n種布局之一：
1. 1號是壞球，且較重；
2. 2號是壞球，且較重；
……
m. m號是壞球，且較重；
m+1. m+1號是壞球，且較輕；
m+2. m+2號是壞球，且較輕；
……
m+n. m+n號是壞球，且較輕。
有一種特殊的情況是m=0或n=0，也就是說壞球的是輕還是重已經(jīng)知，常
常被用來單獨(dú)作為智力題。

結(jié)論1：
1)在以上條件成立的情況下，要保證在m+n個球中找出壞球并知道
其輕重，至少需要稱{log3(m+n)}次。
2)如果m和n不同時為1，那么稱{log3(m+n)}次就足夠了。如果
m=n=1，并且另有一標(biāo)準(zhǔn)球，那么稱{log3(m+n)}={log3(1+1)}=1
次也足夠了。

這里log3表示以3為底的對數(shù)。

需要對2)作點(diǎn)說明。如果m=n=1而沒有標(biāo)準(zhǔn)球的話，那么是永遠(yuǎn)也
稱不出壞球來的。把兩個球一邊一個放在天平上，必然是1號重2號輕。
但是由于沒有標(biāo)準(zhǔn)球，我們無法知道是壞球比較重所以1號是壞的，還
是壞球比較輕所以2號是壞的。如果有標(biāo)準(zhǔn)球，只要把1號球和標(biāo)準(zhǔn)球
比較一下。如果天平不平衡，那么1號球是壞球，且比較重；如果天平
平衡，那么2號球是壞球，且比較輕。策略樹如下：（用s表示標(biāo)準(zhǔn)球）

|--右--( )
|
|
(1; s)|--平--(2輕)
|
|
|--左--(1重)

現(xiàn)在來證明1)。在上面我們看到，可能的布局是m+n種（1重，2重，
……，m重，m+1輕，m+2輕，……，m+n輕）。假設(shè)我們已經(jīng)有一個策
略能保證在這m+n個球中找出壞球并知道其輕重，那么每一個布局都要
通向策略樹上的不同葉子，這棵策略樹至少需要有m+n片葉子。但是一
棵高度為H的三分樹最多只能有3H片葉子。于是這棵策略樹必須滿足條
件
3H ≥ m+n
也就是
H ≥ log3(m+n)
考慮到H是整數(shù)，我們就證明了
H ≥ {log3(m+n)}

現(xiàn)在我們要具體找到一棵高度為{log3(m+n)}的策略樹，使得m+n
種布局通向它的不同葉子。我們對k=m+n使用數(shù)學(xué)歸納法。

首先k=1。那么稱都不要稱，因為必有一壞球，那么壞球就是唯一
的1號球。如果是m=1，n=0，那么1號球比較重；如果是m=0，n=1，那
么1號球比較輕。需要的稱量次數(shù)為{log3(1)}=0。

對于k=2。m=1，n=1的情況已經(jīng)討論過了?？紤]m=2，n=0。這時我
們知道壞球比較重。只要把1號球和2號球放在天平兩邊一稱，哪個比較
重哪個就是壞球。策略樹如下：

|--右--(2重)
|
|
(1; 2)|--平--( )
|
|
|--左--(1重)

m=0，n=2的情況完全類似。

假設(shè)對于m+n＜k的情況我們都可以用{log3(k)}次稱出壞球?？紤]
m+n=k的情況。我們把1到m號球稱為第一組球，m+1到n號球稱為第二組
球。

設(shè)H={log3(m+n)}＝{log3(k)}。那么我們有
3H-1 ＜ k ≤ 3H
3H-2 ＜ k/3 ≤ 3H-1
3H-2 ＜ {k/3} ≤ 3H-1
于是
{log3{k/3}}=H-1。

現(xiàn)在我們把這k個球分為三堆，第一堆和第二堆分別有{k/3}個球，
并且這兩堆中屬于第一組的球的數(shù)目一樣（于是屬于第二組的球的數(shù)
目也一樣），第三堆中有k-2{k/3}個球（也就是其余的球）。舉一個
例子，如果m=7，n=3，那么這三堆可以分成這樣：（當(dāng)然不是唯一的
分法）
第一堆：1，2，3，7 （屬于第一組的3個，第二組的1個）
第二堆：4，5，6，8 （屬于第一組的3個，第二組的1個）
第三堆：9，10

這樣的分堆總是可能的嗎？如果m或n是偶數(shù)，那就很簡單。比如
說假設(shè)m是偶數(shù)，有兩種可能性。如果m/2≥{k/3}，那么就從第一組球
中各取{k/3}個球作為第一和第二堆（這時在第一第二堆中只有第一組
的球）；如果m/2＜{k/3}，那么就把第一組球分為相同的m/2個球的兩
堆，再分別用{k/3}-m/2個第二組球去把它們補(bǔ)充成{k/3}個球的兩堆
（這時在第三堆中就只有第二組的球了）。很顯然這樣的分堆符合上
面的要求。

如果m和n都是奇數(shù)，事情就有點(diǎn)復(fù)雜。首先如果(m-1)/2≥{k/3}
的話，那么按上面的方法也很容易把球按要求分為三堆。但是如果
(m-1)/2＜{k/3}，我們就必須先從第一組中各拿出(m-1)/2個球放入第
一和第二堆，再從第二組中各拿出{k/3}-(m-1)/2個球?qū)⑺鼈冄a(bǔ)充到各
有{k/3}個球為止。這就需要從第二組中總共拿得出2({k/3}-(m-1)/2)
個球來。所以必須有
2({k/3}-(m-1)/2) ≤ n
即
2{k/3} ≤ (m-1)+n
2{k/3} ≤ k-1
這個不等式在k=3或k＞4時總是成立的，但是對k=4就不成立。所以我
們要對k=4且m，n都是奇數(shù)的情況作特殊處理。我們只需考慮m=3，n=1
這種情況。把1號球和2號球放在天平兩端，如果不平衡，那么較重的
那個是壞球；如果平衡，那么把1號球和3號球放在天平兩端，平衡則
4號球為壞球且較輕，不平衡則3號球為壞球且較重。策略樹如下：

|--右--(2重)
|
| |--右--(3重)
(1; 2)|--平--(1; 3)|--平--(4輕)
| |--左--( )
|
|--左--(1重)

m=1，n=3的情況完全類似。

于是現(xiàn)在我們就可以毫無障礙地假設(shè)，我們已經(jīng)將m+n=k個球分為
這樣的三堆：第一堆和第二堆分別有{k/3}個球，并且這兩堆中屬于第
一組的球的數(shù)目一樣（于是屬于第二組的球的數(shù)目也一樣），第三堆
中有k-2{k/3}個球（也就是其余的球）。

我們把第一堆球和第二堆球分別放在天平的左右兩端。如果平衡，
那就說明壞球在第三堆里，這樣我們就把問題歸結(jié)為一個k-2{k/3}個
球的問題；如果右邊比較重，那么我們得到結(jié)論：要么是壞球比較輕，
并且它在第一堆中的第二組球，也就是可能較輕的那些球中，要么是
壞球比較重，并且它在第二堆中的第一組球，也就是可能較重的那些
球中，下面它就歸結(jié)為一個{k/3}個球的問題了；如果是左邊比較重，
那么我們也完全類似地將問題歸結(jié)為一個{k/3}個球的問題。開始的策
略樹如下：（小球的編號作了適當(dāng)變化：假設(shè)1，2，……，s為第一堆
中的第一組球，1'，2'……，s'為第二堆中的第一組球，(s+1)，……
為第一堆中的第二組球，(s+1)'為為第二堆中的第二組球）

歸結(jié)為壞球在
|--右--(1',2',……,s',s+1,……)中
| 的問題（{k/3}個球）
|
|
(1,2,……,s,s+1,……; |
1',2',……,s',(s+1)',……)|--平--歸結(jié)為壞球在第三堆中的問題
| （k-2{k/3}個球）
|
| 歸結(jié)為壞球在
|--左--(1,2,……,s,(s+1)',……)中
的問題（{k/3}個球）

考慮到k-2{k/3}≤{k/3}，另外此次稱量后我們至少可以得到一個標(biāo)準(zhǔn)
球（如果不平衡，第三堆里的球均為標(biāo)準(zhǔn)球，否則第一第二堆里的球
均為標(biāo)準(zhǔn)球）。根據(jù)歸納假設(shè)，上面得到“左”、“平”、“右”三
種情況歸結(jié)后的問題都可以用{log3{k/3}}=H-1次的稱法來解決。所
以加上這第一次稱量，k個球只需{log3(k)}次稱量就可以找出壞球。

在這節(jié)的最后我們給出一個具體的例子：如果有27個球，其中有
一個壞球，而且已知第一堆1-14號球如果其中一個是壞球，那么它比
標(biāo)準(zhǔn)球重，第二堆15-27號球如果其中一個是壞球，那么它比標(biāo)準(zhǔn)球輕。
根據(jù)結(jié)果1，我們知道只要[log3(27)]=3次就可以找出壞球。

按照上面的稱法，首先將27個球分為三堆，第一第二堆的個數(shù)為
{27/3}=9個球，而且其中分別屬于第一和第二組的球的個數(shù)相同。于
是我們可以?。?
第一堆： 1-7，15-16
第二堆：8-14，17-18
第三堆：19-27
現(xiàn)在把第一和第二堆放在天平左右兩端，如果平衡，我們就歸結(jié)為在
19-27號9個球中其中有個較輕壞球的問題；如果右邊重，我們就歸結(jié)
為壞球在8-14，15-16中的問題；如果左邊重，我們就歸結(jié)為壞球在
1-7，17-18中的問題。這三種情況都是9個球的問題。

|--右--歸結(jié)為壞球在8-14，15-16中的問題
|
|
(1-7,15-16; |
8-14,17-18|--平--歸結(jié)為壞球在19-27中的問題
|
|
|
|--左--歸結(jié)為壞球在1-7，17-18中的問題

三種情況中我們只具體做一種：壞球在1-7，17-18中的問題。同
樣地我們將其分為三堆
第一堆：1-3
第二堆：4-6
第三堆：7，17-18
照上面類似地我們有策略樹

|--右--歸結(jié)為壞球在4-6中的問題
|
|
(1-3; 4-6)|--平--歸結(jié)為壞球在7，17-18中的問題
|
|
|--左--歸結(jié)為壞球在1-3中的問題

于是變成了3個球的問題，解決方法就很顯然了，我們把上面的策略樹
寫完整：

|--右--( 5重)
|--右--(4 ; 5)|--平--( 6重)
| |--左--( 4重)
|
| |--右--(17輕)
(1-3; 4-6)|--平--(17;18)|--平--( 7重)
| |--左--(18輕)
|
| |--右--( 2重)
|--左--(1 ; 2)|--平--( 3重)
|--左--( 1重)

類似地我們寫出壞球在8-14，15-16中的問題的策略樹：

|--右--(12重)
|--右--(11;12)|--平--(13重)
| |--左--(11重)
|
| |--右--(15輕)
(8-10;11-13)|--平--(15;

本文地址:http://www.mcys1996.com/scgf/101122.html.

聲明： 我們致力于保護(hù)作者版權(quán)，注重分享，被刊用文章因無法核實真實出處，未能及時與作者取得聯(lián)系，或有版權(quán)異議的，請聯(lián)系管理員，我們會立即處理，本站部分文字與圖片資源來自于網(wǎng)絡(luò)，轉(zhuǎn)載是出于傳遞更多信息之目的,若有來源標(biāo)注錯誤或侵犯了您的合法權(quán)益，請立即通知我們(管理員郵箱：douchuanxin@foxmail.com)，情況屬實，我們會第一時間予以刪除，并同時向您表示歉意,謝謝!

上一篇: 怨天怨地，不如好好努力！

下一篇: 目光的所在