中年男子在一家公司任職
，原本他有很大的希望被晉升為業(yè)務(wù)部主管。
然而
，一個與他暗中競爭的同事
，竟然將他以前工作中所出現(xiàn)的失誤全部羅列出來
，遞交給了董事長
。
于是，他升職的希望便在對方的嫉妒和攻擊下暫時擱淺
。
當(dāng)他把這一切告訴他的妻子后
，他的妻子卻一點都不理解，這令他十分沮喪
。
男子來到山上找到大師，希望幫忙解除內(nèi)心的痛苦
。
大師笑著問他：“在你身邊一定有另外一個女人理解你
，是嗎 ”
男子坦誠地點了點頭
。
大師并沒有過多解釋
，而是起身出去了一會兒。
回來時
，他手中多了一個細細的橡皮圈兒和兩個帶掛鉤的砝碼。
當(dāng)著男子的面
，大師把那兩個砝碼掛在了橡皮圈兒上面
。
那兩個砝碼的重量
，幾乎把橡皮圈兒繃緊到了極限
，如果稍一用力，就會有斷裂的可能
。
中年男子疑惑地看著大師怪異的舉動。
大師問道：“那個陷害你的同事升職了嗎 ”
他搖了搖頭
。
大師繼續(xù)問：“那么
，請你如實告訴我
，你的那個同事所說的事情是否真實 ”
他思忖了一會兒
，回答說：“應(yīng)該有一半是事實吧?div id="4qifd00" class="flower right">
！?/p>
聽了之后，大師就笑了
，說：“既然他也沒有升職
，而且還給你指出了那么多的不足，那么你不但不該仇視他
，還應(yīng)該感謝他
。如果你今后把自己出現(xiàn)失誤的地方全部做好，他還會說什么呢 ”
中年男子贊同地點了點頭
。大師隨手摘下一個砝碼，橡皮圈兒頓時彈回去大半
。
接著
，大師又問：“你的妻子雖然一時不理解你
，但是你們之間感情的裂痕已到了無可挽救的地步了嗎 ”
他又搖了搖頭
，回答說：“感情上還算過得去，至少我還有一個很乖很爭氣的女兒
。”
大師問：“也就是說
，即使另外一個女人再理解你
，你暫時也不可能下定決心和她生活在一起
，是嗎 ”
沉默了一會兒
，中年男子如實地點了點頭。
大師暢然大笑起來
，又把另一個砝碼從橡皮圈兒上摘了下來。
然后
，大師將那個恢復(fù)原狀的橡皮圈兒遞給了他
，并解釋道：“現(xiàn)在
，你已經(jīng)沒有一點兒負擔(dān)了
，又恢復(fù)了先前的彈性，你還是那個完整無缺的‘橡皮圈兒’呀
。”
聽到這兒
，中年男子才恍然大悟
。
是啊，只要摘下生活中那些缺少價值的砝碼
，我們的生命又會恢復(fù)先前的彈性！
有12枚硬幣,其中有一顆是假幣,和一架無砝碼和刻度的天平,稱3次,找出假幣并且算出比真幣重還?C
稱球問題——經(jīng)典智力題推而廣之三
異調(diào)
說明
這篇文章試圖給出稱球問題的一個一般
的和嚴格的解答
。正因為需要做到一般和嚴
格，就要考慮許多平時遇不到的特別情形
，
所以敘述比較繁瑣
。如果對讀者對嚴格的證
明沒有興趣，可以只閱讀介紹問題和約定記
號的第一
、第二節(jié)，以及第三節(jié)末尾27個球
的例子
，和第五節(jié)13個球和40個球的解法
。
事實上所有的技巧都已經(jīng)表現(xiàn)在這幾個例子
里了
。
一
、問題
稱球問題的經(jīng)典形式是這樣的：
“有十二個外表相同的球，其中有一個壞球
，它的重量和其它十
一個有輕微的（但是可以測量出來的）差別。現(xiàn)在有一架沒有砝碼的
很靈敏的天平
，問如何稱三次就保證找出那個壞球
，并知道它比標準
球重還是輕
?div id="jfovm50" class="index-wrap">！?
這可能是網(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號
，
則它比標準球輕
；如果是5號，則它比標準球重
。
第三次將1號放在左邊
，2號放在右邊
。
1.如果右重則1號是壞球且比標準球輕
；
2.如果平衡則5號是壞球且比標準球重；
3.這次不可能左重
。
2.如果平衡則壞球在被拿掉的2-4號，且比標準球輕
。
第三次將2號放在左邊
，3號放在右邊。
1.如果右重則2號是壞球且比標準球輕
；
2.如果平衡則4號是壞球且比標準球輕；
3.如果左重則3號是壞球且比標準球輕
。
3.如果左重則壞球在拿到左邊的6-8號
，且比標準球重
。
第三次將6號放在左邊
，7號放在右邊。
1.如果右重則7號是壞球且比標準球重
；
2.如果平衡則8號是壞球且比標準球重；
3.如果左重則6號是壞球且比標準球重
。
2.如果天平平衡
，則壞球在9-12號。
第二次將1-3號放在左邊
，9-11號放在右邊。
1.如果右重則壞球在9-11號且壞球較重
。
第三次將9號放在左邊
，10號放在右邊
。
1.如果右重則10號是壞球且比標準球重
；
2.如果平衡則11號是壞球且比標準球重；
3.如果左重則9號是壞球且比標準球重
。
2.如果平衡則壞球為12號
。
第三次將1號放在左邊，12號放在右邊
。
1.如果右重則12號是壞球且比標準球重
；
2.這次不可能平衡
；
3.如果左重則12號是壞球且比標準球輕。
3.如果左重則壞球在9-11號且壞球較輕
。
第三次將9號放在左邊
，10號放在右邊
。
1.如果右重則9號是壞球且比標準球輕
；
2.如果平衡則11號是壞球且比標準球輕；
3.如果左重則10號是壞球且比標準球輕
。
3.如果左重則壞球在1-8號
。
第二次將2-4號拿掉
，將6-8號從右邊移到左邊
，把9-11號放
在右邊。就是說
，把1,6,7,8放在左邊，5,9,10,11放在右邊
。
1.如果右重則壞球在拿到左邊的6-8號
，且比標準球輕
。
第三次將6號放在左邊
，7號放在右邊。
1.如果右重則6號是壞球且比標準球輕
；
2.如果平衡則8號是壞球且比標準球輕；
3.如果左重則7號是壞球且比標準球輕
。
2.如果平衡則壞球在被拿掉的2-4號
，且比標準球重。
第三次將2號放在左邊
，3號放在右邊。
1.如果右重則3號是壞球且比標準球重
；
2.如果平衡則4號是壞球且比標準球重
；
3.如果左重則2號是壞球且比標準球重。
3.如果左重則壞球在沒有被觸動的1,5號
。如果是1號
，
則它比標準球重；如果是5號
，則它比標準球輕。
第三次將1號放在左邊
，2號放在右邊
。
1.這次不可能右重
。
2.如果平衡則5號是壞球且比標準球輕
；
3.如果左重則1號是壞球且比標準球重；
夠麻煩的吧
。其實里面有許多情況是對稱的，比如第一次稱時的
右重和右輕
，只需考慮一種就可以了
，另一種完全可以比照執(zhí)行。我
把整個過程寫下來
，只是想嚇唬嚇唬大家。
稍微試一下
，就可以知道只稱兩次是不可能保證找到壞球的
。如
果給的是十三個球
，以上的解法也基本有效
，只是要有個小小的改動，
就是在這種情況下
，在第一第二次都平衡的時候，第三次還是有可能
平衡（就是上面的第2.2.2步）
，那么我們可以肯定壞球是13號球
，可
是我們沒法知道它到底是比標準球輕
，還是比標準球重
。如果給的是
十四個球，我們會發(fā)現(xiàn)無論如何也不可能只稱三次，就保證找出壞球
。
一個自然而然的問題就是：對于給定的自然數(shù)N，我們怎么來解有
N個球的稱球問題
？
在下面的討論中
，給定任一自然數(shù)N
，我們要解決以下問題：
⑴找出N球稱球問題所需的最小次數(shù)
，并證明以上所給的最小次數(shù)的確
是最小的；
⑵給出最小次數(shù)稱球的具體方法
；
⑶如果只要求找出壞球而不要求知道壞球的輕重，對N球稱球問題解決
以上兩個問題
；
還有一個我們并不是那么感興趣，但是作為副產(chǎn)品的問題是：
⑷如果除了所給的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號是壞球，且較重，其他球都正?div id="d48novz" class="flower left">
！焙汀?號是壞球
，
且較輕，其他球都正?div id="d48novz" class="flower left">
！边@樣的情況，稱為一種“布局”
，并記為：
(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ù)不相等的稱量。因為壞
球和標準球重量之間的差別很小
，小于標準球的重量
，所以當(dāng)天平兩
邊球數(shù)不一樣時
，天平一定向球比較多的那邊傾斜
。所以在進行這樣
一次稱量之前
，它的的結(jié)果就可以被預(yù)料到，它不能給我們帶來任何
新的信息
。事實上在看完本文以后大家就很容易明白，即使壞球和標
準球重量之間的差別很大，也不會影響本文的結(jié)論
。因為考慮這種情
況會使問題變麻煩
，而并不能帶來有趣的結(jié)果
，我們就省略對此的考
慮
。
現(xiàn)在我們看到，上面關(guān)于十二個球問題的解法
，其實就是由一系
列稱量組成的——可不是隨隨便便的組合，而是以這樣的形式構(gòu)成的：
稱量1
如果右重
，則
稱量3
……
如果平衡
，則
稱量2
……
如果左重，則
稱量4
……
省略號部分則又是差不多的“如果右重
，則……”等等。所以這就提
示我們用樹的形式來表示上面的解法：樹的根是第一次稱量
，它有三
個分支（即三棵子樹
，于是根有三個子節(jié)點），分別對應(yīng)著在這個稱
量下的右重
、平衡、左重三種情況
。在根的三個子節(jié)點上
，又分別有
相應(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é)點
的那些節(jié)點）部分
，我們標出了“能夠到達”這些節(jié)點的布局，也就
是說在進行每一節(jié)點上的稱量時
，這個布局所給的結(jié)果和通往相對應(yīng)
的葉子的道路上所標出的“右”、“平”和“左”相符合
。從這個圖
我們也可以清楚地看到
，根下的左分支和右分支是對稱的：只需要把
所有的“右”改成“左”
，“左”改成“右”，“輕”改成“重”
，
“重”改成“輕”
；節(jié)點(1-3; 9-11)下的左分支和右分支也有這個
特點。
（如果有朋友對樹理論感興趣
，可以參考隨便哪一本圖論或者離
散數(shù)學(xué)的書。在這里我們只用到樹理論里最基本的知識
，所用的名詞
和結(jié)論都是相當(dāng)直觀的
。所以如果你不知道樹理論，用不著特別去學(xué)
也可以看懂這里的論證
。）
所以給定一棵三分樹（就是說除了葉子以外其他的節(jié)點都有三個
子節(jié)點的樹）
，在每個不是葉子的節(jié)點上給定一個稱量，并且規(guī)定這
個節(jié)點下的三個分支（子樹）分別對應(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é)點數(shù)的最大值加一
。比如說上
面這個圖中，葉子A和根間有1個節(jié)點
，而葉子B和根間有2個節(jié)點，沒
有和根之間的節(jié)點數(shù)超過2的葉子
。所以它的高度是2+1=3
。前面十二
球解法策略樹的高度也是3。一棵沒有任何分支
，只有根節(jié)點的樹
，我
們定義它的高度是0。
顯然
，策略樹的高度就是實行這個策略所需要的稱量的次數(shù)
。我
們的目的
，就是找到一棵“好”的策略樹
，使得它的高度最小。
什么是“好”策略
？我們回過頭來再看十二球解法策略樹
。我們
說過
，葉子上的那些布局都是從根開始通向葉子的
。比如說布局(7重)，
它之所以在那片葉子上是因為按照這個策略
，三次稱量的結(jié)果是“右
左右”；又比如說布局(11重)
，它之所以在那片葉子上是因為按照這
個策略
，三次稱量的結(jié)果是“平右平”。如果兩個布局通向同一片葉
子
，那么就是說按照這個策略，三次稱量的結(jié)果是完全一樣的
，于是
我們就不能通過這個策略來把這兩種布局區(qū)分開來
。比如說在十三個
球的情況下，(13輕)和(13重)都通向和“平平平”相對應(yīng)的葉子
，這
兩個布局中13號球或者輕或者重，于是我們知道13號球一定是壞球
，
但是通過這個策略我們不可能知道它到底是輕還是重
。
所以對于標準的稱球問題（找出壞球并知其比標準球重或輕）的
“好”策略，就是那些能使不同的布局通向不同的葉子的策略
。
三、每個球都已知可能為輕或可能為重的情況
先引入一個記號：對于任意實數(shù)a
，我們用{a}表示大于等于a的最
小整數(shù)
，比如說{2.5}=3，{4}=4
；我們用[a]表示小于等于a的最大整
數(shù)
，比如說[2.5]=2，[4]=4
。
我們首先考慮這樣一種布局的集合
。假設(shè)m，n為兩個非負實數(shù)
，
不同時為0。在編號從1到m+n的m+n個球中
，我們知道1到m號球要么是
標準球
，要么比標準球重，而m+1到m+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)知，常
常被用來單獨作為智力題
。
結(jié)論1：
1)在以上條件成立的情況下，要保證在m+n個球中找出壞球并知道
其輕重
，至少需要稱{log3(m+n)}次。
2)如果m和n不同時為1
，那么稱{log3(m+n)}次就足夠了
。如果
m=n=1
，并且另有一標準球
，那么稱{log3(m+n)}={log3(1+1)}=1
次也足夠了
。
這里log3表示以3為底的對數(shù)。
需要對2)作點說明
。如果m=n=1而沒有標準球的話，那么是永遠也
稱不出壞球來的
。把兩個球一邊一個放在天平上
，必然是1號重2號輕。
但是由于沒有標準球
，我們無法知道是壞球比較重所以1號是壞的
，還
是壞球比較輕所以2號是壞的
。如果有標準球
，只要把1號球和標準球
比較一下。如果天平不平衡
，那么1號球是壞球，且比較重
；如果天平
平衡
，那么2號球是壞球，且比較輕
。策略樹如下：（用s表示標準球）
|--右--( )
|
|
(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)討論過了
?div id="d48novz" class="flower left">
？紤]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個第二組球去把它們補充成{k/3}個球的兩堆
（這時在第三堆中就只有第二組的球了）。很顯然這樣的分堆符合上
面的要求
。
如果m和n都是奇數(shù)
，事情就有點復(fù)雜
。首先如果(m-1)/2≥{k/3}
的話
，那么按上面的方法也很容易把球按要求分為三堆。但是如果
(m-1)/2＜{k/3}，我們就必須先從第一組中各拿出(m-1)/2個球放入第
一和第二堆
，再從第二組中各拿出{k/3}-(m-1)/2個球?qū)⑺鼈冄a充到各
有{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}，另外此次稱量后我們至少可以得到一個標準
球（如果不平衡
，第三堆里的球均為標準球
，否則第一第二堆里的球
均為標準球）。根據(jù)歸納假設(shè)
，上面得到“左”、“平”
、“右”三
種情況歸結(jié)后的問題都可以用{log3{k/3}}=H-1次的稱法來解決
。所
以加上這第一次稱量，k個球只需{log3(k)}次稱量就可以找出壞球
。
在這節(jié)的最后我們給出一個具體的例子：如果有27個球，其中有
一個壞球
，而且已知第一堆1-14號球如果其中一個是壞球
，那么它比
標準球重，第二堆15-27號球如果其中一個是壞球
，那么它比標準球輕
。
根據(jù)結(jié)果1
，我們知道只要[log3(27)]=3次就可以找出壞球
。
按照上面的稱法，首先將27個球分為三堆
，第一第二堆的個數(shù)為
{27/3}=9個球
，而且其中分別屬于第一和第二組的球的個數(shù)相同。于
是我們可以?div id="m50uktp" class="box-center"> 。?
第一堆： 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.
聲明： 我們致力于保護作者版權(quán)，注重分享，被刊用文章因無法核實真實出處，未能及時與作者取得聯(lián)系，或有版權(quán)異議的，請聯(lián)系管理員，我們會立即處理，本站部分文字與圖片資源來自于網(wǎng)絡(luò)，轉(zhuǎn)載是出于傳遞更多信息之目的,若有來源標注錯誤或侵犯了您的合法權(quán)益，請立即通知我們(管理員郵箱：douchuanxin@foxmail.com)，情況屬實，我們會第一時間予以刪除，并同時向您表示歉意,謝謝!
上一篇:
！" rel="prev">
怨天怨地，不如好好努力！
下一篇:
目光的所在
相關(guān)文章
，但你溫暖有光" onerror="nofind(this)" >
！.png" alt="非常在理的一段真實話