UyHiP趣题:用最少的称重次数验证硬币的重量

    这是一个非常有趣的问题,它出自 UyHiP May 2013 的谜题。

    假设你有 n 枚外观完全相同的硬币,它们的重量分别为 1g, 2g, 3g, …, ng 。有意思的是,这一次,你已经知道了各枚硬币的重量,而且你也已经把重量值标在了这些硬币上。但是,由于我不知道各枚硬币的重量,因此我希望你能向我证明,你所标的重量值是正确的(我知道这些硬币的重量是从 1 克到 n 克,我只是不知道哪个硬币对应哪个重量)。

    你唯一能用的工具就是一架天平。每一次,你可以任意选择一枚或多枚硬币,放在天平的左侧,再从剩下的硬币中任意选择一枚或多枚硬币,放在天平的右侧(注意,你只能在天平上放硬币,不能放别的东西)。一个有意思的问题是,为了向我证明你所标的重量值都是对的,你最少需要使用多少次天平?

    显然,为了证明 n 枚硬币的重量标签的正确性,我们最多需要称 n – 1 次。先把硬币 1 放在左边,把硬币 2 放在右边,让对方看到硬币 1 确实比硬币 2 要轻。接下来,向对方验证硬币 2 确实比硬币 3 更轻,硬币 3 确实比硬币 4 更轻,等等。称完 n – 1 次后,我们就相当于给出了 n 枚硬币的轻重顺序,因而它们只有可能分别是 1 克 、 2 克 、 3 克……。

    我们还能做得更好吗?不妨让我们看看 n 比较小的情况。例如,当 n = 4 的时候,利用上述方法可以 3 次完成验证,那么只用 2 次可以完成验证吗?仔细一想,你会发现真的可以!其中一种方法就是,先把硬币 1 和硬币 2 放在左边,把硬币 4 放在右边。由于两枚硬币的重量之和小于第三枚硬币,这只可能是 1 + 2 < 4 ,因此对方会相信,左边两枚硬币分别是 1 和 2 ,右边那枚硬币是 4 ,没放上去的那枚硬币是 3 。对方唯一不知道的就是,在左边两枚硬币中,究竟谁是 1 ,谁是 2 。于是,我们只需要再称一下硬币 1 和硬币 2 ,问题就解决了。

    不妨把证明 n 枚硬币重量标签的正确性最少需要的称重次数记作 B(n) 。我们的问题就是:判断 B(n) 是以什么级别增长的。


 
 
 
 
 
 
 
 
 
 

    答案: B(n) 是以 Θ(log n) 的级别增长的。证明它的下界并不困难。每次称重的时候,一枚硬币要么被放在了左侧,要么被放在了右侧,要么压根儿就没上天平。因而,在 k 次称量当中,一枚硬币的“全程安排”将会有 3k 种不同的可能性。如果 n > 3k ,这就意味着至少会有两枚硬币,它们全程都在一起,每次称重时要么都去左边了,要么都去右边了,要么都没上天平,因而我们就无法区分出谁是谁了。所以说,硬币数 n 必须小于等于 3k ,反过来称重次数 k 也就必须大于等于 log3n 了。

    比较麻烦的就是,我们要想出一种在 O(log n) 步验证硬币重量的算法。我们首先从验证下面的硬币关系开始:

1 < 2
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 6 = 12
……

    不断这样做下去,直到没有这么重的硬币了为止。那么,对方看到了这一系列称量,他会得到些什么结论?他会发现,不管硬币的标称重量是否正确,硬币 6 的实际重量都是硬币 3 的实际重量的两倍,硬币 12 的实际重量也一定是硬币 6 的实际重量的两倍,等等。因而,如果硬币 1 和硬币 2 是正确的,那么硬币 3 也是正确的,接下来所有的硬币都是正确的了;如果硬币 1 或者硬币 2 标称有误,那么硬币 3 就会比标称的更重,于是后面的所有硬币都会比标称的更重。

    假设我们刚才用到的最后一枚硬币是 3 · 2k 。如果 3 · 2k 恰好等于 n ,那么对方就知道了,硬币 1 和硬币 2 是正确的,否则最后这枚硬币的实际重量就会比 n 还大,而这是不可能的。既然硬币 1 和硬币 2 是正确的了,那么刚才用到的所有硬币都是正确的了。

    如果 3 · 2k ≠ n 呢?那么,我们就从刚才用过的所有硬币中选出一些硬币来,让它们的重量之和正好等于 n 。这是总可以做到的。用所有不超过 3 · 2k 的形如 3 · 2i 的数,可以拼出 3 · 2k+1 以内的所有 3 的倍数,再加上 1 和 2 ,我们就可以拼出 3 · 2k+1 以内的所有正整数了。同时注意到, n 一定在这个范围以内,不然的话我们就有 3 · 2k+1 ≤ n ,那刚才 3 · 2k 就不会是最后一枚硬币了。把选出来的这些硬币放到天平左边,把硬币 n 放到天平右边,让对方看到此时天平平衡。那么,对方就知道了,硬币 1 和硬币 2 是正确的,否则天平左边的那些硬币都会比标称的更重,从而让天平左边的实际总重量大于 n ,只在右边放一枚硬币是没法让天平平衡起来的。既然硬币 1 和硬币 2 是正确的了,那么刚才用到的所有硬币都是正确的了。

    无论怎样,我们都用 O(log n) 次称量,证明了 1, 2, 3, 6, 12, …, 3 · 2k 这些硬币的重量。我们把这些硬币叫做辅助币。接下来,我们将利用这些辅助币,用额外的 O(log n) 次称量证明其他所有硬币的重量。

 
    首先,把辅助币从这 n 枚硬币中拿出来。将剩下的硬币从轻到重排成一行,然后把它们分成连续的三段,得到三组硬币。我们需要尽可能保证,三组硬币各自的重量和尽可能一样。如果拿走辅助币之后,剩下的硬币依次是 4, 5, 7, 8, 9, 10, 11, 13, 14, 15 ,那么我会把 4, 5, 7, 8, 9 分成一组, 10, 11, 13 分成一组, 14, 15 分成一组,这三组的重量和分别为 33 、 34 和 29 。现在,把第一组放在天平左边,把第三组放在天平右边,再选出一些总重为 4 克的辅助币(别忘了,用辅助币可以拼出任意不超过 n 的正整数),放在天平的右边,使得天平平衡。于是,对方将会看到,第一组的 5 枚硬币只比第三组的 2 枚硬币重 4 克。他会立即发现,这个 4 克的差值卡得很死。事实上,第一组一定是最轻的 5 枚硬币,第三组一定是最重的 2 枚硬币,只有这样才能实现第一组只比第三组重 4 克。于是,对方就知道了,这三组硬币依次是最轻的 5 枚硬币、中间的 3 枚硬币和最重的 2 枚硬币。他将会知道每一组硬币具体都包含了哪些重量值。

    接下来,我们把每一组硬币继续分成三个小组,在分组时总是遵循下面的原则:第一小组总是最轻的几枚硬币,第三小组总是最重的几枚硬币,同时各个小组的硬币总重尽可能地接近。这里,我们选择把 4, 5, 7, 8, 9 分成 4, 5 | 7, 8 | 9 ,把 10, 11, 13 分成 10 | 11 | 13 ,把 14, 15 分成 14 | | 15 (我们允许某个小组为空)。然后,把每组硬币的第一小组都放到天平左边去,把每组硬币的第三小组都放到天平右边去,再借助辅助币让天平平衡。在我们的例子中, 4, 5, 10, 14 就被放到了左边, 9, 13, 15 就被放到了右边,此时左边比右边轻 4 克,于是在左边放总重 4 克的辅助币,使得天平平衡。对方能够看到,在每一组硬币中,有多少被放到了左边去,有多少被放到了右边去。和上次一样,他将会发现,左边比右边轻 4 克,这个差距是紧的,只能把每一组中最轻的硬币放到左边,把每一组中最重的硬币放到右边,左边才会比右边足足轻 4 克。这样,他就知道了每一组的每一小组硬币都含有哪一段重量值。

    接下来,我们不断地把目前得到的每一组硬币都继续细分成三个小组,同时利用刚才所说的方法向对方证明,每组硬币都被从小到大地分成了连续的三个小组,从而让对方得知每个小组所对应的重量值区间。如果某一组只剩一枚硬币了,对方就可以精确地知道这枚硬币的重量,此时便可以把它从这些硬币中移除了。

    我们在分组时,为什么要保证各小组的硬币总重尽可能接近呢?这是因为,当我们把每一组硬币中的第一小组放到天平左边,同时把每一组硬币中的第三小组放到天平右边后,我们希望天平两边的重量之差不超过 n ,这样我们才能借助辅助币让两边平衡。不过,由于我们在分组时不可能完全均分重量,因而难免出现重量之差仍然大于 n 的情况。此时,我们总可以对其中一些分组进行常数级别的微调(比如把第三小组中最轻的硬币划给第二小组,或者把第二小组中最重的硬币划给第三小组),从而把天平两边的重量之差缩小到 n 克以内。

    在任意时刻,任意一组硬币中的重量值总是一段线性增加的(基本上可以说是连续的)序列,因而把它们从小到大累加起来,其结果是平方级别增长的。因此,在对它进行分组时,从渐近意义上说,第一小组的硬币数量最多不超过该组硬币数量的 √1/3 = 0.577… ,第三小组的硬币数量不会少于该组硬币数量的 1 – √2/3 = 0.1835… 。可见,在检验硬币重量的过程中,各组硬币的数量呈指数级递减,这表明我们所需要的称重次数不超过 O(log n) 。

 
 
 
 

    数列 B(n) 有一个非常有趣的名字,叫做 Baron Münchhausen’s Omni-数列。

    Baron Münchhausen 是 18 世纪德国的一位著名的“吹牛大王”。他参军回家后,向人们讲述了很多“传奇经历”,比如他骑马陷入沼泽地后,抓着自己的头发,把自己连人带马从沼泽里拔了起来。 2000 年, Baron Münchhausen 的名字出现在了俄罗斯全国奥林匹克数学竞赛的分区赛中:

