Stephen 的好看簿

称球问题--经典智力题
本文转自三思科学
说明 　　

   这篇文章试图给出称球问题的一个一般的和严格的解答。正因为需要做到一般和严格，就要考虑许多平时遇不到的特别情形，所以叙述比较繁琐。如果对读者对严格的证明没有兴趣，可以只阅读介绍问题和约定记号的第一、第二节，以及第三节末尾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的三分树最多只能有3^H方片叶子。于是这棵策略树必须满足条
件
　　3^H≥ 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＜(3^H-1)/2，那么称H次就足够了；
3)如果N=(3^H-1)/2，那么称H次足以保证找到坏球，但不足以保证知道坏球比标准球轻还是重；
4)如果N=(3^H-1)/2，而且还另有一个标准球，那么称H次足以保证找到坏球和知道，知道坏球比标准球轻还是重。

　　假设N=2，我们有
5)如果还另有一个标准球，称H={log3(2*2)}=2次足以保证找到坏球和知道坏球比标准球轻还是重。

　　5)看起来有点奇怪，不过这其实很显然。如果有超过两个球，我们知道坏球是"独一无二"的那一个，总找得出来；但是如果只有两个球，一个好球一个坏球，都是"独一无二"的，如果没有一个标准球的话，我们无论如何不可能知道哪个才是好的。

　　首先假设结论成立，我们来看看几个具体例子。如果是12个球，那么
　　H = {log3(2*12)} = 3，
而且
　　12 ＜ (27-1)/2 = 13。
所以根据2)我们知道称3次可以找出坏球并知其轻重。如果是13个球，那么
　　H={log3(2*13)}=3，
而且
　　(27-1)/2=13。
根据3)我们知道称3次可以找出坏球但不一定能知其轻重。但是如果另有一个标准球的话，称3次就可找出坏球且知其轻重。

一般地，能由H次称量找出坏球并知道其轻重的最大小球数量为
　　(3^H-1)/2-1 = (3^H-3)/2；
能由H次称量找出坏球但不需要知道其轻重的最大小球数量为
　　(3^H-1)/2；
有一标准球，能由H次称量找出坏球并知道其轻重的最大小球数量也为
　　(3^H-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) ≤ 3^H-1
也就是
　　2((3H-1)/2-2n) ≤ 3^H-1
所以
　　3^H-1 ≤ 2n+1/2
考虑到3H-1为整数，于是
　　3^H-1 ≤ 2n
但3H-1又是奇数，而2n是偶数，所以
　　3^H-1 ＜ 2n。 (*)
而后一个式子表明
　　2n ≤ 3^H-1
同样考虑到奇偶性
　　2n ＜ 3^H-1。 (**)
我们看到(*)和(**)式是矛盾的。

　　所以对N=(3^H-1)/2的情况，只用H步是不能够称出坏球又知道它的轻重的。它的原因在于，虽然理论上N=(3^H-1)/2，那么可能的布局是(3^H-1)种，而一棵H层的策略树有3^H片叶子，看起来叶子足够多了。但是由于第一步的称量无论如何也不可能把这3^H-1种布局平均地分配在左中右三棵子策略树上，总有一个分支上承受的布局会超过3^(H-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＜(3^H-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＜(3^H-1)/2有
　　N ≤ (3^H-1)/2-1 = (3^H-3)/2
所以
　　N/3 ≤ (3^(H-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} ≤ 3^(H-1)-1
　　{log3(2{N/3}))} ≤ H-1
所以仍旧可以用剩下的H-1次称量解决问题。

　　如果右边重，完全类似于左边重的情况。

　　现在考虑N=(3^H-1)/2的情况，这时允许用一个标准球。我们可以把球分成三堆。第一堆为(3^(H-1)+1)/2个，第二堆为(3^(H-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次称量解决。

　　如果左边重，则要么是坏球比较轻，而且坏球在右面(3^(H-1)+1)/2个球里；要么是坏球比较重，而且坏球在左面除了附加的标准球以外的(3^(H-1)-1)/2个球里。这时根据结论1，我们还要{log3(3^(H-1)+1)/2+(3^(H-1)-1)/2)} = H-1次来找到坏球并知其轻重。所以这也可以用剩下的H-1次称量来解决问题。

　　如果右边重，完全类似于左边重的情况。

　　这就完全证明了结论2中的2)、4)和5)。剩下的就是3)的前半部分：如果N=(3H-1)/2，那么称H次足以保证找到坏球（但可能不知道轻重）。

