在假币谜题中寻找数学真理

我们 最近的一系列谜题以不起眼的双盘天平为特色，它在历史上是商业和政府、艺术和科学的象征。天平在休闲数学中也很流行。平衡谜题需要清晰、合乎逻辑的推理，并且很适合数学概括。让我们看看广达读者如何在下面的谜题中平衡这些品质。

谜题 1

你有八枚外观相同的硬币。一种是假冒的，比其他重量更轻，重量相同。在两次称重中找到坏硬币。找出在x重中可以找到假币的最大硬币数量的一般公式。

解决问题的简单版本通常会揭示解决方案的关键。在这种情况下，假设您只有三枚硬币，其中一枚比另外两枚轻。如果您将其中任何一个与其他两个中的一个进行权衡，它们要么会平衡，要么不会。如果他们不这样做，你知道哪个更轻。如果他们确实平衡，那么第三个是轻的。您只需要一次称量。

所以在这个谜题中，如果你能在第一次称重时分离出一组三个（或更少）包含轻硬币的，你只需要再称重一次。您可以通过平衡任何三个与任何其他三个来做到这一点。如果两组不平衡，则您已找到包含轻组的组，可以按上述方法进行第二次称重。如果它们保持平衡，只需将剩余的两枚硬币相互称重，您就会找到较轻的一枚。

请注意，如果未称重的组中有三个，这也适用，所以我们可以从九个硬币开始。按照这个逻辑，从三个硬币开始，每增加一个重量，我们就可以在之前拥有的硬币数量的三倍中找到轻硬币。因此，在w称重中给我们最大硬币数量n的公式是n = 3 ^w 。

谜题 2

你有 12 个外观相同的硬币。一个比其他具有相同重量的更重或更轻。

1. 在三个称重中找到坏硬币。

2. 您可以在四分之一的称量中找到坏的硬币的最大数量是多少？描述如何找到假硬币。

Ted很好地描述了这个难题的解决方案，他还表明，您实际上可以在 3 次称重中检测出 13 枚硬币中的劣币。这是 Ted 的解决方案（在每种情况下都用凹痕分隔三个称量）：

首先称重 4 个硬币对 4 个硬币。

情况 1：如果不平衡，第二次称重时，在秤的两侧各放 2 个较重的一侧，较轻的一侧各放 1 个。

1a：如果不平衡，坏硬币要么是 2 个硬币仍然在较重的一面，要么是单个硬币仍然在轻的一面。

称量 2 枚可能较重的硬币，坏的一枚是两者中较重的一枚，或者如果它们平衡，则为轻的一枚。

1b：如果第二次称重是平衡的，则劣币是第一次称重较轻侧未使用的 2 枚硬币之一。

将它们相互称重，较轻的就不好。

情况 2：如果平衡，坏硬币是剩下的 5 个硬币之一。将其中的 3 个与已经称过的 3 个（已知 [是] 好的）进行称重。

案例 2a：如果不平衡，您知道坏硬币是这 3 种硬币中的一种，以及它是轻还是重。

第三个称重是任何两个相互对立的 – 如果不平衡，则识别坏硬币，如果平衡，则为三个中的最后一个。

情况 2b：如果第二次称重是平衡的，那么坏硬币就是剩下的 2 枚中的一枚。

将它们中的任何一个与已知的好硬币进行权衡。如果这个结果不平衡，这枚新硬币是坏的，你知道它是重还是轻。如果这个结果是平衡的，那么第 13 个硬币是坏的，但它是重还是轻是未知的（我们不需要知道，所以我们完成了）。

Ted还继续表明，四次称重的最大硬币数量是 40。这个谜题的公式是： n = (3 ^w − 1)/2。

对于剩下的谜题，广义公式仍在专业数学家的研究中，是已发表论文的主题，其中一些已被Rainer aus dem Spring引用。我将仅限于我们在谜题中考虑的少量硬币的解决方案，并且只会提到从这些案例中使用的方法自然得出的概括。

谜题 3

这是谜题 1 的变体。你再次有八枚外观相同的硬币，其中一枚比其他枚更轻。但是，现在您拥有三个刻度。其中两个尺度有效，但第三个被破坏并给出随机结果（有时是正确的，有时是错误的）。你不知道哪个秤坏了。需要多少重量才能找到轻硬币？

正如我们在问题 1 中看到的，这只需要两次称量，并且平衡良好。我们也知道两个好的天平总是一致的，所以如果我们只是在所有三个天平上重复每个称量，我们将按照读者的建议在六个称量中得到答案。如果我们尝试在较少的称量中进行，它会变得有点棘手。我们不能仅仅通过在两个秤上称量相同的硬币来识别一个好的秤，因为即使他们同意，两个秤中的任何一个都可能仍然是一个坏秤。 （这也表明错误信息或随机信息很容易混淆真相。）

