问题
称球问题的经典形式是这样的：
“有十二个外表相同的球，其中有一个坏球，它的重量和其他十一个有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的很灵敏的天平，问如何称三次就保证找出那个坏球，并知道它比标准球重还是轻。”
这可能是被做过次数最多的一道智力题了。它的一种解法如下：将十二个球编号为1～12。
第一次，先将1～4号放在左边，5～8号放在右边。
1.如果右重，则坏球在1～8号。第二次将2～4号拿掉，将6～8号从右边移到左边，把9～11号放在右边。就是说，把1，6，7，8放在左边，5，9，10，11放在右边。
2.如果右重，则坏球在没有被触动的1，5号。如果是1号，则它比标准球轻；如果是5号，则它比标准球重。
第三次将1号放在左边，2号放在右边。
1.如果右重，则1号是坏球，且比标准球轻；2.如果平衡，则5号是坏球，且比标准球重；3.这次不可能左重。
4.如果平衡则坏球在被拿掉的2～4号，且比标准球轻。
第三次将2号放在左边，3号放在右边。
1.如果右重，则2号是坏球，且比标准球轻；2.如果平衡，则4号是坏球，且比标准球轻；3.如果左重，则3号是坏球，且比标准球轻。
4.如果左重，则坏球在拿到左边的6～8号，且比标准球重。
第三次将6号放在左边，7号放在右边。
1.如果右重，则7号是坏球，且比标准球重；2.如果平衡，则8号是坏球，且比标准球重；3.如果左重，则6号是坏球，且比标准球重。
4.如果天平平衡，则坏球在9～12号。
第二次将1～3号放在左边，9～11号放在右边。
1.如果右重，则坏球在9～11号，且坏球较重。
第三次将9号放在左边，10号放在右边。
1.如果右重，则10号是坏球，且比标准球重；2.如果平衡，则11号是坏球，且比标准球重；3.如果左重，则9号是坏球，且比标准球重。
4.如果平衡，则坏球为12号。
第三次将1号放在左边，12号放在右边。
1.如果右重，则12号是坏球，且比标准球重；2.这次不可能平衡；3.如果左重，则12号是坏球，且比标准球轻。
4.如果左重，则坏球在9～11号，且坏球较轻。
第三次将9号放在左边，10号放在右边。
1.如果右重，则9号是坏球，且比标准球轻；2.如果平衡，则11号是坏球，且比标准球轻；3.如果左重，则10号是坏球，且比标准球轻。
4.如果左重，则坏球在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号是坏球，且比标准球轻。
4.如果平衡，则坏球在被拿掉的2～4号，且比标准球重。
第三次将2号放在左边，3号放在右边。
1.如果右重，则3号是坏球，且比标准球重；2.如果平衡，则4号是坏球，且比标准球重；3.如果左重，则2号是坏球，且比标准球重。
3.如果左，重则坏球在没有被触动的1，5号。如果是1号，则它比标准球重；如果是5号，则它比标准球轻。
第三次将1号放在左边，2号放在右边。
1.这次不可能右重。
2.如果平衡，则5号是坏球，且比标准球轻；3.如果左重，则1号是坏球，且比标准球重；够麻烦的吧。其实里面有许多情况是对称的，比如第一次称时的右重和右轻，只需考虑一种就可以了，另一种完全可以比照执行。我把整个过程写下来，只是想吓唬吓唬大家。
稍微试一下，就可以知道只称两次是不可能保证找到坏球的。如果给的是十三个球，以上的解法也基本有效，只是要有个小小的改动，就是在这种情况下，在第一第二次都平衡的时候，第三次还是有可能平衡，那么我们可以肯定坏球是13号球，可是我们没法知道它到底是比标准球轻，还是比标准球重。如果给的是十四个球，我们会发现无论如何也不可能只称三次，就保证找出坏球。
一个自然而然的问题就是：对于给定的自然数N，我们怎么来解有N个球的称球问题？
在下面的讨论中，给定任一自然数N，我们要解决以下问题：（1）找出N球称球问题所需的最小次数，并证明以上所给的最小次数的确是最小的；（2）给出最小次数称球的具体方法；（3）如果只要求找出坏球而不要求知道坏球的轻重，对N球称球问题解决以上两个问题；还有一个我们并不是那么感兴趣，但是作为副产品的问题是：（4）如果除了所给的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～4；5～8）
-右-（1，6～8；5，9～11）
-右-（1；2）
-右-（1轻）-平-（5重）-左-（2轻）-平-（2；3）
-右-（2轻）-平-（4轻）-左-（3轻）-左-（6；7）
-右-（7重）-平-（8重）-左-（6重）-平-（1-3；9-11）
-右-（9；10）
-右-（10重）-平-（11重）-左-（9重）-平-（2；3）
-右-（12重）-平-（13轻，13重）*-左-（12轻）-左-（9；10）-右-（9轻）-平-（11轻）-左-（10轻）-左-（1-3；9-11）
-右-（6；7）
-右-（6轻）-平-（8轻）-左-（7轻）-平-（2；3）
-右-（3重）-平-（4重）-左-（2重）-左-（1；2）
-右-（2重）-平-（5轻）-左-（1重）
（*：对应十三个球的情形。）这里“右”、“平”和“左”分别表示称量的结果为“右重”、“平衡”和“左重”所对应的分支。在树的叶子（就是最右边没有子节点的那些节点）部分，我们标出了“能够到达”这些节点的布局，也就是说在进行每一节点上的称量时，这个布局所给的结果和通往相对应的叶子的道路上所标出的“右”、“平”和“左”相符合。从这个图我们也可以清楚地看到，根下的左分支和右分支是对称的：只需要把所有的“右”改成“左”，“左”改成“右”，“轻”改成“重”，“重”改成“轻”；节点（1～3；9～11）下的左分支和右分支也有这个特点。
如果有朋友对树理论感兴趣，可以参考随便哪一本图论或者离散数学的书。在这里我们只用到树理论里最基本的知识，所用的名词和结论都是相当直观的。所以如果你不知道树理论，用不着特别去学也可以看懂这里的论证。
所以给定一棵三分树（就是说除了叶子以外其他的节点都有三个子节点的树），在每个不是叶子的节点上给定一个称量，并且规定这个节点下的三个分支（子树）分别对应右重、平衡、左重的情况，我们就得到了一种称球的方法。我们把这样一棵三分树称为一个“策略”或一棵“策略树”。你可以给出一个平凡的策略，比如说无论发生了什么事总是把1号和2号球放在左右两侧来称（在叶子上我们没有写出相应的布局，用@来代替）：（1；2）-右-（1；2）-右-@A-平-@-左-@-平-（1；2）-右-@-平-@-左-@-左-（1；2）-右-（1；2）-右-@B-平-@-左-@-平-（1；2）-右-@-平-@-左-@-左-（1；2）-右-@-平-@-左-@当然这么个策略没什么用场，只能让我们知道1号球和2号球之间的轻重关系。另外我们看到，每个分支不一定一样长，上面这棵策略树根下面左分支就比较长。
一棵树的高度是叶子到根之间的结点数的最大值加一。比如说上面这个图中，叶子A和根间有1个节点，而叶子B和根间有2个节点，没有和根之间的节点数超过2的叶子。所以它的高度是2＋1=3。前面十二球解法策略树的高度也是3。一棵没有任何分支，只有根节点的树，我们定义它的高度是0。
显然，策略树的高度就是实行这个策略所需要的称量的次数。我们的目的，就是找到一棵“好”的策略树，使得它的高度最小。
什么是“好”策略？我们回过头来再看十二球解法策略树。我们说过，叶子上的那些布局都是从根开始通向叶子的。比如说布局（7重），它之所以在那片叶子上是因为按照这个策略，三次称量的结果是“右左右”；又比如说布局（11重），它之所以在那片叶子上是因为按照这个策略，三次称量的结果是“平右平”。如果两个布局通向同一片叶子，那么就是说按照这个策略，三次称量的结果是完全一样的，于是我们就不能通过这个策略来把这两种布局区分开来。比如说在十三个球的情况下，（13轻）和（13重）都通向和“平平平”相对应的叶子，这两个布局中13号球或者轻或者重，于是我们知道13号球一定是坏球，但是通过这个策略我们不可能知道它到底是轻还是重。
所以对于标准的称球问题（找出坏球并知其比标准球重或轻）的“好”策略，就是那些能使不同的布局通向不同的叶子的策略。
问题的解答
现在我们就可以来回答第一节中的问题了。
结论2：
现有N个小球，其中有一个坏球不知比标准球轻还是重。我们令H={log32N｝。
