12 枚硬币与天平——只称 3 次找出假币的信息计数法

大家好，我是 Senko。本文将解读逻辑谜题的名作“12 枚硬币与天平”。

外表完全相同的 12 枚硬币里，混着一枚重量不同的假币。假币比真币重还是轻，并不知道。能用的只有没有砝码的天平。那么，仅称 3 次，能不能既指出哪一枚是假的，还说出它是重是轻呢？乍看次数完全不够，其实是刚刚好够。

12 枚硬币问题是什么

12 枚硬币问题（英语 twelve-coin problem，假币问题整体叫 counterfeit coin problem），是在天平称量次数有限的条件下锁定假币这类谜题的代表。先把规则整理一下。

硬币 12 枚。其中只有一枚重量不同，其余 11 枚同重
假币比真币是重是轻并不知道
天平只能把硬币放上左右托盘看倾斜，没有砝码
最多称 3 次。要指出哪一枚是假的，以及它是重是轻

这道谜题有意思的地方，全在“是重是轻不知道”这一点上。假如已知假币偏重，事情就好办多了。可轻重不明时，天平倾斜了也分不清是“左盘里有偏重的假币”还是“右盘里有偏轻的假币”，朴素的做法很快就走进死胡同。

1945 年登上杂志，战时大流行

这道谜题的历史意外地新，有记录可查的初出是1945 年 1 月的美国数学杂志《美国数学月刊》。E·D·谢尔出的题是从 8 枚硬币里两次找出偏轻的假币，此后不久，轻重不明、12 枚、3 次的现在形态便流传开来。

据说在第二次世界大战期间，这道谜题在同盟国一侧的科学家与军人之间爆炸性流行。因为太多人丢下工作去琢磨它，甚至留下了“不如把这道谜题空投给德国那边，妨碍敌人的研究”这样的玩笑。真伪暂且不论，它抓住人不放的本事是确凿无疑的。

战后它作为数学谜题的经典被全世界的书收录，如今还被当作信息论与算法的入门教材使用。

6 枚对 6 枚的开局为什么是坏棋

多数人最先想到的开局是“把 12 枚分成 6 枚对 6 枚来称”。对半砍来收缩范围，也就是二分查找的发想。可这偏偏是典型的坏棋。

理由有两个。第一，假币必定在某一个盘里，所以天平百分之百会倾斜。结果已经定成一种的实验，能得到的信息就少了。第二，就算倾斜了，也分不清是“左边 6 枚里有偏重的假币”还是“右边 6 枚里有偏轻的假币”，嫌疑只减到 12 种。

这里引入这道谜题的核心算法。天平称一次的结果是“左边重”“平衡”“右边重”这 3 种。也就是说，3 次称量能区分的模式最多只有 3×3×3 即27 种。

而答案的候选是“哪一枚是假的”的 12 种，乘以“是重是轻”的 2 种，共24 种。27 对 24。勉强够用，可余量只有 3。所以，只要打出一次像“必定倾斜的称量”那样用不满 3 种结果的手，那一刻起 3 次就解不开了。平衡也是宝贵的信息——这是这道谜题最大的教训。

4 枚对 4 枚再调换的具体步骤

那么来看实际解法。开局用4 枚对 4 枚称。给硬币编上 1～12 号，把 1、2、3、4 放左盘，5、6、7、8 放右盘。

平衡的情况好办，假币在剩下的 9～12 这 4 枚里。而且 1～8 这 8 枚已确定是真币，可以随意当基准用。第二次拿 9、10、11 与 3 枚真币比，倾斜方式就能收窄嫌疑与轻重，第三次即可锁定。

有意思的是倾斜的情况。假设左边沉下去，嫌疑人看着增加成了“可能偏重的 1～4”与“可能偏轻的 5～8”共 8 枚。此处的妙手，是调换硬币。

第二次把左盘重组为1、2、5，右盘重组为3、4、6，把 7、8 先拿下来。等于把偏重嫌疑的 3、4 挪到右边，把偏轻嫌疑的 5 挪到左边。这次称量的结果分成 3 种。

平衡的情况：假币是拿下来的 7 或 8。两者都是偏轻嫌疑，所以第三次用 7 对 8 比，轻的那枚是假币
与刚才一样左边沉的情况：原因在没挪动的硬币。收窄到左边留下的 1、2（偏重嫌疑）或右边留下的 6（偏轻嫌疑），所以第三次用 1 对 2 比，重的那枚是假币，平衡则 6 是偏轻的假币
倾斜反转的情况：原因在换了盘的硬币。收窄到挪到右边的 3、4（偏重嫌疑）或挪到左边的 5（偏轻嫌疑），所以第三次用 3 对 4 比，重的那枚是假币，平衡则 5 是偏轻的假币

说到底，这是“分成不动、挪走、拿下三组”的设计：倾斜的变化（相同、反转、平衡）会直接告诉你犯人在哪一组。细节的分配有好几种流派，但任何流派的脊梁都一样，让 3 种结果与 3 个分组一一对应地去编排每一次称量，才是解法的本体。

不是二分查找，而是三分查找的发想

这道谜题教给我们的，是先数一数一次试验的结果会分成几种这套想法。

用是非作答的提问，一次分 2 种，n 次能区分 2 的 n 次方种。用 20 个问题猜中约 105 万种的“二十个问题”游戏，以及把引入缺陷的提交记录对半收缩的 git bisect，都属于这个二进制的世界。而天平一次分成 3 种，所以可以说它是同样次数下比二进制能处理更多候选的三进制工具。

这个视角能直接用在实务的排障上。与其反复做“是不是服务器 A 的问题”这种二选一的验证，不如设计出一次测试就把结果分向多个方向的验证，比如“是网络层、应用层，还是数据层”，那就能用更少的手数摸到原因。反复做那些结果几乎只有一种的确认工作，与反复称 6 枚对 6 枚是一回事。

另外，“没有异常这个结果也含有信息量”这条教训同样重要。就像天平的平衡把 9～12 变成嫌疑人一样，对正常运转部分的确认，会用消去法照出异常的所在。

枚数与条件变了会怎样

能借到一枚作基准的真币时

能处理到 13 枚。在要连轻重一起指出的条件下，n 次称量能处理的枚数最多是（3 的 n 次方−3）÷2 枚，也就是 3 次的极限是 12 枚。可一旦能额外用一枚真币作基准，凑盘上枚数的自由度就变高，变成（3 的 n 次方−1）÷2 枚，3 次可对付到 13 枚。只要有一个可信的基准，搜索能力就会变宽，这与手头有一台校准过的仪器检查就轻松，是同一个结构。