← 发霉啦：今天，我换了个新牙医

0

上期脑力小体操 3天平和8银币谜题 答案详解

9月30日，脑力小体操 版块 3天平和8银币谜题。

有8枚外观相同的银币，其中1枚里面掺了锡。现在给你3台没配砝码的天平。已知其中两个可正常使用，但第三台天平会给出随机结果(有时是正确的，有时是错误的)。你不知道哪个秤坏了。问：你称量几次可找到那枚假币？

显而易见的，锡比银轻，所以假币更轻。

下面公布称量方法。核心思路是，如果两台天平给出了一样的结果，则这个结果肯定为真。

具体操作，先给银币标上记号。简单的用数字代号：1，2，……，8。注意，应用下面的方法，哪怕再添上一枚银币(9号)，也不会增加称量次数。

接着用 3除银币代号数。则显然余数只能为0、1、2。

有两种分组标准，其一，余数相同的放到一组：(3、6)(1、4、7)(2、5、8)。3和6整除3，余数是0；4除以3，余数是1；5除以3，余数为2，如此。

其二，每一组里，余数恰好各为0、1、2。这个其实有最自然的分组：(1、2、3)(4、5、6)(7、8)。这里最后一组(7、8)和之前的(3、6)都少了数字9。

用符号“-”表示称量操作，“=”表示结果。

如表达式(1、4、7)-(1、2、3)=(1、2、3)，表示比较(1、4、7)和(1、2、3)这两组的轻重，结果是(1、2、3)更轻。

如果重量一样，记(1、4、7)-(1、2、3)=(3、6),也就是输出结果为剩下的那一组。

注意，1号银币不可能在同一次称量的时候，同时位于天平两端，但可以同时不位于两端——就是直接拿走1号——而这不会影响最终结果。也就是说(1、4、7)-(1、2、3)=(4、7)-(2、3)。

三架天平分别记为ABC。

下面 实际操作步骤。

第一次，用A (1、4、7)-(2、5、8)。
第二次，用B (1、2、3)-(4、5、6)。
第三次，用C 比较前两次筛选出的两组的轻重。
第四次，根据之前的情况，具体分析。

用几种具体情况演示一下算法。

①如 第一次，(1、4、7)-(2、5、8)=(3、6)；第二次，(1、2、3)-(4、5、6)=(7、8)。我们立即可知，天平A和B必然有一个是坏的！

为什么呢？如果A和B全是好天平，则两次结果都是可信的。(1、2、3)-(4、5、6)=(7、8)，说明假币在(7、8)里，但(1、4、7)-(2、5、8)=(3、6)说明假币在(3、6)里，矛盾。所以天平A和B必然有一个是坏的，也就是说C肯定是好的。同时假币一定在(3、6、7、8)里

第三次，(7、8)-(3、6)。输出的结果肯定不为平(记=0)。比如(7、8)-(3、6)=(7、8)，那第四次就直接(7)-(8)，确定假币。

②再如 第一次，(1、4、7)-(2、5、8)=(2、5、8)；第二次，(1、2、3)-(4、5、6)=(1、2、3)。因为两架天平必有一架是好的。所以假币肯定在(1、2、3、5、8)里。

第三次 (2、5、8)-(1、2、3)=(5、8)-(1、3)。

如果(5、8)-(1、3)=0。则立知2为假币。为什么呢？

可以分别假设C是好天平和坏天平：若C坏，则前两次称量结果全部正确，所以只能是2；若C好，则最后一次测量有意义，但又推理出假币肯定在(1、2、3、5、8)里，所以必然是2。所以无论C好坏，结果都是2。

如果(5、8)-(1、3)≠0(如=(5、8))，类似的分类讨论：C好，则假币在(5、8)里，也就是说天平B是坏的，进而A是好的；C坏，则A和B都是好的。所以 A总是好的，同时假币肯定在(2、5、8)里。这样，第四次，用A (5)-(8)便可。

③再再如 第一次，(1、4、7)-(2、5、8)=(2、5、8)；第二次，(1、2、3)-(4、5、6)=(7、8)。这种情况看起来有点特殊，按算法，第三次(2、5、8)-(7、8)?

因为两次称量已经确定假币在(2、5、7、8)里，所以稍微变通一下便可：第三次添加一枚肯定不是假币的辅助币 (2、5、8)-(7、4、8)。

若(2、5)-(7、4)=0， 与②里类似的推理知，8为假币。
若(2、5)-(7、4)=(2、5)，与②里类似的推理知A天平肯定是好的。第四次称量肯定能找出假币。
若(2、5)-(7、4)=(7、4)，与②里类似的推理知B天平肯定是好的。第四次称量肯定能找出假币。

实际上，按照这一程序，无论前三次输出结果如何(只要本质上无矛盾)，都能借助推理确定一个好天平和假币所在的组(至多三枚硬币)。故而第四次称量肯定能得到结论。剩下的情况，大家自己推理试试。

答案，至多需要称量4次。

借助三进制和数学归纳法，这种方法可以推广到用给定的天平组在 3x + 1 称重中找到 3^2x 枚硬币中的轻硬币。因此，对于 81 个硬币，您需要 7 次称重。对于更大量的硬币(>~1000)，存在更强大的算法。

赞一个 (1)