放下無(wú)價(jià)值的砝碼

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

然而，一個(gè)與他暗中競(jìng)爭(zhēng)的同事，竟然將他以前工作中所出現(xiàn)的失誤全部羅列出來(lái)，遞交給了董事長(zhǎng)。

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

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

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

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

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

大師并沒(méi)有過(guò)多解釋，而是起身出去了一會(huì)兒。

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

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

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

中年男子疑惑地看著大師怪異的舉動(dòng)。

大師問(wèn)道：“那個(gè)陷害你的同事升職了嗎 ”

他搖了搖頭。

大師繼續(xù)問(wèn)：“那么，請(qǐng)你如實(shí)告訴我，你的那個(gè)同事所說(shuō)的事情是否真實(shí) ”

他思忖了一會(huì)兒，回答說(shuō)：“應(yīng)該有一半是事實(shí)吧?！?/p>

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

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

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

他又搖了搖頭，回答說(shuō)：“感情上還算過(guò)得去，至少我還有一個(gè)很乖很爭(zhēng)氣的女兒。”

大師問(wèn)：“也就是說(shuō)，即使另外一個(gè)女人再理解你，你暫時(shí)也不可能下定決心和她生活在一起，是嗎 ”

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

大師暢然大笑起來(lái)，又把另一個(gè)砝碼從橡皮圈兒上摘了下來(lái)。

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

聽(tīng)到這兒，中年男子才恍然大悟。

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

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

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

異調(diào)

說(shuō)明

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

一、問(wèn)題

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

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

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

將十二個(gè)球編號(hào)為1-12。

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

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

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

一個(gè)自然而然的問(wèn)題就是：對(duì)于給定的自然數(shù)N，我們?cè)趺磥?lái)解有
N個(gè)球的稱球問(wèn)題？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

首先k=1。那么稱都不要稱，因?yàn)楸赜幸粔那颍敲磯那蚓褪俏ㄒ?
的1號(hào)球。如果是m=1，n=0，那么1號(hào)球比較重；如果是m=0，n=1，那
么1號(hào)球比較輕。需要的稱量次數(shù)為{log3(1)}=0。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

類似地我們寫出壞球在8-14，15-16中的問(wèn)題的策略樹(shù)：

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

本文地址:http://www.soujuw.cn/scgf/101122.html.

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

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

下一篇: 目光的所在