2008 (4)
带信息的球
先复习一下带颜色球的含意：绿球表示已知该球是好球，白球表示可能是好球，也可能是坏球，但如是坏球则轻；黑球表示可能是好球，也可能是坏球，但如是坏球则重；灰球则无任何信息，即便知其是坏球，还是不知（较好球而言）是轻还是重。换言之，黑球和白球已有部分信息，绿球则有完全信息，而灰球不含任何信息。
我们可以证明如下的结论：
引理一：如果n个带部分信息的球中恰有一个坏球，而且 3^(k-1) < n <= 3^k, 则用k次天平就能找出坏球并知其轻重。除了一个例外，就是k=1时，如果2个球1白1黑，则多少次都没法找到坏球。
引理二：如果n个灰色球中恰有一个是坏球，但有好球（绿色球）可以借用，且 {3^(k-1)-1}/2 < n <= (3^k-1)/2, 则用k次天平就能找出坏球并知轻重。
什么是有好球可以借用？以k=3为例说明一下。在n=13的情况下，如何只用3次天平就找出坏球并知轻重？先借用9个好球放在天平的一边，另一边放9个灰色球。如两边持平，则9个灰色球为好球，涂上绿颜色。坏球在剩下的4个灰球中，因为有好球可以借用，再用两次天平就可找出坏球并知轻重了（请读者仔细想想）。如两边不平，灰球轻则将其涂上白色，重则涂上黑色，坏球必在这9个球中。因为有部分信息，用引理一，用两次天平就可找出坏球并知轻重了。如无好球借用，3次是不可能一定从13个灰色球中找出坏球并知轻重的。当然，可以找出其中的坏球，但有可能不知轻重，读者不妨仔细想想。
两个引理都可以用数学归纳法证明，这里从略。
有了这两个引理，就不难证明下面的定理了：
定理：如果n=(3^k-3)/2个不含任何信息（灰色球）的球中恰有一个坏球，则用k次天平就能找出坏球并知轻重。
证明如下：令x={3^(k-1)-1}/2, 则n=3x。天平两边各放x个球，称过之后有两种可能。
情形1， 天平持平：这时天平上的球都是好球，涂上绿色。剩下的x个灰球还是不带任何信息，但已有好球可以借用。引用引理二，剩下的x个球再用k-1次天平就能找出坏球并知轻重。
情形2，天平不平 : 将轻的那边的球涂上白色，重的那边涂上黑色，剩下的是好球，涂上绿色。现在2x个球已有部分信息，由引理一可知再用k-1次天平便可找到坏球并知轻重。
在定理中令k=3，就是著名的12球问题了。
