本文发表于《CSDN开发高手》2004年第5期

称球问题相信大家已经很熟悉了，并且已经知道从12个球中找出坏球并判断其轻重最多只需要3次称量。但如果把球数改变一下，比如说13个球，答案又是几次呢？本文将对这一问题进行“深入”分析。为了后面叙述方便，先在这里把一般化后的问题重复一下：

有m（m≥3）个球，记为q1、q2、…、qm，其中有且仅有一个坏球，其重量与其他的不同，现使用无砝码的天平进行称量，令n为称量次数，问：能确保找到坏球并指出它与好球的轻重关系的n的最小值是多少？

先来看理论上要多少次。每次称量有左边轻、平衡和右边轻共3种可能的情况，而坏球的可能结果有q1轻、q1重、q2轻、q2重、…、qm轻、qm重等共2m种。因此，根据商农的信息论，此问题的熵就是需要的称量次数，又因为n是整数，所以有：n=⌈log32m⌉n=\lceil log_32m \rceil。

不过理论终归是理论，直接拿到现实生活中往往行不通。一个很简单的情况，4个球，上面的公式说2次称量就够了。但你可以想想办法，反正我是没找到两次解决问题的方案。

那，是理论错了吗？唔，我可不敢怀疑商农，我只敢怀疑我自己。来看看我们错在哪了吧。对4个球的情况，第一次称量只有两个可选的方案：

方案1：q1放左盘，q2放右盘。若不平衡（由于对称性，只分析左边轻的情况，下同），则可能的结果还剩q1轻和q2重，再称一次就能找到坏球；若平衡，则可能的结果还剩q3轻、q3重、q4轻和q4重4个，再套用一下商农的定理，此时还要称⌈log34⌉=2\lceil log_34 \rceil=2次。所以方案1被否决。

方案2：q1、q2放左盘，q3、q4放右盘。此时天平肯定不会平衡，称量后，可能的结果有q1轻、q2轻、q3重和q4重4个。同样的道理，方案2也难逃被否决的命运。

在4个球这么简单的情况下就撞得满头是包，未免让人难以接受，总结一下经验教训吧，把上面的分析归纳一下并推广到一般情况，就是：整个称量过程中，要达到目的，倒数第k次称量前的可能结果数h，必须满足条件h≤3kh \le 3^k。

上面的得出的结论虽然不能让我们找到问题的答案，但却有助于我们确定每次称量的方案，特别是第一次如何做。假设我们计划的称量次数是n，第一次在左右两盘中各放x个球，则保证下面两个不等式同时成立是解决问题的必要条件：

2(m−2x)≤3n−12(m-2x) \le 3^{n-1}  （平衡时）

2x≤3n−12x \le 3^{n-1} （不平衡时）

把这两个不等式稍加变换，就成了下面的样子：

2m−3n−14≤x≤3n−12\frac{2m-3^{n-1}}4 \le x \le \frac{3^{n-1}}2

注意到x是整数，3n−13^{n-1}是奇数，2m是偶数，所以上面的不等式等价于：$$\frac{2m-3^{n-1}}4 \lt x \le \frac{3^{n-1}-1}2$$
显然，在n一定的情况下，m越大，x的取值范围越小，而当x只能取值3n−1−12\frac{3^{n-1}-1}2时，m继续增大，就会导致n次称量找到坏球的计划破产。化简一下，可以得出在n一定的情况下m的取值范围：m<3n2−1m \lt \frac{3^n}2-1。发现了吗？现在m的最大值正好比我们最初的结果少了1。同时此结果也与前面提到的4个球的实际情况相符。

但分析了半天，我们只证明了m不在取值范围内时，n次称量不能确保找到坏球。那m在取值范围内的时候，肯定能找到吗？答案是肯定的，不过马上证明它有点难，先来看两个简单一点的命题。

