称球问题的一般解法

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

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

有 $m$($m \le 3$)个球,记为 $q_1$、$q_2$、…、$q_m$,其中有且仅有一个坏球,其重量与其他的不同,现使用无砝码的天平进行称量,令 $n$ 为称量次数,问:能确保找到坏球并指出它与好球的轻重关系的 $n$ 的最小值是多少?

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

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

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

方案 1:$q_1 $放左盘,$q_2$ 放右盘。若不平衡(由于对称性,只分析左边轻的情况,下同),则可能的结果还剩 $q_1$ 轻和 $q_2$ 重,再称一次就能找到坏球;若平衡,则可能的结果还剩 $q_3$ 轻、$q_3$ 重、$q_4$ 轻和 $q_4$ 重 $4$ 个,再套用一下商农的定理,此时还要称 $\lceil log_34 \rceil=2$ 次。所以方案 1 被否决。

方案 2:$q_1$、$q_2$ 放左盘,$q_3$、$q_4$ 放右盘。此时天平肯定不会平衡,称量后,可能的结果有 $q_1$ 轻、$q_2$ 轻、$q_3$ 重和 $q_4$ 重 $4$ 个。同样的道理,方案 2 也难逃被否决的命运。

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

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

    $2(m-2x) \le 3^{n-1}$  (平衡时)

    $2x \le 3^{n-1}$ (不平衡时)

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

$$ \frac{2m-3^{n-1}}4 \le x \le \frac{3^{n-1}}2 $$

注意到 $x$ 是整数,$3^{n-1}$ 是奇数,$2m$ 是偶数,所以上面的不等式等价于:

$$ \frac{2m-3^{n-1}}4 \lt x \le \frac{3^{n-1}-1}2 $$

显然,在 $n$ 一定的情况下,$m$ 越大,$x$ 的取值范围越小,而当 $x$ 只能取值 $\frac{3^{n-1}-1}2$ 时,$m$ 继续增大,就会导致 $n$ 次称量找到坏球的计划破产。化简一下,可以得出在 $n$ 一定的情况下 $m$ 的取值范围:$m \lt \frac{3^n}2-1$。发现了吗?现在 $m$ 的最大值正好比我们最初的结果少了 $1$。同时此结果也与前面提到的 $4$ 个球的实际情况相符。

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

命题 1: 有 A、B 两组球,球的个数分别为 $a$、$b$,且 $0\le b-a\le1$,已知这些球中有且仅有一个坏球,若它在 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 \lt \lfloor \frac{3^n}6\rfloor$,否则就与命题的前提不符了。
A1A2A3B1B2B3称量方案
$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=\lfloor \frac{3^n}2\rfloor$ 时,$n$ 次称量无法确保找到坏球并指出其轻重关系。但如果此时也有一个已知的好球的话,答案就不一样了,这时 $n$ 次称量就已经足够(命题 2)。仍使用数学归纳法。

  1. 当 $n=2$ 时,$m=4$,验证一下可知命题成立。
  2. 假设当 $n=k$ 时命题也成立。
  3. 当 $n=k+1$ 时。我们把这些球尽量平均的分成三组,则每组球的个数分别为:$\lfloor \frac{3^n}6\rfloor$、$\lfloor \frac{3^n}6\rfloor$、$\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$ 时,找到一个满足不等式 $\frac{2m-3^{n-1}}4 \lt x \le \frac{3^{n-1}-1}2$ 的 $x$,在天平左右两盘中各放 $x$ 个球。如果天平平衡,问题转化为 $n=k$ 时的情形或命题 2 中的情形;不平衡,则转化为命题 1 的情形。命题成立。

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