Question

有十二个蛋，其中有一个是坏蛋，坏蛋不知轻重，其余的十一个蛋一样重，用天平称三次，找出坏蛋是哪个

Answer 1

首先，把鸡蛋编上号，从1到12，以便叙述算法。在用天平进行称量的时候，每一次都可能有三种结果，分别是：左盘比右盘重，左盘比右盘轻，以及左右平衡。用0、1、2三个数来表示这三种状态，那么所有的结果都可以编码为三进制的数。题目规定可以称3次，那么一共可能出现3×3×3＝27种组合，也就是要用3位三进制数来表示。这27个三进制数一共可以指示出27个“坏蛋”可能存在的位置。而12个鸡蛋中有一个“坏蛋”，那么只有12个可能的位置。加上坏蛋到底比好蛋重还是轻不清楚，所以这两种可能都必须考虑，那么一共只有12×2＝24个“坏蛋”可能存在的位置。24＜27这是很显而易见的事，所以说，12个鸡蛋，称3次完全能找出那个“坏蛋”。就算是13个鸡蛋，有13×2＝26种可能，但26＜27，仍能找出那个“坏蛋”。
解题的方法很简单，把编上号的鸡蛋，按一定的顺序分成3堆。每次都把第一堆放在左盘上，第二堆放在右盘上进行称量，记录上称量的结果。然后按合适的原则重新另外分组，再称。如此重复3次，就可以得到唯一确定的称量结果码。对照一个真值表，就可以找到“坏蛋”的序号，并且“坏蛋”到底比“好蛋”重还是轻也可以知道。
那么，分堆的方法是什么？只要每种称量结果码都是唯一的就可以了，我采用了如下的分堆原则：
第一堆 第二堆 第三堆
第一次： 1 2 3 4 5 6 7 8 9 10 11 12
第二次： 1 2 5 9 3 6 10 11 4 7 8 12
第三次： 1 9 10 12 2 3 4 7 5 6 8 11

至于如何来找到一个合适当分堆方法，感兴趣的请接着往下看：
前面提到了，只要能使每个结果码唯一，分堆的方法就是可用的。方法不止一种，我们只需要其中的一个就足够了。为此假设“坏蛋”是个偏重的蛋，先找出12个三进制码。由于没有别的限制条件，任取12个码就是。
然后假设“坏蛋”是个偏轻的蛋。这时原来结果是0的码位将会变成1，原来是1的码位会变成0，而2不变。也就说偏重时的结果码210，若改为偏轻的话，码会变为201。为了区别清楚坏蛋到底是偏重还是偏轻，必须明确区分这两种码。我们把这种码对称为“0－1镜像码对”。显然，假设“坏蛋”偏重时选的那12个码中，不能同时出现“0－1镜像码对”的两个码，否则就无法把偏重的情况和偏轻的情况区分开来。而且222这个码由于没有“0－1镜像码”，不能参与选择，必须把它排除在外。这样就只有26个码可供选择了。
一个3位三进制码的每一位的值都代表了一次称量的结果。坏蛋出现在第一组的可能只有4种，因为第一组只有4个蛋。所以结果码中某一位上0出现的次数只能是4次，同理，1和2也只能出现4次。因此在选择码的时候得注意使0、1、2在每位上都出现4次。若不符合，可通过把一个码替换成它的“0－1镜像码”来解决。通过一次或多次的替换，最终可以找到一些满足以上所有条件的码的组合，这实际上就是我们所需要的结果真值表。根据结果码倒推出分组方法应该不难，只要确定哪些数字在哪组内就可以了。