命题1： 有A、B两组球，球的个数分别为a、b，且0≤b-a≤1，已知这些球中有且仅有一个坏球，若它在A组中，则比正常球轻，在B组中则比正常球重。另有一个好球。先使用无砝码的天平称量，令n=⌈log3(a+b)⌉n=\lceil log_3(a+b)\rceil，则可以找到一个称量方案，使得最多经过n次称量，就可以找到坏球（此时肯定能指出它与好球的重量关系）。

使用数学归纳法证明如下：

  1. 当n=1时，a、b的取值可能有{0，1}、{1，1}、{1，2}三组，由于还有一个已知的好球，所以不难验证此时命题成立。
  2. 假设当n=k时命题也成立。
  3. 当n=k+1时。我们将A、B两组球分别尽量平均得分为三组，记为A1、A2、A3、B1、B2和B3。不影响一般性，假设这六组球按球数从少到多的排列次序也与前面的顺序一致，且A1有球a1个。则第一次称量时的称量方案与每组球个数的对应关系如下，其中需要注意的是：在最后两种情况下，必有a1<⌊3n6⌋a1 \lt \lfloor \frac{3^n}6\rfloor，否则就与命题的前提不符了。
A1 A2 A3 B1 B2 B3 称量方案
a1 a1 a1 a1 a1 a1 A1、B1放左盘；A2、B2放右盘
a1 a1 a1 a1 a1 a1+1 A1、B1放左盘；A2、B2放右盘
a1 a1 a1+1 a1 a1 a1+1 A1、B3放左盘；A3、B1放右盘
a1 a1 a1+1 a1 a1+1 a1+1 A1、B2放左盘；A2、B3放右盘
a1 a1+1 a1+1 a1 a1+1 a1+1 A2、B2放左盘；A3、B3放右盘
a1 a1+1 a1+1 a1+1 a1+1 a1+1 A2、B2放左盘；A3、B3放右盘

很明显，不管结果是什么，第一次称量之后，问题都能转化为n=k时的情形。所以，命题1是真命题。

前面已经证明m=⌊3n2⌋m=\lfloor \frac{3^n}2\rfloor时，n次称量无法确保找到坏球并指出其轻重关系。但如果此时也有一个已知的好球的话，答案就不一样了，这时n次称量就已经足够（命题2）。仍使用数学归纳法。

  1. 当n=2时，m=4，验证一下可知命题成立。
  2. 假设当n=k时命题也成立。
  3. 当n=k+1时。我们把这些球尽量平均的分成三组，则每组球的个数分别为：⌊3n6⌋\lfloor \frac{3^n}6\rfloor、⌊3n6⌋\lfloor \frac{3^n}6\rfloor、⌊3n6⌋+1\lfloor \frac{3^n}6\rfloor+1。第一次称量时，第一组和那个好球放左盘，第三组放右盘。若平衡，问题转化为n=k时的情形，不平衡，问题转化为命题1的情形。命题成立。

有了前面两个证明作基础，最初的问题就很简单了，再次祭出数据学归纳法。由于m<5时的情况有些特殊(考虑只有一个球或两个球的情况)，不能作为递推得依据，所以我们从n=3，也就是m=5开始。

  1. 当n=3时，m在5和12之间（13的情况已经被排除在外），通过一一验证可知命题成立。
  2. 假设当n=k时命题也成立。
  3. 当n=k+1时，找到一个满足不等式2m−3n−14<x≤3n−1−12\frac{2m-3^{n-1}}4 \lt x \le \frac{3^{n-1}-1}2的x，在天平左右两盘中各放x个球。如果天平平衡，问题转化为n=k时的情形或命题2中的情形；不平衡，则转化为命题1的情形。命题成立。

综上所述，称球问题的完整答案是：当球数m<3n2−1m\lt\frac{3^n}2-1时，n次称量时就能确保找到坏球，并指出它与好球的轻重关系；当球数m=⌊3n2⌋m=\lfloor\frac{3^n}2\rfloor时，n次称量只能确保找到坏球，而无法指出它与好球的轻重关系。要想指出轻重关系，就可能需要多进行一次称量。但如果此时再有一个好球，就又可以把这次称量省掉了。