用最少的称重次数验证硬币的重量

偏执的太偏执、 2022-01-10 18:15 408阅读 0赞

这是一个非常有趣的问题，它出自 [**UyHiP May 2013**][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) 是以 Θ(logn)  的级别增长的。证明它的下界并不困难。每次称重的时候，一枚硬币要么被放在了左侧，要么被放在了右侧，要么压根儿就没上天平。因而，在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(logn) 次称量，证明了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-数列。

BaronMü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 克。

后来， TanyaKhovanova 、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 看来，这个硬币问题还只是“一整类尚未被探索过的数学问题中的冰山一角”。感兴趣的读者不妨做一些小小的研究，或许会有意想不到的发现。

[UyHiP May 2013]: http://www.brand.site.co.il/riddles/201305q.html