　　这很简单，如果我们拿掉一个球，那么根据2)，一定能用H次称量来找到坏球并且知道轻重--唯一的例外是，如果被拿掉的那个恰好就是坏球--那么这时候所有称量的结果都是天平保持平衡。如果发生了这样的事，所有称量的结果都是天平保持平衡，我们就可以断定坏球就是那个被拿掉的球，当然这时这个球从来没有上过天平，我们绝无可能知道它是比标准球重，还是比标准球轻。


//以下的证明都简洁的,嘿嘿.要善于思考（转载）
定理:用天平称m次最多可以在只有一个坏球(重量不同)的n(n=(3^m-1)/2)个小球中找出这个坏球(不需要知道其轻重的),且这里的n是最佳的,不能再大了.
证明:
   
    *_~.

      首先说一下基本思路,我们把一次称量映射成一个n长的向量,此n长向量
由元素{0,1,-1}组成(本文后面提到的向量元素都是取自0,1,-1).映射关系如下.

1:把n个球编号,1,2,....n
2:第k次称量对应的向量记为A[k].A[k]的元素按以下方式确定.
  在这次称量中:
  如果第i(i=1,2...n)个小球在左盘,则令A[k](i)=1;
  如果第i(1=1,2...n)个小球在右盘,则令A[k](i)=-1;
  如果第i(i=1,2...n)个小球没有参加称量,令A[k](i)=0.
  这里A[k](i)表示向量A[k]的第i个元素.

  下面我们构造一组满足两个条件的向量组A,为以下的工作做准备

约束条件
1.对任意i,j.A[i]!=-A[j] ( != 表示不等)
2.sum(A)=0,即A中所有向量和是零向量.
____________________________________________________________________
| |
| 第一步: 我们首先证明满足这样条件的m长向量个数不会超过n=(3^m-1)/2 |
|___________________________________________________________________|

   我们首先注意到所有的元素取自{-1,0,1}的向量总数是3^m.去掉非零向量,
其余的3^m-1各向量按互为相反向量(记对应元素互为相反数)配对,共有(3^m-1)/2对.
显然根据条件1,每一对中最多取一个元素,这样n<=(3^m-1)/2+1(算上0向量).
   
   下面再说不可能在所有的(3^m-1)/2对中每一对中都取出一个向量来.
   
   用反证法,不然,我们首先考虑所有的向量中第一位元素非零的向量共有多少个,
显然有2*3^(m-1)个,由于这样的向量必然是两两互为相反数的.所以所有的(3^m-1)/2
对中有2*3^(m-1)/2=3^(m-1)个对第一位取自{1,-1}.这样如果我们在每一对中都取一
个向量的话,我们考虑所有向量的和的第一位元素,其值应该是前面所说的3^(m-1)个首位
非零的向量首位元素之和.而1,-1,3^(m-1)均为奇数,所以其和不可能是偶数零.而由上面
的约束条件2知所有的向量和为零.矛盾.
所以我们知道要满足上面的两个约束条件,n<=(3^m-1)/2

___________________________________________________
| |
| 第二步: 下面我们证明n=(3^m-1)/2是可以达到的. |
|_________________________________________________|_

用归纳法.
m=1,n=(3^1-1)/2=1,取(0)
m=2,n=(3^2-1)/2=4,取(0,0),(0,1),(-1,0),(1,-1)

设m=k时成立,就是可以找到(3^k-1)/2个满足条件的k长向量.那么
 m=k+1时,我们在前面说的(3^k-1)/2-1个k长非零向量前分别添加元素-1,0,1,这样就得