8 枚硬币的重量分别是 1g, 2g, …, 8g ,但我们不知道哪枚硬币对应于哪个重量。 Baron Münchhausen 宣称他知道每一枚硬币的重量,而且他还说,只需要用天平称一次,他便能向众人验证出,至少有一枚硬币的重量正如他所言。这真的有可能,还是他又在说大话?

    问题的答案是,这是有可能的。 Baron Münchhausen 可以把最轻的 5 枚硬币放在天平左边,把最重的 2 枚硬币放在天平右边,于是天平平衡。 5 枚硬币的总重和 2 枚硬币的总重相同,只有可能是 1 + 2 + 3 + 4 + 5 = 7 + 8 ,这就证明了没放上天平的那枚硬币确实是 6 克。

    后来, Tanya Khovanova 、 Konstantin Knop 和 Alexey Radul 合写了一篇论文,对这个问题进行了扩展:验证 n 枚硬币中至少一枚硬币的重量,最少需要使用多少次天平?他们把该问题的答案形成的数列叫做 Baron Münchhausen 数列,用 A(n) 来表示。他们利用很多与三角形数有关的性质,证明了一个非常令人吃惊的结论: A(n) 总是小于等于 2 的。并且,我们还能精确地知道,在哪些情况下 A(n) = 1 :若 n 是一个三角形数,或者 n 等于某个三角形数加 1 ,或者第 n 个三角形数是一个平方数,或者第 n 个三角形数等于某个平方数加 1 ,则 A(n) = 1 。其他情况下, A(n) 都等于 2 。

    但是,如果我们要求用最少的称量次数检验出所有硬币的重量呢?于是,我们就把这个加强版问题的答案形成的数列叫做 Baron Münchhausen’s Omni-数列,这就是数列 B(n) 名字的由来。

    有意思的是,真要追溯起来,数列 B(n) 似乎比数列 A(n) 出现得更早。在 1991 年莫斯科奥林匹克数学竞赛中, Sergey Tokarev 提出了下面这个问题:

有 6 枚硬币,它们的重量分别为 1 克、 2 克、 3 克、 4 克、 5 克、 6 克。它们看上去完全相同,只是上面的标签不一样。每一枚硬币上都标有 {1, 2, 3, 4, 5, 6} 中的一个数,它代表这枚硬币的重量。只用两次天平,如何判断出这些标签是否都是正确的?

    其中一种可能的答案是,首先检验 1 + 2 + 3 = 6 ,然后检验 1 + 6 < 3 + 5 。另一种方案则是检验 1 + 2 + 5 < 3 + 6 和 1 + 3 < 5 。两种方法都可以把 6 枚硬币的实际重量确定下来。另外,根据前面的论断,只用一次天平是无法把 6 枚硬币都区分开的,因此 B(6) 精确地等于 2 。这恐怕是序列 B(n) 在历史上的第一次出镜了。

    有趣的是,虽然我们已经成功破解了 A(n) ,但却始终没有揭开 B(n) 的面纱。目前,人们已经求出了数列 B(n) 的开头几项:

0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, …

    UyHiP 是我非常喜欢的一个每月谜题活动,它的 puzzlemaster 是 Michael Brand 。 Michael Brand 本人对数列 B(n) 非常感兴趣,他已经发表了好几篇论文,在渐近意义上证明了一些与数列 B(n) 有关的性质。但是,正如刚才所说,我们对 B(n) 的了解仍然少得可怜;我们甚至还不知道, B(n) 是否是单调递增的。并且,在 Michael Brand 看来,这个硬币问题还只是“一整类尚未被探索过的数学问题中的冰山一角”。感兴趣的读者不妨做一些小小的研究,或许会有意想不到的发现。

 

17 条评论

发表评论