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

这是一个非常有趣的问题，它出自UyHiP May 2013(http://www.brand.site.co.il/riddles/201305q.html)的谜题。

假设你有 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 次称量当中，一枚硬币的“全程安排”将会有 3^k种不同的可能性。如果 n > 3^k，这就意味着至少会有两枚硬币，它们全程都在一起，每次称重时要么都去左边了，要么都去右边了，要么都没上天平，因而我们就无法区分出谁是谁了。所以说，硬币数 n 必须小于等于 3^k，反过来称重次数 k 也就必须大于等于 log₃n 了。

比较麻烦的就是，我们要想出一种在 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 · 2^k。如果 3 · 2^k恰好等于 n ，那么对方就知道了，硬币 1 和硬币 2 是正确的，否则最后这枚硬币的实际重量就会比 n 还大，而这是不可能的。既然硬币 1 和硬币 2 是正确的了，那么刚才用到的所有硬币都是正确的了。

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

无论怎样，我们都用 O(log n) 次称量，证明了 1, 2, 3, 6, 12, …, 3 · 2^k这些硬币的重量。我们把这些硬币叫做辅助币。接下来，我们将利用这些辅助币，用额外的 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 看来，这个硬币问题还只是“一整类尚未被探索过的数学问题中的冰山一角”。感兴趣的读者不妨做一些小小的研究，或许会有意想不到的发现。