经典称球问题之解答与推广(最全最强之终结者版)(转载)
By 遥控
at 2017-05-25 • 0人收藏 • 105人看过
本文转自《三思科学》电子杂志第三期，2001年9月1日。作者异调
转载请保留。
称球问题——经典智力题推而广之三
异调
说明
这篇文章试图给出称球问题的一个一般
的和严格的解答。正因为需要做到一般和严
格，就要考虑许多平时遇不到的特别情形，
所以叙述比较繁琐。如果对读者对严格的证
明没有兴趣，可以只阅读介绍问题和约定记
号的第一、第二节，以及第三节末尾27个球
的例子，和第五节13个球和40个球的解法。
事实上所有的技巧都已经表现在这几个例子
里了。
一、问题
称球问题的经典形式是这样的：
“有十二个外表相同的球，其中有一个坏球，它的重量和其它十
一个有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的
很灵敏的天平，问如何称三次就保证找出那个坏球，并知道它比标准
球重还是轻。”
这可能是网上被做过次数最多的一道智力题了。它的一种解法如
下：
将十二个球编号为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，那
转载请保留。
称球问题——经典智力题推而广之三
异调
说明
这篇文章试图给出称球问题的一个一般
的和严格的解答。正因为需要做到一般和严
格，就要考虑许多平时遇不到的特别情形，
所以叙述比较繁琐。如果对读者对严格的证
明没有兴趣，可以只阅读介绍问题和约定记
号的第一、第二节，以及第三节末尾27个球
的例子，和第五节13个球和40个球的解法。
事实上所有的技巧都已经表现在这几个例子
里了。
一、问题
称球问题的经典形式是这样的：
“有十二个外表相同的球，其中有一个坏球，它的重量和其它十
一个有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的
很灵敏的天平，问如何称三次就保证找出那个坏球，并知道它比标准
球重还是轻。”
这可能是网上被做过次数最多的一道智力题了。它的一种解法如
下：
将十二个球编号为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，那