12 枚硬币问题

假设你有一架天平（无刻度, 仅能比较重量）和 枚外观完全相同的硬币. 其中有一枚是伪币, 它的重量与其余 枚真币不同, 但你并不知道它是比真币更重还是更轻.

目标是：通过最多 次称量, 找出这枚伪币, 并判断它究竟是更重还是更轻.

逻辑难点

初学者往往会尝试将硬币平分为两组（每组 枚）进行初步称量. 然而, 如果天平不平衡, 我们只能知道伪币在其中的某一组, 却无法判断该组是包含了“过重”的伪币还是“过轻”的伪币. 这种策略在后续步骤中会迅速陷入信息不足的困境.

为了在 次称量内提取足够的信息（天平每次称量有“平衡”、“左重”、“右重”三种结果, 次称量理论上最多可区分 种情况）, 我们需要更精细的分组策略.

第一步：初始化分组

将 枚硬币编号为 至 .

第一次称量：左盘放置 , 右盘放置 .

根据结果, 我们分为两种大类情况讨论.

情况 A：天平平衡

如果天平平衡, 说明伪币必然在剩余的 中, 而 均为真币.

第二次称量：左盘放置 （待测）, 右盘放置 （已知真币）.

1. 若平衡：伪币必然是 . 第三次称量：将 与任意真币（如 ）对比, 即可确定其轻重.
2. 若不平衡：伪币在 中.
   • 若 偏重, 则说明伪币在其中且为“重币”.
   • 若 偏轻, 则说明伪币在其中且为“轻币”. 第三次称量：任取其中两枚（如 和 ）对比. 若平衡, 则第 枚是伪币；若不平衡, 结合第二次的轻重结论即可锁定伪币.

情况 B：天平不平衡

假设左盘 轻于右盘 （反之同理）. 这意味着伪币要么是 中的一个“轻币”, 要么是 中的一个“重币”. 同时, 确定为真币.

第二次称量：这步是关键. 我们进行交叉置换和移位：

• 左盘放置：（保留一个疑似轻币, 移入两个疑似重币）
• 右盘放置：（移入一个疑似轻币, 保留两个疑似重币）
• 剩余：（疑似轻币）和真币

观察第二次称量的结果：

1. 若平衡：伪币必然在未上盘的 中, 且必然是轻币. 第三次称量：对比 和 , 较轻者即为伪币.

2. 若左盘仍轻于右盘： 由于我们将 移到了右盘, 将 移到了左盘, 而天平的偏转方向未变, 说明伪币的位置没有发生导致结果反转的变化. 这意味着伪币要么是留在左盘的轻币 , 要么是留在右盘的重币 . 第三次称量：对比 和 . 若平衡, 则 是轻伪币；若不平衡, 较重者即为重伪币.

3. 若天平反转（左盘重于右盘）： 说明伪币的位置发生了变动, 导致轻重关系反转. 变动的硬币中, 可能的嫌疑人是：移到右盘的轻币候选人 , 或者移到左盘的重币候选人 . 第三次称量：对比 和 . 若平衡, 则 是轻伪币；若不平衡, 较重者即为重伪币.

总结

通过合理的置换与真币的引入, 我们在每一次称量中都最大限度地排除了可能性. 这个问题本质上是信息论的应用： 次称量最多可以从 枚硬币中找出一枚性质不明的伪币. 对于 , 这个上限正是 枚.