榕城老应

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

经过前面这些思考，发现也不难有一般性结果。

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

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

我们现在证明。

引理1：称k次可以并最多在3**k个半确定的球中找出次品，并且知道其轻重。

用数学归纳法，k=1。3个半确定的球，一定有至少有两个属于同一类，比如说重次球，将这两个上天平，重的那个就是次品，如果平衡，外边的那个就是次品，而且从它的类别知道这次品是较重还是较轻。验证正确。

假设结论对k-1次正确。将3**k个半确定的球三等分，天平一边各放3**(k-1)个球，使得两边共有偶数个重次球，记为2a个。这总是可以做到的。因为我们可以把“不齐整”数目的球放在外面。这样天平左右各有a个重次球和3**(k-1)-a个轻次球。这时如果左边重，左边的a个重次球和右边的3**(k-1)-a个轻次球，共3**(k-1)个半确定球有嫌疑，其他都是正品。如果右边重，同理将嫌疑缩小到3**(k-1)个半确定球。如果平衡，嫌疑在外面的3**(k-1)个半确定球中。我们已知用k-1次可以解决3**(k-1)个半确定的球。证毕。

引理2：如果加一个已知的正品球称k次，可以并最多在（3**k+1）/2个球中找出次品，但有且仅有一种情况不知其次品的轻重。

在k=1情况，有2个球，取一个与正品球上天平，如果平衡，次品在外面，但不知它比正品轻还是重，注意这是归纳证明中仅有的情况。

假设结论对k-1次正确。考虑第一次天平称量，一边取（3**（k-1）-1）/2个加上一个正品球，另一边取（3**（k-1）+1）/2个球。我们知道这次称量以后，如果天平平衡，那么嫌疑在外面。余下k-1次可以解决这里的（3**（k-1）+1）/2个球，有且仅有一种情况不知其次品的轻重。如果天平不平衡，天平的两边都是半确定的球。由引理1知道，余下k-1次可以解决这里的3**(k-1)个球。因为这个数是奇数，所以我们必须在第一次天平称量时再加上一个已知的正品球。因此称k次，可以并最多解决3**（k-1）+（3**（k-1）+1）/2=（3**k+1）/2个球。证毕。

定理：在一堆等重球中有一个重量不同的次品球，用天平称k次找出来，这堆球最多且可以是（3**k-1）/2个球。

在第一次称量我们最多可以将3**(k-1)-1个球两等分放在天平上，如果不平衡，由引理1，可以再称k-1次解决。如果平衡，天平这里都是已知球，由引理2，可以再称k-1次解决外面的（3**（k-1）+1）/2个球。所以总共可以解决（3**k-1）/2个球。证毕。

由这个定理我们可以知道称2，3，4，5次，分别可以在4，13，40，121个球中找出那个次品，因为这个证明是构造性的，所以知道该怎么称量。

如果在称球问题中不知道有没有这个次品球存在，这和判别出嫌疑的次品球是较轻还是较重是同一个问题。在引理2证明中知道，只有每次分堆时，天平都是平衡的，总是被分在外面的那个球被认为是次品球时不知轻重。把这个球去掉，或者说要解决的问题少了一个球就行了。这也就是说，用天平称k次可以在一堆（3**k-3）/2个球中确定有没有一个重量不同的次品，如果有，是哪一个，是较轻还是较重。

有人问，如果我要解决问题那堆球比你构造性证明中的数量少，怎么办？你每次分堆时把不齐整的数搁在外边那堆，不就行了？