称球问题--经典智力题推而广之.doc

称球问题-经典智力题推而广之.txt人和人的心最近又最远，真诚是中间的通道。试金可以用火，试女人可以用金，试男人可以用女人-往往都经不起那么一试。称球问题-经典智力题推而广之说明 这篇文章试图给出称球问题的一个一般 的和严格的解答。正因为需要做到一般和严 格，就要考虑许多平时遇不到的特别情形， 所以叙述比较繁琐。如果对读者对严格的证 明没有兴趣，可以只阅读介绍问题和约定记 号的第一、第二节，以及第三节末尾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+nk的情况我们都可以用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 于是 log3k/3=H-1。 现在我们把这k个球分为三堆，第一堆和第二堆分别有k/3个球， 并且这两堆中属于第一组的球的数目一样（于是属于第二组的球的数 目也一样），第三堆中有k-2k/3个球（也就是其余的球）。举一个 例子，如果m=7，n=3，那么这三堆可以分成这样：（当然不是唯一的 分法） 第一堆：1，2，3，7（属于第一组的3个，第二组的1个） 第二堆：4，5，6，8（属于第一组的3个，第二组的1个） 第三堆：9，10 这样的分堆总是可能的吗？如果m或n是偶数，那就很简单。比如 说假设m是偶数，有两种可能性。如果m/2k/3，那么就从第一组球 中各取k/3个球作为第一和第二堆（这时在第一第二堆中只有第一组 的球）；如果m/2k/3，那么就把第一组球分为相同的m/2个球的两 堆，再分别用k/3-m/2个第二组球去把它们补充成k/3个球的两堆 （这时在第三堆中就只有第二组的球了）。很显然这样的分堆符合上 面的要求。 如果m和n都是奇数，事情就有点复杂。首先如果(m-1)/2k/3 的话，那么按上面的方法也很容易把球按要求分为三堆。但是如果 (m-1)/2k/3，我们就必须先从第一组中各拿出(m-1)/2个球放入第 一和第二堆，再从第二组中各拿出k/3-(m-1)/2个球将它们补充到各 有k/3个球为止。这就需要从第二组中总共拿得出2(k/3-(m-1)/2) 个球来。所以必须有 2(k/3-(m-1)/2) n 即 2k/3 (m-1)+n 2k/3 k-1 这个不等式在k=3或k4时总是成立的，但是对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-2k/3个球（也就是其余的球）。 我们把第一堆球和第二堆球分别放在天平的左右两端。如果平衡， 那就说明坏球在第三堆里，这样我们就把问题归结为一个k-2k/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-2k/3个球） | | 归结为坏球在 |-左-(1,2,s,(s+1),)中 的问题（k/3个球） 考虑到k-2k/3k/3，另外此次称量后我们至少可以得到一个标准 球（如果不平衡，第三堆里的球均为标准球，否则第一第二堆里的球 均为标准球）。根据归纳假设，上面得到“左”、“平”、“右”三 种情况归结后的问题都可以用log3k/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次。 假设N2，我们有 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（这里2nN）个球在天平两端， 然后看天平的状况再决定后面的步骤。此时有三种情况 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（现在假定N3） 个小球的情况。仍记H=log3(2N)。 首先如果N(3H-1)/2，我们把N个球分成三堆：第一堆和第二堆 中分别有N/3个球，第三堆中为剩下的球，有N-2N/3个。我们把第 一和第二堆小球放在天平左右端进行第一次称量。 三种情况： 如果天平平衡，那么坏球在第三堆的N-2N/3个里，问题归结为 N-2N/3个小球，称H-1次，而且此时我们可以随便从第一或第二堆里 拿出一个球来作标准球。但是 N-2N/3 3N/3-2N/3 = N/3 但由N(3H-1)/2有 N (3H-1)/2-1 = (3H-3)/2 所以 N/3 (3H-1-1)/2 右边一定是一个整数，所以我们最终得到 N-2N/3 N/3 (3H-1-1)/2。 根据归纳假设，在有标准球的情况下，N-2N/3个球的问题可被H-1次 的称量解决。 如果左边重，则要么是坏球比较轻，而且坏球在右面N/3个球里； 要么是坏球比较重，而且坏球在左面N/3个球里。这时根据结论1，我 们还要log3(2N/3)次来找到坏球并知其轻重。和上面的计算完全 一样， N/3 (3H-1-1)/2 于是 2N/3 3H-1-1 log3(2N/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)|