关于3ⁿ-1枚硬币中假币可在n次称重内识别的证明问询

咱们用数学归纳法来严谨证明这个结论，逻辑会非常清晰：

一、基础案例验证 #

n=1时 #

此时硬币总数是$3^1 -1 = 2$枚。只需要把两枚硬币放在天平两端称1次，重的那枚就是假币（如果存在的话），完全符合“至多1次称重”的要求。

n=2时 #

对应8枚硬币，咱们可以这样操作：

• 先拿出2枚硬币，把剩下的6枚平均分成两组（各3枚），第一次称这两组。
  • 如果两组重量相等：说明假币在之前拿出的2枚里，再称1次就能确定重的那枚，总共2次。
  • 如果其中一组更重：假币在这组3枚里。从这3枚里拿2枚称第二次，重的就是假币；如果相等，剩下的那枚就是假币，同样总共2次。
    完全满足“至多2次称重”的条件。

二、归纳法推广 #

归纳假设 #

假设当$n=k$（k为正整数）时，对于$3^k -1$枚硬币（至多1枚重假币），我们总能用至多k次称重找出假币（或确定无假币）。

归纳步骤（证明n=k+1时成立） #

当$n=k+1$时，硬币总数为$3^{k+1} -1$枚。我们把硬币分成三组：

• A组：$3^k$枚
• B组：$3^k$枚
• C组：$3^{k+1}-1 - 2*3^k = 3^k -1$枚

第一次称重A组和B组：

1. 若A、B重量相等：假币必然在C组的$3^k -1$枚里。根据归纳假设，这部分硬币用至多k次就能找出假币，加上本次称重，总共$k+1$次，符合要求。
2. 若A（或B）更重：假币在重的那组$3^{k$枚里。对于$3}k$枚硬币找重假币，我们可以每次把硬币分成3等份，称其中两组——重的那组有假币，相等则在第三组，每次范围缩小到1/3，k次称重后就能精准定位假币。加上本次称重，总共也是$k+1$次，符合要求。

结论 #

通过基础案例验证+数学归纳法，我们证明了：对于数量为$3^n -1$的硬币（至多1枚重假币），总能通过至多n次称重识别出假币。

内容的提问来源于stack exchange，提问作者Raton