到了3[(3^k-1)/2-1]=(3^(k+1)-1)/2-4.易证这些向量也满足前面给出的约束条件.
又由前面的证明知m=k时有一对向量未被选取(即由于前面的奇偶矛盾).设为(R,-R),我们
在她的基础上再构造3个新向量.(1,R),(-1,0..0),(0,-R).再加上全零向量.就得到的
[3^(k+1)-1]/2个满足约束条件的向量组.

*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
* *
* 下面用前面构造的向量组来解决m个小球中找出唯一坏球的方法. *
* *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
首先把所有的向量按列向量的方式写出,每列一个向量.这样有m各行向量排成一个m*n矩阵.

这样每一行就是一个n长行向量,按照本文最开始说的对应关系.我们往盘中放小球(即若
第k个元素为1,则放标号为k的小球在左盘,为-1则放右盘,0不放).并且我们记第k次称量
的结果写在第k行向量的右面.并且按照下面的方式纪录.左面沉则记1,右面沉记-1,平衡
记0.这样就得到了一组m长的结果列向量.

我们说把这个结果列向量与前面的矩阵的每一列相比较,如果与第k列相同,那么可以断言
标号为k的小球是坏球.:-)

    这是因为只有一个坏球,假设是标号为j的球是坏球.由于不知道该球比标准球轻还
是重.
   i)如果重,那么看矩阵的第j列,第s个元素为1,那么根据前面的纪录方法知结果向量
中的第s个元素也为1;第s个元素为-1,结果向量中的相应元素也为-1;第s元素为0,那么结
果向量中的相应元素也为0.
   ii)如果轻,道理相同,不过是1-->-1,-1-->1,0-->0.

因此,我们即使不知道坏小球比标准小球轻还是重,但是结果向量一定等于该小球所对的
列向量或者它的相反向量.故我们得到结果向量后,就得到两个互为相反向量的两个可能
向量.我们在前面的n列中找到与他们其中之一相同的向量,这列向量所对应的小球就是坏
球.


/////////////////////////////////////////////////////////////////////////////
   
说明:
   由于我们的限制条件1,使得每行向量中的1,-1数目一样多,这保证了称量时左右两
盘的球数一样多.

   由于限制条件2,保证了结果列向量所对应的两个互为相反向量的两个向量不能同时
在矩阵中.这就使得我们可以唯一确定坏球.

最后说一下,n=(3^m-1)/2是不能改进的,这由前面的向量构造中可以看出,如果数目增加
,别必然导致出现相反向量对或相同向量,这时由于我们不知道坏球是轻是重,从而无法
在这两个球中做出判断.

一道趣味数学题与诺依曼的故事
     有这样一道数学题：
     两个男孩各骑一辆自行车，从相距2O英里（1英里合1.6093千米）的两个地方，开始沿直线相向骑行。在他们起步的那一瞬间，一辆自行车车把上的一只苍蝇，开始向另一辆自行车径直飞去。它一到达另一辆自行车车把，就立即转向往回飞行。这只苍蝇如此往返，在两辆自行车的车把之间来回飞行，直到两辆自行车相遇为止。
     如果每辆自行车都以每小时1O英里的等速前进，苍蝇以每小时15英里的等速飞行，那么，苍蝇总共飞行了多少英里？

     答案很简单: 每辆自行车运动的速度是每小时10英里，两者将在1小时后相遇于2O英里距离的中点。苍蝇飞行的速度是每小时15英里，因此在1小时中，它总共飞行了15英里。许多人试图用复杂的方法求解这道题目。他们计算苍蝇在两辆自行车车把之间的第一次路程，然后是返回的路程，依此类推，算出那些越来越短的路程。但这将涉及所谓无穷级数求和，这是非常复杂的高等数学。
 
     我是想由此引出下面这个故事：
     据说，在一次鸡尾酒会上，有人向约翰·冯·诺伊曼（John von Neumann,1903～1957,20世纪最伟大的数学家之一。）提出这个问题，他思索片刻便给出正确答案。提问者显得有点沮丧，他解释说，绝大多数数学家总是忽略能解决这个问题的简单方法，而去采用无穷级数求和的复杂方法。
     冯·诺伊曼脸上露出惊奇的神色。“可是，我用的的确是无穷级数求和的方法，”他解释道。