|
还是那个老问题：有12个外表一模一样的球，其中有一个坏球重量不同于其他11个。只允许使用三次天平，如何找出坏球并弄清是轻是重？
上一文已经提过，利用信息论里的结论，已有可行的解法。但是，那个解法有个缺陷：就是下一次如何称，依赖于上一次的结果。你没法偷闲，得盯着天平等结果，再设计下一步的方案。这样不好，你总得抽点时间上上网，瞅瞅热闹，对不？有没有更好的方法呢？
有的。
先谈谈想法：
每用一次天平，就会有一个结果：左重，右重，或左右平衡。左重用L表示，右重用R表示，左右平衡就用B（BALANCED）表示。从左到右依次写下三次结果。比方说，LBR表示第一次左重，第二次左右平衡和第三次右重。
总共会有多少个不同的组合呢？因为每一个位置有三种可能，不难算出，答案是27。在这27种可能中，包括了LLL，BBB和RRR。
结果BBB是什么意思？它表示，三次称球，坏球都不在天平上。所以我们可以要求，每一个球至少得上一次天平，这样可避免BBB的出现。再看LLL又是什么意思。它表示，坏球要么三次都在左边，或三次都在右边，如何排除这种可能？只需不让同一个球每次都在同一边即可，这通时也排除了RRR的可能。
好了，这样就只有24种可能了。
再来看看LBR和RBL分别代表什么意思。假设我们先得出LBR，那么如果每次都把天平两边的球互换一下，结果就自然成了RBL了。所以这本质上代表同一种方案，只不过是将天平左右的球互换了一下而已。如果从LBR得出某号球是坏球并且重，那么RBL自然就得出该号球为坏球并且轻了。类似，LLR和RRL表应该揭示同一个坏球，只不过轻重互换。依此类推，24种可能就分成了12组，代表本质上12种不同的方案。每组各含两种可能，揭示了同一个坏球，其中一个揭示坏球为重，另一个揭示坏球为轻。
这12组分别是：{LLB,RRB}, {LLR,RRL}, {LBL,RBR}, {LBB, RBB}, {LBR,RBL}, {LRL,RLR}, {LRB,RLB}, {LRR,RLL}, {BLL,BRR}, {BLB,BRB}, {BLR, BRL}, {BBL, BBR}。
那么，LLB和RRB哪一个表示坏球为重呢？这个可由我们自定。假设LLB表示某号球为坏球且重，它又是什么意思？它表示该号球第一次第二次均在天平的左边，第三次不在天平上了。如果这样的球只有一个，那它一定就是坏球了。我们的目标是，设计一种方案，使得每一个结果组合对应着唯一一个球，从而把坏球找到并知轻重。再看LLB，从第二次到第三次结果发生了变化，这又说明坏球就在变换了的那些球中，而且是从天平上换到了比方是桌子上。
为方便起见，根据第一次变化来给每个结果组合分组。先定义L->B->R->L为顺时针方向，则L->R->B->L为逆时针方向。
如果第一次变化是顺时针方向，则将该接果组合归为重球组，否则归为轻球组。比如LLB，它的第一次变化是从L变为B，是顺时针方向，所以归为重球组。反之，RRB的第一次变化是从R变为B，所以归为轻球组。大家不难发现，12组中，每一组中的两个结果只有一个归为重球组，另一个归为轻球组。
同样为了方便，把上述12组分别标上从1到12个号码，于是有下面的结果。
组号 重球组 轻球组
1 LLB RRB
2 RRL LLR
3 LBL RBR
4 LBB RBB
5 LBR RBL
6 RLR LRL
7 RLB LRB
8 RLL LRR
9 BRR BLL
10 BRB BLB
11 BRL BLR
12 BBR BBL
现在我们来设计天平的用法。将组号和球号对应起来，也就是组号代表球号。
将重球组中第一个字母为L的球放到天平左边，第一个字母为R的球放到天平右边，这样称第一次。所以，第一次左边是1，3，4，5四个球，而右边是2，6，7，8四个球。类似，将重球组中第二个字母为L的球放到天平左边，第二个字母为R的球放到天平右边，这样称第二次。第二次 左边有1，6，7，8四个球，右边有2，9，10，11四个球。接下去，将重球组中第三个字母为L的球放到天平左边，第三个字母为R的球放到天平右边，这样称第三次。第三次左边有2，3，8，11四个球，右边有5，6，9，12四个球。
所以三次称球方案如下：
左边 右边
1，3，4，5 2，6，7， 8
1，6，7，8 2，9，10，11
2，3，8，11 5，6，9， 12
从左到右依次写下三次称出的结果。
如果最后的结果是LBB，我们有什么结论？首先，LBB对应4号球，其次，它属重球组，所以结论是：4号球是坏球并且重。为什么是这样？该结果表示坏球一开始在天平上，后两次都不在天平上了，只有4号球符合这个条件，而从第一次称球结果就知4号球重。
再看最后的结果是LRB的情形：它对应7号球，属轻球组，所以7号球为坏球并且轻。其它情形可以此类推，读者自己试试看。
当然，我们也可如下推理。
1）假设已知坏球较重，如1号球为坏球时，三次称出的结果应该是LLB。同样，如2号球为坏球，三次称出的结果就是RRL了。以此类推我们可以得出下面的重球表：
球号 结果
1 LLB
2 RRL
3 LBL
4 LBB
5 LBR
6 RLR
7 RLB
8 RLL
9 BRR
10 BRB
11 BRL
12 BBR
由于表上的对应关系，如果反过来知道三次的称球结果在右边，我们就很容易找到对应的坏球并且能判断为重了。
2）同理，如果已知坏球为轻，又可得出下面的轻球表。
球号 结果
1 RRB
2 LLR
3 RBR
4 RBB
5 RBL
6 LRL
7 LRB
8 LRR
9 BLL
10 BLB
11 BLR
12 BBL
同样，如果结果在上表中，也很容易找到对应的坏球了并知其为轻了。
今天先谈到这里，以后再试图给出更通俗易懂的解释。有兴趣的同学，请等着下一只鞋子落地。
|
