稱球問題經典形式
稱球問題的經典形式是這樣的：
“有十二個外表相同的球，其中有一個壞球，它的重量和其它十
一個有輕微的（但是可以測量出來的）差別。現在有一架沒有砝碼的
很靈敏的天平，問如何稱三次就保證找出那個壞球，并知道它比標準
球重還是輕。”
這可能是網上被做過次數最多的一道智力題了。它的一種解法如
下：
將十二個球編號為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號是壞球且比標準球重；
夠麻煩的吧。其實里面有許多情況是對稱的，比如第一次稱時的
右重和右輕，只需考慮一種就可以了，另一種完全可以比照執行。我
把整個過程寫下來，只是想嚇唬嚇唬大家。
稍微試一下，就可以知道只稱兩次是不可能保證找到壞球的。如
果給的是十三個球，以上的解法也基本有效，只是要有個小小的改動，
就是在這種情況下，在第一第二次都平衡的時候，第三次還是有可能
平衡（就是上面的第2.2.2步），那么我們可以肯定壞球是13號球，可
是我們沒法知道它到底是比標準球輕，還是比標準球重。如果給的是
十四個球，我們會發現無論如何也不可能只稱三次，就保證找出壞球。
一個自然而然的問題就是：對于給定的自然數N，我們怎么來解有
N個球的稱球問題？
在下面的討論中，給定任一自然數N，我們要解決以下問題：
⑴找出N球稱球問題所需的最小次數，并證明以上所給的最小次數的確
是最小的；
⑵給出最小次數稱球的具體方法；
⑶如果只要求找出壞球而不要求知道壞球的輕重，對N球稱球問題解決
以上兩個問題；
還有一個我們并不是那么感興趣，但是作為副產品的問題是：
⑷如果除了所給的N個球外，另外還給一標準球，解決以上三個問題。
二、記號
我們先不忙著馬上著手解決上述問題。先得給出幾個定義，尤其
是，要給出比較簡單的符號和記法。大家看到上面給出的解法寫起來
實在麻煩——想象一下如果我們要用這種方法來描述稱40個或1000個
球的問題！
仍舊考慮十二個球的情況和上面舉的解法。在還沒有開始稱第一
次時，我們對這十二個球所知的信息就是其中有一或較輕，或較重的
壞球，所以以下24種情況都是可能的：
1. 1號是壞球，且較重；
2. 2號是壞球，且較重；
……
12. 12號是壞球，且較重；
13. 1號是壞球，且較輕；
14. 2號是壞球，且較輕；
……
24. 12號是壞球，且較輕。
沒有其他的可能性，比如說“1、2號都是壞球，且都較重”之類。當
我們按上面解法“先將1-4號放在左邊，5-8號放在右邊”稱過第一次
以后，假設結果是右重，稍微分析一下，就會知道上面的24種情況中，
現在只有8種是可能的，就是
1. 1號是壞球，且較輕；
2. 2號是壞球，且較輕；
3. 3號是壞球，且較輕；
4. 4號是壞球，且較輕；
5. 5號是壞球，且較重；
6. 6號是壞球，且較重；
7. 7號是壞球，且較重；
8. 8號是壞球，且較重。
我們把諸如“1號是壞球，且較重，其他球都正常”和“2號是壞球，
且較輕，其他球都正常”這樣的情況，稱為一種“布局”，并記為：
(1重) 和 (2輕)
我們把“先將1-4號放在左邊，5-8號放在右邊”這樣的步驟，稱為一
次“稱量”。我們把上面這次稱量記為
(1,2,3,4; 5,6,7,8)
或
(1-4; 5-8)
也就是在括號內寫出參加稱量的球的號碼，并且以分號分開放在左邊
和放在右邊的球號。在最一開始，我們有24種可能的布局，而在經過
一次稱量(1-4; 5-8)后，如果結果是右重，我們就剩下上述8種可能
的布局。我們的目的，就是要使用盡量少的稱量，而獲得唯一一種可
能的布局——這樣我們就知道哪個球是壞球，它是比較重還是比較輕。
這里我們注意到沒有必要去考慮兩邊球數不相等的稱量。因為壞
球和標準球重量之間的差別很小，小于標準球的重量，所以當天平兩
邊球數不一樣時，天平一定向球比較多的那邊傾斜。所以在進行這樣
一次稱量之前，它的的結果就可以被預料到，它不能給我們帶來任何
新的信息。事實上在看完本文以后大家就很容易明白，即使壞球和標
準球重量之間的差別很大，也不會影響本文的結論。因為考慮這種情
況會使問題變麻煩，而并不能帶來有趣的結果，我們就省略對此的考
慮。
現在我們看到，上面關于十二個球問題的解法，其實就是由一系
列稱量組成的——可不是隨隨便便的組合，而是以這樣的形式構成的：
稱量1
如果右重，則
稱量3
……
如果平衡，則
稱量2
……
如果左重，則
稱量4
……
省略號部分則又是差不多的“如果右重，則……”等等。所以這就提
示我們用樹的形式來表示上面的解法：樹的根是第一次稱量，它有三
個分支（即三棵子樹，于是根有三個子節點），分別對應著在這個稱
量下的右重、平衡、左重三種情況。在根的三個子節點上，又分別有
相應的稱量，和它們的三個分支……如果具體地寫出來，就是
|--右--( 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重)
（*：對應十三個球的情形。）
這里“右”、“平”和“左”分別表示稱量的結果為“右重”、“平
衡”和“左重”所對應的分支。在樹的葉子（就是最右邊沒有子節點
的那些節點）部分，我們標出了“能夠到達”這些節點的布局，也就
是說在進行每一節點上的稱量時，這個布局所給的結果和通往相對應
的葉子的道路上所標出的“右”、“平”和“左”相符合。從這個圖
我們也可以清楚地看到，根下的左分支和右分支是對稱的：只需要把
所有的“右”改成“左”，“左”改成“右”，“輕”改成“重”，
“重”改成“輕”；節點(1-3; 9-11)下的左分支和右分支也有這個
特點。
（如果有朋友對樹理論感興趣，可以參考隨便哪一本圖論或者離
散數學的書。在這里我們只用到樹理論里最基本的知識，所用的名詞
和結論都是相當直觀的。所以如果你不知道樹理論，用不著特別去學
也可以看懂這里的論證。）
所以給定一棵三分樹（就是說除了葉子以外其他的節點都有三個
子節點的樹），在每個不是葉子的節點上給定一個稱量，并且規定這
個節點下的三個分支（子樹）分別對應右重、平衡、左重的情況，我
們就得到了一種稱球的方法。我們把這樣一棵三分樹稱為一個“策略”
或一棵“策略樹”。你可以給出一個平凡的策略，比如說無論發生了
什么事總是把1號和2號球放在左右兩側來稱（在葉子上我們沒有寫出
相應的布局，用@來代替）：
|--右--@A
|--右--(1; 2)|--平--@
| |--左--@
|
| |--右--@
(1; 2)|--平--(1; 2)|--平--@
| |--左--@
|
| |--右--@B
| |--右--(1; 2)|--平--@
| | |--左--@
| |
| | |--右--@
|--左--(1; 2)|--平--(1; 2)|--平--@
| |--左--@
|
| |--右--@
|--左--(1; 2)|--平--@
|--左--@
當然這么個策略沒什么用場，只能讓我們知道1號球和2號球之間的輕
重關系。另外我們看到，每個分支不一定一樣長，上面這棵策略樹根
下面左分支就比較長。
一棵樹的高度是葉子到根之間的結點數的最大值加一。比如說上
面這個圖中，葉子A和根間有1個節點，而葉子B和根間有2個節點，沒
有和根之間的節點數超過2的葉子。所以它的高度是2+1=3。前面十二
球解法策略樹的高度也是3。一棵沒有任何分支，只有根節點的樹，我
們定義它的高度是0。
顯然，策略樹的高度就是實行這個策略所需要的稱量的次數。我
們的目的，就是找到一棵“好”的策略樹，使得它的高度最小。
什么是“好”策略？我們回過頭來再看十二球解法策略樹。我們
說過，葉子上的那些布局都是從根開始通向葉子的。比如說布局(7重)，
它之所以在那片葉子上是因為按照這個策略，三次稱量的結果是“右
左右”；又比如說布局(11重)，它之所以在那片葉子上是因為按照這
個策略，三次稱量的結果是“平右平”。如果兩個布局通向同一片葉
子，那么就是說按照這個策略，三次稱量的結果是完全一樣的，于是
我們就不能通過這個策略來把這兩種布局區分開來。比如說在十三個
球的情況下，(13輕)和(13重)都通向和“平平平”相對應的葉子，這
兩個布局中13號球或者輕或者重，于是我們知道13號球一定是壞球，
但是通過這個策略我們不可能知道它到底是輕還是重。
所以對于標準的稱球問題（找出壞球并知其比標準球重或輕）的
“好”策略，就是那些能使不同的布局通向不同的葉子的策略。
三、每個球都已知可能為輕或可能為重的情況
先引入一個記號：對于任意實數a，我們用{a}表示大于等于a的最
小整數，比如說{2.5}=3，{4}=4；我們用[a]表示小于等于a的最大整
數，比如說[2.5]=2，[4]=4。
我們首先考慮這樣一種布局的集合。假設m，n為兩個非負實數，
不同時為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，也就是說壞球的是輕還是重已經知，常
常被用來單獨作為智力題。
結論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為底的對數。
需要對2)作點說明。如果m=n=1而沒有標準球的話，那么是永遠也
稱不出壞球來的。把兩個球一邊一個放在天平上，必然是1號重2號輕。
但是由于沒有標準球，我們無法知道是壞球比較重所以1號是壞的，還
是壞球比較輕所以2號是壞的。如果有標準球，只要把1號球和標準球
比較一下。如果天平不平衡，那么1號球是壞球，且比較重；如果天平
平衡，那么2號球是壞球，且比較輕。策略樹如下：（用s表示標準球）
|--右--( )
|
|
(1; s)|--平--(2輕)
|
|
|--左--(1重)
現在來證明1)。在上面我們看到，可能的布局是m+n種（1重，2重，
……，m重，m+1輕，m+2輕，……，m+n輕）。假設我們已經有一個策
略能保證在這m+n個球中找出壞球并知道其輕重，那么每一個布局都要
通向策略樹上的不同葉子，這棵策略樹至少需要有m+n片葉子。但是一
棵高度為H的三分樹最多只能有3H片葉子。于是這棵策略樹必須滿足條
件
3H ≥ m+n
也就是
H ≥ log3(m+n)
考慮到H是整數，我們就證明了
H ≥ {log3(m+n)}
現在我們要具體找到一棵高度為{log3(m+n)}的策略樹，使得m+n
種布局通向它的不同葉子。我們對k=m+n使用數學歸納法。
首先k=1。那么稱都不要稱，因為必有一壞球，那么壞球就是唯一
的1號球。如果是m=1，n=0，那么1號球比較重；如果是m=0，n=1，那
么1號球比較輕。需要的稱量次數為{log3(1)}=0。
對于k=2。m=1，n=1的情況已經討論過了。考慮m=2，n=0。這時我
們知道壞球比較重。只要把1號球和2號球放在天平兩邊一稱，哪個比較
重哪個就是壞球。策略樹如下：
|--右--(2重)
|
|
(1; 2)|--平--( )
|
|
|--左--(1重)
m=0，n=2的情況完全類似。
假設對于m+n＜k的情況我們都可以用{log3(k)}次稱出壞球。考慮
m+n=k的情況。我們把1到m號球稱為第一組球，m+1到n號球稱為第二組
球。
設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。
現在我們把這k個球分為三堆，第一堆和第二堆分別有{k/3}個球，
并且這兩堆中屬于第一組的球的數目一樣（于是屬于第二組的球的數
目也一樣），第三堆中有k-2{k/3}個球（也就是其余的球）。舉一個
例子，如果m=7，n=3，那么這三堆可以分成這樣：（當然不是唯一的
分法）
第一堆：1，2，3，7 （屬于第一組的3個，第二組的1個）
第二堆：4，5，6，8 （屬于第一組的3個，第二組的1個）
第三堆：9，10
這樣的分堆總是可能的嗎？如果m或n是偶數，那就很簡單。比如
說假設m是偶數，有兩種可能性。如果m/2≥{k/3}，那么就從第一組球
中各取{k/3}個球作為第一和第二堆（這時在第一第二堆中只有第一組
的球）；如果m/2＜{k/3}，那么就把第一組球分為相同的m/2個球的兩
堆，再分別用{k/3}-m/2個第二組球去把它們補充成{k/3}個球的兩堆
（這時在第三堆中就只有第二組的球了）。很顯然這樣的分堆符合上
面的要求。
如果m和n都是奇數，事情就有點復雜。首先如果(m-1)/2≥{k/3}
的話，那么按上面的方法也很容易把球按要求分為三堆。但是如果
(m-1)/2＜{k/3}，我們就必須先從第一組中各拿出(m-1)/2個球放入第
一和第二堆，再從第二組中各拿出{k/3}-(m-1)/2個球將它們補充到各
有{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都是奇數的情況作特殊處理。我們只需考慮m=3，n=1
這種情況。把1號球和2號球放在天平兩端，如果不平衡，那么較重的
那個是壞球；如果平衡，那么把1號球和3號球放在天平兩端，平衡則
4號球為壞球且較輕，不平衡則3號球為壞球且較重。策略樹如下：
|--右--(2重)
|
| |--右--(3重)
(1; 2)|--平--(1; 3)|--平--(4輕)
| |--左--( )
|
|--左--(1重)
m=1，n=3的情況完全類似。
于是現在我們就可以毫無障礙地假設，我們已經將m+n=k個球分為
這樣的三堆：第一堆和第二堆分別有{k/3}個球，并且這兩堆中屬于第
一組的球的數目一樣（于是屬于第二組的球的數目也一樣），第三堆
中有k-2{k/3}個球（也就是其余的球）。
我們把第一堆球和第二堆球分別放在天平的左右兩端。如果平衡，
那就說明壞球在第三堆里，這樣我們就把問題歸結為一個k-2{k/3}個
球的問題；如果右邊比較重，那么我們得到結論：要么是壞球比較輕，
并且它在第一堆中的第二組球，也就是可能較輕的那些球中，要么是
壞球比較重，并且它在第二堆中的第一組球，也就是可能較重的那些
球中，下面它就歸結為一個{k/3}個球的問題了；如果是左邊比較重，
那么我們也完全類似地將問題歸結為一個{k/3}個球的問題。開始的策
略樹如下：（小球的編號作了適當變化：假設1，2，……，s為第一堆
中的第一組球，1'，2'……，s'為第二堆中的第一組球，(s+1)，……
為第一堆中的第二組球，(s+1)'為為第二堆中的第二組球）
歸結為壞球在
|--右--(1',2',……,s',s+1,……)中
| 的問題（{k/3}個球）
|
|
(1,2,……,s,s+1,……; |
1',2',……,s',(s+1)',……)|--平--歸結為壞球在第三堆中的問題
| （k-2{k/3}個球）
|
| 歸結為壞球在
|--左--(1,2,……,s,(s+1)',……)中
的問題（{k/3}個球）
考慮到k-2{k/3}≤{k/3}，另外此次稱量后我們至少可以得到一個標準
球（如果不平衡，第三堆里的球均為標準球，否則第一第二堆里的球
均為標準球）。根據歸納假設，上面得到“左”、“平”、“右”三
種情況歸結后的問題都可以用{log3{k/3}}=H-1次的稱法來解決。所
以加上這第一次稱量，k個球只需{log3(k)}次稱量就可以找出壞球。
在這節的最后我們給出一個具體的例子：如果有27個球，其中有
一個壞球，而且已知第一堆1-14號球如果其中一個是壞球，那么它比
標準球重，第二堆15-27號球如果其中一個是壞球，那么它比標準球輕。
根據結果1，我們知道只要[log3(27)]=3次就可以找出壞球。
按照上面的稱法，首先將27個球分為三堆，第一第二堆的個數為
{27/3}=9個球，而且其中分別屬于第一和第二組的球的個數相同。于
是我們可以取：
第一堆： 1-7，15-16
第二堆：8-14，17-18
第三堆：19-27
現在把第一和第二堆放在天平左右兩端，如果平衡，我們就歸結為在
19-27號9個球中其中有個較輕壞球的問題；如果右邊重，我們就歸結
為壞球在8-14，15-16中的問題；如果左邊重，我們就歸結為壞球在
1-7，17-18中的問題。這三種情況都是9個球的問題。
|--右--歸結為壞球在8-14，15-16中的問題
|
|
(1-7,15-16; |
8-14,17-18|--平--歸結為壞球在19-27中的問題
|
|
|
|--左--歸結為壞球在1-7，17-18中的問題
三種情況中我們只具體做一種：壞球在1-7，17-18中的問題。同
樣地我們將其分為三堆
第一堆：1-3
第二堆：4-6
第三堆：7，17-18
照上面類似地我們有策略樹
|--右--歸結為壞球在4-6中的問題
|
|
(1-3; 4-6)|--平--歸結為壞球在7，17-18中的問題
|
|
|--左--歸結為壞球在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;16)|--平--(14重)
| |--左--(16輕)
|
| |--右--( 9重)
|--左--(8 ; 9)|--平--(10重)
|--左--( 8重)
和壞球在19-27中的問題的策略樹：
|--右--(19輕)
|--右--(19;20)|--平--(21輕)
| |--左--(20輕)
|
| |--右--(25輕)
(19-21;22-24)|--平--(25;26)|--平--(27輕)
| |--左--(26輕)
|
| |--右--(22輕)
|--左--(22;23)|--平--(24輕)
|--左--(23輕)
于是最終將此三棵策略樹拼起來的到最終解法：
|--右--(12重)
|--右--(11;12)|--平--(13重)
| |--左--(11重)
|
| |--右--(15輕)
|--右--(8-10; |--平--(15;16)|--平--(14重)
| 11-13)| |--左--(16輕)
| |
| | |--右--( 9重)
| |--左--(8 ; 9)|--平--(10重)
| |--左--( 8重)
|
| |--右--(19輕)
| |--右--(19;20)|--平--(21輕)
| | |--左--(20輕)
| |
| | |--右--(25輕)
(1-7,15-16; |--平--(19-21;|--平--(25;26)|--平--(27輕)
8-14,17-18)| 22-24)| |--左--(26輕)
| |
| | |--右--(22輕)
| |--左--(22;23)|--平--(24輕)
| |--左--(23輕)
|
| |--右--( 5重)
| |--右--(4 ; 5)|--平--( 6重)
| | |--左--( 4重)
| |
| | |--右--(17輕)
|--左--(1-3; |--平--(17;18)|--平--( 7重)
4-6)| |--左--(18輕)
|
| |--右--( 2重)
|--左--(1 ; 2)|--平--( 3重)
|--左--( 1重)
對一棵策略樹正確性的驗證比較容易（雖然比較煩）。首先檢查
是否所有的布局都在某片葉子上了；其次就是檢驗每個布局經過樹中
的每個節點的流向是否正確，就是說用此節點上的稱量方法，它所屬
的左中右分支符合實際。
四、問題的解答
現在我們就可以來回答第一節中的問題了。
結論2：現有N個小球，其中有一個壞球不知比標準球輕還是重。
我們令H={log3(2N)}。
1)要保證在N個球中找出壞球并知道其輕重，至少需要稱H次。
假設N≠2，我們有
2)如果N＜(3H-1)/2，那么稱H次就足夠了；
3)如果N=(3H-1)/2，那么稱H次足以保證找到壞球，但不足以保
證知道壞球比標準球輕還是重；
4)如果N=(3H-1)/2，而且還另有一個標準球，那么稱H次足以保
證找到壞球和知道，知道壞球比標準球輕還是重。
假設N=2，我們有
5)如果還另有一個標準球，稱H={log3(2*2)}=2次足以保證找到
壞球和知道壞球比標準球輕還是重。
5)看起來有點奇怪，不過這其實很顯然。如果有超過兩個球，我
們知道壞球是“獨一無二”的那一個，總找得出來；但是如果只有兩
個球，一個好球一個壞球，都是“獨一無二”的，如果沒有一個標準
球的話，我們無論如何不可能知道哪個才是好的。
首先假設結論成立，我們來看看幾個具體例子。如果是12個球，
那么
H = {log3(2*12)} = 3，
而且
12 ＜ (33-1)/2 = 13。
所以根據2)我們知道稱3次可以找出壞球并知其輕重。如果是13個球，
那么
H={log3(2*13)}=3，
而且
(33-1)/2=13。
根據3)我們知道稱3次可以找出壞球但不一定能知其輕重。但是如果另
有一個標準球的話，稱3次就可找出壞球且知其輕重。
一般地，能由H次稱量找出壞球并知道其輕重的最大小球數量為
(3H-1)/2-1 = (3H-3)/2；
能由H次稱量找出壞球但不需要知道其輕重的最大小球數量為
(3H-1)/2；
有一標準球，能由H次稱量找出壞球并知道其輕重的最大小球數量也為
(3H-1)/2。
為了比如說為了找出壞球并知道其輕重，則3次最多可以稱12個，4次
為39個，5次為120個，6次為363個等等；為了找出壞球卻不需知道其
輕重，則3次最多可以稱13個，4次為40個，5次121個，6次364個等等
——但是如果另有一個標準球，那么就可以用相同的次數來知道壞球
的輕重。
首先我們證明至少需要稱{log3(2N)}次。這和上節類似問題的證
明幾乎相同。我們看到，N個小球可能的布局是2N種（1重，2重，……，
N重，1輕，2輕，……，N輕）。所以相應策略樹至少需要有2N片葉子。
但是一棵高度為H的三分樹最多只能有3H片葉子。于是這棵策略樹必
須滿足條件
H ≥ {log3(2N)}。
現在我們來證明3)的后半部分：如果N=(3H-1)/2，那么稱H次還
是不足以保證知道壞球比標準球輕還是重。
我們知道第一步稱量一定是各放n（這里2n≤N）個球在天平兩端，
然后看天平的狀況再決定后面的步驟。此時有三種情況
1)如果天平平衡，那么壞球就在剩下的N-2n個球里。這時候根據1)，
我們還需要{log3(2(N-2n))}次來找到壞球并知其輕重；
2)如果是左邊重，則要么是壞球比較輕，而且壞球在右面n個球里，
要么是壞球比較重，而且壞球在左面n個球里。這時根據結論1，我
們還要{log3(2n))}次來找到壞球并知其輕重；
3)如果是右邊重，那么有和上面類似的結論，我們還要{log3(2n))}
次來找到壞球并知其輕重。
如果我們在H次里可以稱出壞球并知其輕重，那么我們必然要有
{log3(2(N-2n))} ≤ H-1 和 {log3(2n))} ≤ H-1
但前一個式子表明
2(N-2n) ≤ 3H-1
也就是
2((3H-1)/2-2n) ≤ 3H-1
所以
3H-1 ≤ 2n+1/2
考慮到3H-1為整數，于是
3H-1 ≤ 2n
但3H-1又是奇數，而2n是偶數，所以
3H-1 ＜ 2n。 (*)
而后一個式子表明
2n ≤ 3H-1
同樣考慮到奇偶性
2n ＜ 3H-1。 (**)
我們看到(*)和(**)式是矛盾的。
所以對N=(3H-1)/2的情況，只用H步是不能夠稱出壞球又知道它
的輕重的。它的原因在于，雖然理論上N=(3H-1)/2，那么可能的布局
是(3H-1)種，而一棵H層的策略樹有3H片葉子，看起來葉子足夠多了。
但是由于第一步的稱量無論如何也不可能把這3H-1種布局平均地分配
在左中右三棵子策略樹上，總有一個分支上承受的布局會超過3H-1種，
于是在此分支上就無法用剩下的H-1次稱量來稱出壞球又知道它的輕
重。
接下來我們同時證明結論2中的2)、4)和5)。也就是說，我們要具
體找到一種策略，如果N＜(3H-1)/2，那么不用標準球在H次內找到壞
球又知道它的輕重的；如果N=(3H-1)/2或者N=2，則允許使用一個標
準球來達到同樣目的。仍舊使用數學歸納法。
首先對N=1，{log3(2N)}=1且N=(31-1)/2，允許使用標準球。因
為只有一個球，而題目的條件是有一個壞球，所以這唯一的一個就是
壞球，現在只需要知道它比標準球重還是輕。這只要把標準球和這個
小球在天平上比較一次就可以了，策略樹如下（我們用s表示標準球）：
|--右--(1輕)
(1; s)|--平--( )
|--左--(1重)
對N=2和N=3，{log3(2N)}=2。我們給出下面高度為2的策略樹，
很容易驗證其正確性。
N=2，允許使用標準球：
|--右--(1輕)
| |--右--(2輕)
(1; s)|--平--(2; s)|--平--( )
| |--左--(2重)
|--左--(1重)
N=3：
|--右--(1輕)
|--右--(1; 3)|--平--(2重)
| |--左--( )
|
| |--右--(3輕)
(1; 2)|--平--(1; 3)|--平--( )
| |--左--(3重)
|
| |--右--( )
|--左--(1; 3)|--平--(2輕)
|--左--(1重)
現在假設對小于N的情況，稱法都已經找到。考慮N（現在假定N>3）
個小球的情況。仍記H={log3(2N)}。
首先如果N＜(3H-1)/2，我們把N個球分成三堆：第一堆和第二堆
中分別有{N/3}個球，第三堆中為剩下的球，有N-2{N/3}個。我們把第
一和第二堆小球放在天平左右端進行第一次稱量。
三種情況：
如果天平平衡，那么壞球在第三堆的N-2{N/3}個里，問題歸結為
N-2{N/3}個小球，稱H-1次，而且此時我們可以隨便從第一或第二堆里
拿出一個球來作標準球。但是
N-2{N/3} ≤ 3{N/3}-2{N/3} = {N/3}
但由N＜(3H-1)/2有
N ≤ (3H-1)/2-1 = (3H-3)/2
所以
N/3 ≤ (3H-1-1)/2
右邊一定是一個整數，所以我們最終得到
N-2{N/3} ≤ {N/3} ≤ (3H-1-1)/2。
根據歸納假設，在有標準球的情況下，N-2{N/3}個球的問題可被H-1次
的稱量解決。
如果左邊重，則要么是壞球比較輕，而且壞球在右面{N/3}個球里；
要么是壞球比較重，而且壞球在左面{N/3}個球里。這時根據結論1，我
們還要{log3(2{N/3}))}次來找到壞球并知其輕重。和上面的計算完全
一樣，
N/3 ≤ (3H-1-1)/2
于是
2{N/3} ≤ 3H-1-1
{log3(2{N/3}))} ≤ H-1
所以仍舊可以用剩下的H-1次稱量解決問題。
如果右邊重，完全類似于左邊重的情況。
現在考慮N=(3H-1)/2的情況，這時允許用一個標準球。我們可以
把球分成三堆。第一堆為(3H-1+1)/2個，第二堆為(3H-1-1)/2個
再加上標準球，所以第二堆一共也是(3H-1+1)/2個球，第三堆是剩
下的
(3H-1)/2-(3H-1+1)/2-(3H-1-1)/2 = (3H-1-1)/2
個球。我們把第一和第二堆小球放在天平左右端進行第一次稱量。
三種情況：
如果天平平衡，那么壞球在第三堆的(3H-1-1)/2個里。根據歸
納假設，在有標準球的情況下，這可被H-1次稱量解決。
如果左邊重，則要么是壞球比較輕，而且壞球在右面(3H-1+1)/2
個球里；要么是壞球比較重，而且壞球在左面除了附加的標準球以外
的(3H-1-1)/2個球里。這時根據結論1，我們還要
{log3(3H-1+1)/2+(3H-1-1)/2)} = H-1
次來找到壞球并知其輕重。所以這也可以用剩下的H-1次稱量來解決問
題。
如果右邊重，完全類似于左邊重的情況。
這就完全證明了結論2中的2)、4)和5)。剩下的就是3)的前半部分：
如果N=(3H-1)/2，那么稱H次足以保證找到壞球（但可能不知道輕重）。
這很簡單，如果我們拿掉一個球，那么根據2)，一定能用H次稱量
來找到壞球并且知道輕重——唯一的例外是，如果被拿掉的那個恰好
就是壞球——那么這時候所有稱量的結果都是天平保持平衡。如果發
生了這樣的事，所有稱量的結果都是天平保持平衡，我們就可以斷定
壞球就是那個被拿掉的球，當然這時這個球從來沒有上過天平，我們
絕無可能知道它是比標準球重，還是比標準球輕。
五、四十個球的例子
最后我們來解決一下40個球，沒有標準球的問題。我們知道
40 = (34-1)/2
所以我們可以稱4次找出壞球，但是因為沒有標準球，就不一定能知道
壞球的輕重。
順便先考慮13個球，另有一標準球的問題。
13 = (33-1)/2
所以稱3次可以找出壞球，因為有標準球，我們還可以同時知道壞球的
輕重。
根據上一節的證明過程，這時我們要把這13個球分為3堆：
第一堆：1-5
第二堆：6-9，再加上標準球s
第三堆：10-13
我們把第一和第二堆小球放在天平左右端進行第一次稱量。
如果是左邊重，那么要么是第一堆1-5號球中有一個是壞球，而且
它比標準球重，要么是第二堆6-9號球中有一個是壞球，那么它比標準
球輕。用結論1來解決的問題，第三節末尾我們處理過27個球的問題，
9個球的問題就是小菜了：
|--右--( 4重)
|--右--(3 ; 4)|--平--( 6輕)
| |--左--( 3重)
|
| |--右--( 8輕)
(1-2,6;3-4,7)|--平--(8 ; 9)|--平--( 5重)
| |--左--( 9輕)
|
| |--右--( 2重)
|--左--(1 ; 2)|--平--( 7輕)
|--左--( 1重)
如果是右邊重，那么和上面的情況對稱，只要把策略樹中的“左”
和“右”互換，“輕”和“重”互換即可。
如果平衡，那么就化為4個球（10-13號）有一個標準球2次稱出的
問題。雖然還可以往下照葫蘆畫瓢地遞歸一次，不過4個球的情況就太
簡單了，所以直接寫出策略樹：
|--右--(10輕)
|--右--(10;11)|--平--(12重)
| |--左--(11輕)
|
| |--右--(13輕)
(10,11;12,s)|--平--(13; s)|--平--( )
| |--左--(13重)
|
| |--右--(11重)
|--左--(10;11)|--平--(12輕)
|--左--(10重)
把左中右三個分支拼起來我們就得到13個球有一標準球稱3次的策
略樹：
|--右--( 1輕)
|--右--(1 ; 2)|--平--( 7重)
| |--左--( 2輕)
|
| |--右--( 9重)
|--右--(1-2,6;|--平--(8 ; 9)|--平--( 5輕)
| 3-4,7)| |--左--( 8重)
| |
| | |--右--( 3輕)
| |--左--(3 ; 4)|--平--( 6重)
| |--左--( 4輕)
|
| |--右--(10輕)
| |--右--(10;11)|--平--(12重)
| | |--左--(11輕)
| |
| | |--右--(13輕)
(1-5; |--平--(10,11;|--平--(13; s)|--平--( )
6-9,s)| 12,s)| |--左--(13重)
| |
| | |--右--(11重)
| |--左--(10;11)|--平--(12輕)
| |--左--(10重)
|
| |--右--( 4重)
| |--右--(3 ; 4)|--平--( 6輕)
| | |--左--( 3重)
| |
| | |--右--( 8輕)
|--左--(1-2,6;|--平--(8 ; 9)|--平--( 5重)
3-4,7)| |--左--( 9輕)
|
| |--右--( 2重)
|--左--(1 ; 2)|--平--( 7輕)
|--左--( 1重)
現在可以考慮40個球，無標準球的問題了。根據上一節的證明過
程，我們首先拿掉第40號球，使之變為39個球的問題。然后我們把這
39個球分為3堆：
第一堆：1-13
第二堆：14-26
第三堆：27-39
把第一和第二堆小球放在天平左右端進行第一次稱量。
如果是右邊重，那么要么是第一堆1-14號球中有一個是壞球，而
且它比標準球重，要么是第二堆15-27號球中有一個是壞球，那么它比
標準球輕。這恰好是第三節末尾我們解決過的例子！這個策略樹分支
我們可以完全拷貝過來。
如果是左邊重，那么和上面的情況對稱，只要把策略樹中的“左”
和“右”互換，“輕”和“重”互換即可。
如果平衡，那么問題轉化為本節開始的13個球，有一標準球的問
題（可取1號球為標準球），上面的策略樹也可拷貝過來，只是要把原
來的1-13號球和這里的27-39號球一一對應（只要把所有的號碼加26即
可）。
把左中右三個策略分支合并起來，并考慮到如果所有稱量結果都
是平衡的話，則第40號球為壞球的結論。我們就得到了下面的關于稱
40個球的巨無霸策略樹，它有81片葉子：
|--右--( 1輕)
|--右--(1 ; 2)|--平--( 3輕)
| |--左--( 2輕)
|
| |--右--(18重)
|--右--(1-3; |--平--(17;18)|--平--( 7輕)
| 4-6)| |--左--(17重)
| |
| | |--右--( 4輕)
| |--左--(4 ; 5)|--平--( 6輕)
| |--左--( 5輕)
|
| |--右--(23重)
| |--右--(22;23)|--平--(24重)
| | |--左--(22重)
| |
| | |--右--(26重)
|--右--(1-7, |--平--(19-21;|--平--(25;26)|--平--(27重)
| 15-16;| 22-24)| |--左--(25重)
| 8-14,| |
| 17-18)| | |--右--(20重)
| | |--左--(19;20)|--平--(21重)
| | |--左--(19重)
| |
| | |--右--( 8輕)
| | |--右--(8 ; 9)|--平--(10輕)
| | | |--左--( 9輕)
| | |
| | | |--右--(16重)
| |--左--(8-10; |--平--(15;16)|--平--(14輕)
| 11-13)| |--左--(15重)
| |
| | |--右--(11輕)
| |--左--(11;12)|--平--(13輕)
| |--左--(12輕)
|
| |--右--(27輕)
| |--右--(27;28)|--平--(33重)
| | |--左--(28輕)
| |
| | |--右--(35重)
| |--右--(27-28,|--平--(34;35)|--平--(31輕)
| | 32;| |--左--(34重)
| | 29-30,|
| | 33)| |--右--(29輕)
| | |--左--(29;30)|--平--(32重)
| | |--左--(30輕)
| |
| | |--右--(36輕)
| | |--右--(36;37)|--平--(38重)
| | | |--左--(37輕)
| | |
| | | |--右--(39輕)
(1-13;|--平--(27-31;|--平--(36,37;|--平--(39; 1)|--平--(40壞)
14-26)| 32-35,1)| 38,1)| |--左--(39重)
| | |
| | | |--右--(37重)
| | |--左--(36;37)|--平--(38輕)
| | |--左--(36重)
| |
| | |--右--(30重)
| | |--右--(29;30)|--平--(32輕)
| | | |--左--(29重)
| | |
| | | |--右--(34輕)
| |--左--(27-28,|--平--(34;35)|--平--(31重)
| 32;| |--左--(35輕)
| 29-30,|
| 33)| |--右--(28重)
| |--左--(27;28)|--平--(33輕)
| |--左--(27重)
|
| |--右--(12重)
| |--右--(11;12)|--平--(13重)
| | |--左--(11重)
| |
| | |--右--(15輕)
| |--右--(8-10; |--平--(15;16)|--平--(14重)
| | 11-13)| |--左--(16輕)
| | |
| | | |--右--( 9重)
| | |--左--(8 ; 9)|--平--(10重)
| | |--左--( 8重)
| |
| | |--右--(19輕)
| | |--右--(19;20)|--平--(21輕)
| | | |--左--(20輕)
| | |
| | | |--右--(25輕)
|--左--(1-7, |--平--(19-21;|--平--(25;26)|--平--(27輕)
15-16;| 22-24)| |--左--(26輕)
8-14, | |
17-18)| | |--右--(22輕)
| |--左--(22;23)|--平--(24輕)
| |--左--(23輕)
|
| |--右--( 5重)
| |--右--(4 ; 5)|--平--( 6重)
| | |--左--( 4重)
| |
| | |--右--(17輕)
|--左--(1-3; |--平--(17;18)|--平--( 7重)
4-6)| |--左--(18輕)
|
| |--右--( 2重)
|--左--(1 ; 2)|--平--( 3重)
|--左--( 1重)