伪币问题II（绿皮书）：仅一次称重确定5袋硬币重量类型的技术问询

Hey，这个问题我刚好琢磨过，咱们一步步拆解明白：

首先先把问题再明确下，避免理解偏差：

有5个袋子，每个袋子里有100枚硬币。每枚硬币的重量可能是9g、10g或11g。每个袋子里的硬币重量完全一致，但我们不知道每个袋子装的是哪种重量的硬币。你有一台能显示精确重量的电子秤，如何仅通过一次称重就确定每个袋子的硬币类型？

咱们先从更简单的2袋情况入手，理解核心逻辑——这正是你提到的鸽巢原理的应用：

• 如果只有1个袋子，那太简单了，拿1枚称就行，直接知道是9、10还是11g。
• 但到2个袋子时，总共有3²=9种可能的重量组合（也就是“鸽子”）。要是咱们从第2袋只拿1枚，总共称2枚的话，总重量只会有18、19、20这3种可能（也就是“鸽巢”），这肯定会有歧义——不同的组合会得到相同的重量，根本没法区分。

所以核心就是要给每个袋子选一个独特的取币数量，让每个袋子的重量偏差（相对于10g的标准币）能在总重量里形成唯一的“标识”，不会和其他袋子的偏差互相干扰。那选什么数量合适呢？

答案是用3的幂次来取硬币，具体操作如下：

• 先给5个袋子分别编号1到5
• 从袋1取3⁰=1枚，袋2取3¹=3枚，袋3取3²=9枚，袋4取3³=27枚，袋5取3⁴=81枚
• 把这些硬币全部放到秤上，得到总重量W

接下来计算偏差值：先算如果所有硬币都是10g的标准重量，总重量应该是(1+3+9+27+81)*10 = 1210g。然后算Δ = W - 1210g。

现在把Δ转换成三进制数，这里要注意处理非0/1的数字：

• 因为每个袋子的偏差只有-1（9g）、0（10g）、+1（11g）三种，所以三进制里如果出现2，就转换成进位：2 = 3 - 1，也就是当前位记为-1，高位加1；如果出现-2，就转换成-2 = -3 + 1，当前位记为1，高位减1
• 转换后的三进制数的每一位，从低位到高位（对应袋1到袋5）就代表了每个袋子的偏差：
  • 某一位是-1：该袋硬币是9g
  • 某一位是0：该袋硬币是10g
  • 某一位是1：该袋硬币是11g

举个实际例子帮你理解：假设总重量是1215g，那Δ=1215-1210=5。把5转成普通三进制是12，这里的2我们需要转换：12 = 13¹ + 23⁰ = 13¹ + (3-1)3⁰ = 13¹ +13¹ -13⁰ = 23¹ -13⁰，再把2转换：23¹=3² -3¹，所以最终是13² -13¹ -1*3⁰，也就是三进制的1(-1)(-1)。对应到袋子就是：袋3是11g（+1），袋2是9g（-1），袋1是9g（-1），袋4和袋5都是10g。

为什么选3的幂次？因为每袋的重量偏差刚好有三种可能，3的幂次能保证每个袋子的偏差在总重量里的“权重”是完全独立的，不会和其他袋子的偏差产生重叠歧义，完美避免了你提到的“鸽巢碰撞”问题——这样总共有3⁵=243种可能的Δ值，每一种都对应唯一的袋子重量组合，一次称重就足够区分所有情况。

备注：内容来源于stack exchange，提问作者Connor Brown