称13球问题十分经典，就我所知也有三十多年历史了。因为问题简单，不需要预备知识，又有点难度，纯凭清醒脑力来解答，成为大人小孩通杀经久不衰的练脑题，聪明的中学生纸上画画也能解出，大人也就考究个虚空冥想，心智澄明的功力。这问题网上有不少答案，恐怕连中学生都知道了。喜欢做研究的人，就会考虑一般性的问题。

在除了一个重量不同的次品外，其他等重的一堆球中，用天平称k次找出来，问这堆球最多可以是多少？

它的通解是：最多可以达到n =（3**k-1）/2个球。这里3**k意思是3的k次方。我曾将这证明贴在外面的网上，很多人都看过了，现在附在后面。在科学网写科普，要有点技术含量的新意，才对得起愿意动脑筋看帖子的人。我就在这里分享考虑问题的思路。

首先考虑一个简单的情况，假如已知这个次品比正品重（或轻），把这堆球三等分，放两堆到天平两边称一次可以指出是在哪一堆，一直重复这三等分法，就能确定是哪一个。所以称k次可以分辨3**k个球。

有人从信息的角度解答这简单题。从n个球中取出次品的概率是1/n，确定它需要log2(n)比特的信息量；用天平称会有三种结果：左重右轻、平衡、左轻右重，称一次给出的信息量是log2(3)；所以从n个球中找出次品，需要称的次数k是log2(n)/log2(3)=log3(n)，也就是n = 3**k ，这和上面的答案是一样的。

对于不知次品轻重的情况，从n个球中取出次品的概率是1/n，而这次品是偏重或偏轻的概率是1/2，确定它需要log2(2n)比特的信息量。所以从n个球中找出次品需要称的次数k至少是log2(2n)/log2(3)=log3(2n)，也就是2n <= 3**k ，考虑到左边是偶数，右边是奇数，故有n =（3**k-1）/2，这和通解的答案是一样的。

这个信息量说法看起来很牛，既简练又准确。但是做研究，每一步必须有根据，所有说法要落到实处，一直追查到逻辑上没有含糊之处才算完。我们首先要问：为什么可以应用这信息的计算？这球的信息量和天平的信息量是怎么联系起来？

“信息论中的编码理论呀！”好。那我们就要考究怎么把这问题转化为编码问题。

对于简化问题，把这球排成一列，每次称时相当于编码数字的位置，判断次品属于哪一堆相当于给这位置赋值，从而可以给这列球编号，这构造了编码的模型，当然可以用信息量来解。为了说明可以应用编码的概念，其根据是天平称量把球区分成3堆的分类法。这是绕了一圈来说问题，这里的信息论编码只是用来装饰，除了看起来比较高深以外，对解题没有多大帮助，还不如直接用分类法解来得更直观。

对于一般问题，怎么用几次天平称量的状态给这2n种的可能性编码？天平只能作用在物理的球上，每个球联系着两种的可能，在天平的两边必须放等量的球，所以考虑编码还必须受到物理实现的约束。不考虑这些细节，没办法构造编码的数学模型。直接套用信息量计算的公式看起来很牛，虽然结果也对。但深思下去就觉得这个步子迈得太大，缺乏说服力。

我举个例子来提疑问。大家知道对于5个球，用天平称两次是没有办法从中区分出次品球。这用信息量的解释是：5个球其中有个次品不知偏重或轻，信息量是log2(10)，称两次信息处理能力是2log2(3)= log2(9)，当然是不能区分。但是，我们如果加上一个已知的正品球，就能够区分了。（这个解法见《称球问题》帖子和下面决策树，其中放外边那堆5个球的称法，或后面通解的证明）需知这个已知的球信息量是0，加在一起不会减少问题的信息量。或许你说它可以加强天平分辨能力，这就需要深入分析其作用。所以说直接套用信息量的做法，没有揭示其中的逻辑。

好了，同分析简化问题看法一样，与其绕一圈套用信息的说法，不如考虑决策树来得直观。

决策树【1】是这样的，天平在树的节点上，每个节点依天平的3种状态分出3个分支，称量的次数k相当于树的层数，决策树的叶子是几次称量后可以分辨的状态集。什么是问题空间的状态？每个球有两种状态“疑重”或“疑轻”，分别代表着它可能是重的次品和轻的次品，附上球的编号，n个球对应着2n个状态。这些疑是次品球的状态通过通过节点，即天平称量的分流，沿着不同分支各自走向叶子。叶子中的状态是通过它所经路径称量的排除，次品和它的状态被确定到这里。如果要分辨出次品及其轻重，每个叶子只能包含一个状态，如果只要分辨出次品，叶子里包含的状态必须不超出一个球但可以包含这球的两个状态。举个具体例子。

比如说3个球，按编号和“疑重”、“疑轻”，6种状态分别记为1z 1q 2z 2q 3z 3q。将1号和2号球分别放天平左边和右边，3号在外面，一次称量后的决策树如下：