其实这个问题可以解决，非常巧妙，只需要四次称量！ Rainer aus dem Spring使用似乎是为这个难题创建的新符号发布了解决方案。但在你去那里之前，我希望你想象一个我希望能让事情变得更直观的场景。

想象一下，您是一名侦探，正在调查一个小国的肇事逃逸事件，该国汽车的车牌只有两位数，仅使用数字 0、1 和 2。A、B 和 C 三个人观察到了这一事件。他们中的两个总是正确回答一个三选题，一个给出完全随机的答案。你不知道随机回答者是谁。你必须问他们每个人一个三选一的问题，然后选择一个绝对说真话的人以获得更多信息。

这是你如何做到的。问 A 第一个数字是 0、1 还是 2。假设 A 说 2。问 B 第二个数字是 0、1 还是 2。假设 B 说 1。然后让 C 在这三个陈述中做出选择：

• 只有A说的是实话。
• 只有B说的是实话。
• 两人都在说实话。

这个谜题是由俄罗斯数学家康斯坦丁·诺普发明的，他是硬币称重谜题的世界权威。他的许多论文都是俄文的，但您可以在他的合作者 Tanya Khovanova 的博客上找到几个硬币谜题（以及其他有趣的谜题）。

至于概括，我将留给你看，同样的方法是否适用于在 32 枚硬币中找到特殊硬币的类型，其中 16 枚是重的，16 枚是轻的。

谜题 5

你有n枚外观相同的硬币，其中一些是伪造的，而且比其他的更轻。你所知道的是，至少有一枚假币，而且普通硬币比假币多。你的工作是检测所有的假币。

至少有一枚轻硬币并且普通硬币比轻硬币多的事实使得这个谜题不像最初出现的那么复杂，至少对于小数字来说是这样。让我们来看看一到八枚硬币的称重次数。

对于一枚硬币和两枚硬币，第二个条件下不可能有轻硬币，因此不需要称重。

三枚硬币：只有一枚轻硬币。每个拼图 1 需要称重一次。

四枚硬币：只有一枚轻硬币。需要额外称重一次，因此w = 2。

五枚硬币：一到两枚轻硬币。这是第一个有趣的案例。问题是：我们应该用一枚硬币对一枚，还是两枚硬币对两枚？

如果我们权衡一对一，那么我们可以：

1. 两次不平衡称量：发现两枚硬币；我们完了。
2. 两个中的一个平衡称重：平衡的硬币必须是正常的，所以最后一个硬币需要另一个称重， w = 3。
3. 两次平衡称量：在第三次称量中，将之前每次称量中的一枚硬币与另一枚硬币进行称重。如果它们是平衡的，所有四个都是正常的，硬币5是轻的。我们完了; w = 3。如果它们不平衡，我们已经找到了两个轻硬币，并且我们完成了三次称重。

相反，如果我们用两个对两个来称重，我们仍然需要三个称重，因为我们必须区分硬币在任一侧可能不同或相似的可能性。将少量硬币组合在一起进行称重似乎与使用单个硬币进行称重相比没有任何优势。

这证明了：

六枚硬币：一到两个轻硬币； w = 4。

七枚硬币：一到三枚轻硬币； w = 5。

八枚硬币：一到三枚轻硬币； w = 6。这个解有一个简单的结构：

• 首先对一枚硬币对下一枚硬币进行四次称重。所有硬币都被使用。
• 最坏情况：所有四个称量都是平衡的（有两个相互平衡的轻硬币）。
• 接下来的两次称重：称重为 1 的硬币和称重为 2 的硬币；类似地，将一枚 3 重的硬币与一枚 4 重的硬币称重。
• 其中一个称量将是不平衡的，识别出两个轻硬币。我们完成了六次称重。

抱歉，我们的 0、0、1、2、3、4、5、6 的序列肯定不够有趣，无法提交给在线整数序列百科全书！

正如Jonas Tøgersen Kjellstadli指出的那样，对于小数，解决方案似乎是w = n − 2，但我们还没有证明这对于大数不会改变。在某个n处，使用多个硬币称重可能会开始做得更好，或者可能需要比n -2 更多的称重。我们可以简单地将八枚硬币的解决方案推广到所有 2 的幂，将n -2 作为所有 2 的幂的权重数量的上限。

Mark Pearson 讨论了这个问题与纠错码的相似性，并建议使用基于可能结果数量的信息论方法。使用这种方法， Mike Roberts为更一般的情况发布了一个下限， Rainer aus dem Spring得出了一个近似值。 Rainer 还发布了一篇已发表论文的上限，但指出该上限对于低n并不明显，因此对于我们上面考虑的小数字没有帮助。因此，对于七枚硬币，引用的范围为 4 到 16，而我们的答案 5 介于两者之间。 J. Payette为所有谜题提供了额外的数学参考和界限。

感谢所有参与的人。本月的洞察奖共同授予 Ted 和 Rainer aus dem Spring。恭喜！

下次见，了解新见解。