我们的 最近的一系列谜题 以简陋的双盘天平为特色，它在历史上是商业和政府、艺术和科学的象征。天平秤在娱乐数学中也很流行。平衡谜题需要清晰、逻辑推理，并且非常适合数学概括。让我们看看如何 广达 读者在下面的谜题中平衡了这些品质。
拼图1
你有八枚外观相同的硬币。 一种是假冒的，比其他重量更轻，重量相同。 在两次称重中找到坏硬币。 找出你可以在其中找到假币的最大硬币数量的一般公式 x 称重。
解决问题的简单版本通常会揭示解决方案的关键。在这种情况下，假设您只有三枚硬币，其中一枚比另外两枚轻。如果你将其中任何一个与另外两个之一进行权衡，它们要么会平衡，要么不会。如果没有，您就知道哪个更轻。如果它们确实平衡，那么第三个就是轻的。您只需要一次称重。
因此，在这个难题中，如果您可以在第一次称重中分离出包含轻硬币的一组三个（或更少），则您只需要再称重一次。您可以通过平衡任意三个与其他三个来做到这一点。如果两组不平衡，则找到轻的那一组，可以按上述方法进行第二次称重。如果它们平衡，只需将剩余的两枚硬币相互称重，您就会找到轻的一枚。
请注意，如果未称重的组中有三个硬币，这也适用，因此我们可以从九个硬币开始。按照这个逻辑，从三枚硬币开始，每增加一次称重，我们就可以找到轻质硬币，其数量是我们之前拥有的硬币数量的三倍。给我们最大硬币数量的公式 n in w 因此称量为 n = 3w.
拼图2
你有 12 个外观相同的硬币。 一个比其他具有相同重量的更重或更轻。
-
在三个称重中找到坏硬币。
-
您可以在四分之一的称量中找到坏的硬币的最大数量是多少？ 描述如何找到假硬币。
这个难题的解决方案被很好地描述了 特德，他还表明，实际上可以通过三次称重来检测 13 枚硬币中的劣质硬币。这是 Ted 的解决方案（在每种情况下都用缩进分隔三个称量）：
首先称量 4 个硬币与 4 个硬币的重量。
情况一：如果不平衡，第二次称重时，将较重的一侧各放 1 个，轻的一侧各放 2 个。
1a：如果不平衡，坏硬币要么是仍然在重的一侧的 2 个硬币，要么是仍然在轻的一侧的单个硬币。
称量 2 个可能较重的硬币，坏的硬币要么是两个硬币中较重的，要么是单个较轻的硬币（如果它们是平衡的）。
1b：如果第二次称重平衡，则坏硬币是第一次称重较轻一侧中未使用的 2 个硬币之一。
互相称一下，轻的不好。
情况2：如果平衡，坏币就是剩下的5枚硬币中的一枚。将其中的 3 个与已称重的任何 3 个（已知为良好）进行比较。
情况 2a：如果不平衡，您就知道坏硬币是这 3 种硬币之一，无论它是轻的还是重的。
第三次称重是其中任何两个相互对比——如果不平衡，则识别出劣币，如果平衡，则为三者中的最后一个。
情况2b：如果第二次称重平衡，则劣币为剩余2枚中的一枚。
将其中任何一个与已知的优质硬币进行称重。如果这个结果不平衡，这枚新币就是坏币，你就知道它是重还是轻了。如果这个结果是平衡的，那么第13枚硬币是坏的，但是不知道它是重还是轻（我们不需要知道，所以我们就完成了）。
特德 还继续表明，四次称重的硬币的最大数量是 40。这个谜题的公式是： n =（3w − 1)/2。
对于剩下的难题，专业数学家仍在研究广义公式，并且是已发表论文的主题，其中一些已被引用 春天的雷纳。我将只讨论我们在谜题中考虑的少量硬币的解决方案，并且只会提及从这些情况下使用的方法自然得出的概括。
拼图3
这是谜题 1 的变体。你再次有八枚外观相同的硬币，其中一枚比其他枚更轻。 但是，现在您拥有三个刻度。 其中两个尺度有效，但第三个被破坏并给出随机结果（有时是正确的，有时是错误的）。 你不知道哪个秤坏了。 需要多少重量才能找到轻硬币？
正如我们在问题 1 中看到的，这只需要两次称重并保持良好的天平。我们还知道，两个好的天平总是一致的，因此，如果我们只是在所有三个天平上重复每次称量，我们将按照读者的建议在六次称量中得到答案。如果我们尝试以较少的称重次数来完成，就会变得有点棘手。我们不能仅通过在两个秤上称量相同的硬币来确定秤的好坏，因为即使它们一致，两者中的任何一个仍然可能是坏秤。 （这也表明错误信息或随机信息很容易混淆事实。）
事实上，这个问题只需四次称重就可以非常巧妙地解决！ 春天的雷纳 使用似乎是为这个难题创建的新符号来发布解决方案。但在你去那里之前，我希望你想象一个场景，我希望这会让事情变得更直观。
想象一下，您是一名侦探，正在一个小国调查一起肇事逃逸案，该国的汽车有两位数车牌，仅使用数字 0、1 和 2。 A、B 和 C 三个人观察了这一事件。其中两人总是正确回答三选题，另一人给出完全随机的答案。您不知道随机回答者是谁。你必须问他们每个人一个三选题，然后选择一个绝对说真话的人以获得更多信息。
操作方法如下。问 A 第一个数字是 0、1 还是 2。假设 A 说 2。问 B 第二个数字是 0、1 还是 2。假设 B 说 1。然后要求 C 在这三个陈述中做出选择：
- 只有A说的是实话。
- 只有B说的是实话。
- 两人都说的是实话。
您可以相信 C 告诉您的那个数字，并向那个人询问另一个数字。要了解原因，请考虑如果 A 说谎，则 C 是可靠的并且会说 B 说的是真话。第二个数字实际上是 1，然后你可以向 B 询问第一个数字。同样，如果 B 说谎，那么 C 又是可靠的，并且会说 A 说的是真话。那么第一个数字实际上是 2，你可以向 A 询问第二个数字。最后，如果C在说谎，那么A和B都是可靠的，所以你仍然可以相信并选择C说的任何人。 （如果 C 说 A 和 B 都说的是真话，那么他们一定都是真话。）这里的关键是你所选择的问题不允许 C 说谎，从而对 A 和 B 都产生怀疑。由于 A 和 B 中至少有一个是可靠的，所以你总是可以选择 C 同意的一个，即使它只是一个随机答案。如果这三个数字都一致，那么您就已经拥有了车牌的两位数字。
以下是如何将这个故事转化为我们的谜题。刻度为 A、B 和 C。您可以将车牌的两位数字转换为硬币，如下所示：01 是硬币 1，02 是硬币 2，10 是硬币 3，11 是硬币 4，12 是硬币 5， 20 是 6 号硬币，21 是 7 号硬币，22 是 8 号硬币。精明的读者会认识到这是以 3 为基数（或三进制）的数字系统。另请注意，还有一个可能的数字 00，您可以将其用于第九枚硬币，该技术也适用于该硬币，如谜题 1 中所示。
第一次称重时，您将硬币除以第一个（以 3 为基数）数字，因此您的三组硬币将是 [1, 2]、[3, 4, 5] 和 [6, 7, 8]。在秤 A 上对 [3, 4, 5] 与 [6, 7, 8] 进行称重。如果 A 运行良好，您将获得正确的第一个数字组，如拼图 1 中所示。同样，对于在秤 B 上进行第二次称重，您的组将是具有相同第二个数字的那些：[1, 4, 7]、[2, 5, 8] 和 [3, 6]。如果 B 运行良好，您将得到正确的第二个数字。对于第三次称重，在秤 C 上，将 A 确定的组与 B 确定的组进行权衡。按照我们的示例，对于 21，组将为 [6, 7, 8] 和 [1, 4, 7]。硬币 7 不能同时放在两侧，因此我们将其省略并相互权衡 [6, 8] 和 [1, 4]。请注意，如果 A 和 B 都可靠，则 7 实际上是正确答案，并且 C 的哪一方重量轻并不重要。如果碰巧 C 的称重是平衡的，则所有三个秤都一致，并且只需称重三次即可得出答案（硬币 7）。如果 A 可靠而 B 不可靠，则较轻的硬币位于 [6, 8] 中，该范围 C 将确认；如果 B 可靠而 A 不可靠，则较轻的硬币位于 [1, 4] 中，该范围 C 确认也会确认。
因此，在三次称重中，我们要么确定了轻硬币，要么将其缩小到两个一组，并且我们还确定了工作规模。剩下的工作将在秤 A 或秤 B（以秤 C 同意的那个秤）上进行第四次称重。
这个解决方案让我觉得非常漂亮！
这个方法可以推广到寻找 3 个中的轻硬币2x 硬币 3x + 使用给定的一组天平秤进行 1 次称重。因此，您需要称量 81 次才能称量 1,000 个硬币。对于大量硬币 (>~XNUMX)，更强大的解决方案 存在.
拼图4
你有 16 枚硬币，其中 XNUMX 枚很重且重量相同。 其他八个很轻，重量相同。 你不知道哪些硬币是重的还是轻的。 除了带有特殊标记的硬币外，这些硬币看起来都一样。 有了一个好的秤，你能分清这枚特殊硬币的三重是轻还是重？ 您可以从多少硬币开始并在四次称重中成功解决这个问题？
正如我们的一位读者所总结的那样，乍一看，这个难题似乎几乎不可能通过三次称重来完成。然而，只要有一些聪明才智，这是可以做到的，而且 特德 和 春天的雷纳 提供了正确的解决方案。特德提供了一些值得关注的宝贵一般原则。
首先，除非您通过称重获得不平衡的结果，否则您将没有足够的信息来确定特殊硬币是重还是轻。所以你必须尝试强迫一个不平衡的结果。
其次，如果您得到平衡的结果（假设特殊硬币 A 平衡了硬币 B），您可以将平衡的硬币合并起来，并与另外两个硬币 C 和 D 进行称重。如果它们不平衡，您就会得到答案；否则，您将得到答案。否则，您现在已经将相似的硬币数量增加了一倍，这可能会帮助您在下次称重时得到不平衡的答案。如果您的初始不平衡结果如以下解决方案所示，您还可以使用 4 的幂（8、XNUMX 等）的硬币数量反向执行此过程。
以下是在所有情况下，在三次称重中可以识别特殊硬币A的类型的整个程序。 （B、C、D 是称量 1（W1）时与 A 放在同一侧的三枚硬币；X 和 Y 是 W1 中未使用的两枚硬币。）
这个谜题是俄罗斯数学家发明的 康斯坦丁·诺普，硬币称量谜题的世界权威。他的许多论文都是俄语的，但您可以在网上找到几个硬币谜题（以及其他有趣的谜题） 新闻 他的合作者坦尼娅·霍瓦诺娃 (Tanya Khovanova) 的作品。
至于概括，我将留给你看看同样的方法是否适用于在 32 枚硬币中查找特殊硬币的类型，其中 16 枚是重的，16 枚是轻的。
拼图5
你有 n 外观相同的硬币，其中一些是伪造的，并且比其他的更轻。 你所知道的是，至少有一枚假币，而且普通硬币比假币多。 你的工作是检测所有的假币。
事实上，至少有一枚轻质硬币，并且普通硬币比轻质硬币多，这一事实使得这个谜题不像最初看起来那么复杂，至少对于少量硬币来说是这样。我们来看看 XNUMX 到 XNUMX 个硬币的称量次数。
对于一枚和两枚硬币，第二个条件不可能有轻硬币，因此不需要称重。
三枚钱币：只有一枚轻币。每个拼图 1 需要称重一次。
四枚钱币：只有一枚轻币。需要额外称重一次，因此 w = 2。
五币：一到两枚光币。这是第一个有趣的案例。问题是：我们应该用一枚硬币对一枚硬币进行称量，还是用两枚硬币对两枚硬币进行称重？
如果我们一一权衡，那么我们可以得到：
- 两次不平衡称重：发现两枚硬币；我们完了。
- 两枚平衡称重：平衡后的硬币必须是正常的，因此最后一枚硬币需要再次称重， w = 3。
- 两次平衡称重：在第三次称重中，将之前称重的一枚硬币与另一枚硬币进行称重。如果平衡，则四个都是正常的，硬币 5 是较轻的。我们完了; w 又=3。如果不平衡，我们就找到了两枚轻币，分三次称重就完成了。
相反，如果我们以两对二进行称重，我们仍然需要进行三次称重，因为我们必须区分硬币两侧不同或相似的可能性。使用少量硬币组合在一起进行称重似乎与使用单个硬币称重相比没有任何优势。
这已得到证实：
六币：一到两枚光币； w = 4。
七币：光币一到三枚； w = 5。
八币：光币一到三枚； w = 6. 该解决方案结构简单：
- 首先将一枚硬币与下一枚硬币进行四次称重。所有硬币都被使用。
- 最坏的情况：四个称量全部平衡（有两个轻硬币相互平衡）。
- 接下来两次称重：分别称重 1 的一枚硬币和称重 2 的一枚硬币；同样，将重量为 3 的硬币与重量为 4 的硬币进行称重。
- 其中一个称重将是不平衡的，从而识别出两枚轻硬币。我们完成了六次称重。
抱歉，我们的 0, 0, 1, 2, 3, 4, 5, 6 序列肯定不够有趣，无法提交给 在线整数序列百科全书!
As 乔纳斯·托格森·谢尔斯塔德利 指出，解决方案似乎是 w = n − 2 对于较小的数字，但我们还没有证明对于较大的数字这不会改变。在一些 n，使用多个硬币称重可能会开始做得更好，或者比 n − 可能需要 2 个。我们可以简单地将 2 个硬币的解推广到 XNUMX 的所有幂，给出 n − 2 作为 2 的所有幂的称重次数的上限。
马克·皮尔森讨论了这个问题与纠错码的相似性，并建议使用基于可能结果数量的信息论方法。使用这样的方法， 迈克·罗伯茨 发布了更一般情况的下限，其中 春天的雷纳 推导出一个近似值。雷纳还发布了 上限 来自已发表的论文，但指出低值的界限并不尖锐 n 因此对于我们上面考虑的小数字没有帮助。因此，对于 4 个硬币，引用的界限给出的范围是 16 到 5，我们的答案 XNUMX 就落在这个范围之间。 J·帕耶特 为所有谜题提供额外的数学参考和界限。
感谢所有参与的人。本月的洞察奖共同授予 Ted 和 Rainer aus dem Spring。恭喜！
下次新的再见 行业洞见.
