中年男子在一家公司任職,原本他有很大的希望被晉升為業(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ù)先前的彈性!
稱球問(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í)向您表示歉意,謝謝!
上一篇: 怨天怨地,不如好好努力!
下一篇: 目光的所在