第一列表示称量前，所有疑是次品球的状态，及在天平的位置，园括号里的球在天平的左边，方括号的在右边，其他的在天平外边。第二列是称量时天平的状态。第三列是被称量后区分出的疑是次品球的状态集。比如说1z 2q是在天平左重时，疑是次品只可能是1号重或2号球轻。在这叶子里，因为有两个状态，有两个球号的还不知道次品是哪个。只有对应平衡时3z 3q，知道3号球是次品，但不知其轻重。

细考决策树中，沿着所有平衡分支走到底的（全平衡）叶子，里面包含着每次称量都是平衡情况下的疑是次品球，它总是放在天平外。因为都没经过称量，所以它包含着每个球的两种状态。如果这叶子里只有一个球号，那个次品球就是它了，但不知其轻重。而所有其他叶子里的球，都至少经过了一次的称量，球一但上过天平，它的两种状态就分离开来，沿着两个分支走去，所以不可能同在一片叶子里。在这些叶子里，每个球都只能有一种状态。考虑n个球，通过称量要把它们区分出来，因为全平衡叶子必须包含一个球的两种状态，这需要2n-1片叶子。K次称量最多可以有3**k片叶子，我们有：2n-1 <= 3**k即n <=（3**k+1）/2。这是称k次能够区分球的上限。这个上限不一定能够达到，要看实际的测量是怎么分配的。

下面的决策树是13球的一个区分方案：将1-4号球放天平左边，5-8号右边，9-13号外面，这里第3，5，7列是第一次、第二次、第三次称重后天平状态区分出疑是次品球的状态集，其中园括号里是下次称量时，天平左边中的球号状态；方括号则是右边的；括号外是在天平外待定的球号状态，x表示在天平那边加一个正品球。

这个决策树很直观地揭露出很多信息。其一，（3**k+1）/2是个很好的上界，通过合适的配置可能实现。如在第一次平衡后的子树显示，加一个正品球就可以区分5个球达到了这个上界，注意到这个13球的决策树，叶子中有两个空位，如果称量时手里有个正品球，第一次称9个加上这个正品球，3次就能区分出14个球，也达到这个上界。所以13球的局限在于天平分配上，这暗示着没有已知正品球时，可以达到的极限是n =（3**k-1）/2。其二，因为全平衡叶子不能区分球的两种状态，如果要求确定次品的轻重，我们就不能利用这个叶子，所以这种情况下的极限是n =（3**k-3）/2。有了这些猜测和决策树分配的思路，不难用数学归纳法证明这些结论。

在《称球问题》帖子里，有人建议用黄金分割法（优选法）来确定放在外面的球数，对13球这确实近似于正确值5，但是0.618比率并没有与正确值有内在联系，也只是一个猜测法。从下面证明可以看出，对于称k次情况，放在外面的球数应该是（3**(k-1)+1）/2。当k > 3时，优选法建议的值就开始不对了。

有人说，这题中的正品球应该是不可区分的，就像玻色子一样。这个改变了题意。不过探索新问题这也是做研究时常做的事，就像我们看到很漂亮的理论结果，就看看改变一下条件能否也得出有意义的结果。我想了一下，觉得这个改变把难度降低了点，家里有小孩的不妨让他们试试，这个（因为不可区分）不允许混合称过的球及没称过球的解法。问：在这时要几次才能分13球？反问题是：称3次可以从多少这样的球中找出次品？

做研究、玩游戏和写帖子凡是有意义的，都需要有一点技术含量。这才对得起花时间的读者和自己的智商。有时看到没什么技术含量的东西却冠以夸张的说法，还顾盼自雄，真的很无语。这如果只是想炒作自己，尚无大害。如果做研究也是这般的态度，写的也是吹毛求疵但没有什么有意义的内容，类似于：发现了Gale-Shapley算法不符合“为稳定婚配设计的求偶规则”提法之类的口水文，为此洋洋自得，以为捍卫了数学的严谨性和科学的严肃性，那学生们就可堪忧虑了。

【附录】

称球问题通解的证明

做研究最好的方法是先看简单特殊的问题，从直观中找出思路，经过前面这些思考，我们已经找到诀窍，所以不难将它扩大成一般性的结果。

考虑一般问题，把球分三堆，放两堆等数的球上天平，如果平衡，次品当然在外面这一堆。如果不平衡，比如说左边重，我们只知道外边的肯定是正品，但次品不知道是在天平的哪一边。重的那一边的球定义为“疑重球”，如果在这边，那次品一定是较重。轻的那一边定义为“疑轻球”，若是在这边则次品较轻。所以天平上的这些球经过一次称量之后已经被消除掉一部分的不确定性，称为半确定的球。半确定的球集合中只有两类的球，疑重球或疑轻球，集合中可以混合着这两类球，但知道每个球属于哪一类。