数字 15 描述了无限网格的秘密极限

作为智利大学的一名本科生， 贝尔纳多·苏贝卡索 对使用计算机做数学持模糊的看法。 它似乎与真正的知识发现背道而驰。

“有一些本能或直觉的反应反对使用计算机来解决你的问题，就像它违背了一个奇妙论点的理想之美或优雅，”他说。

但随后在 2020 年，Subercaseaux 坠入爱河，而且经常发生的是，他的优先事项发生了变化。 他着迷的对象是他在网上论坛上看到的一个问题。 大部分问题他扫过就忘了，但这一个引起了他的注意。 他向右滑动。

“我做的第一件事就是在 Facebook 群组中点赞帖子，希望稍后当其他人发布解决方案时能收到通知，”他说。

问题是关于用数字填充无限网格。 事实证明，这不是那种可以随心所欲解决的问题。 为了做到这一点，Subercaseaux 不得不离开智利前往卡内基梅隆大学攻读研究生。

在那里，2021 年 XNUMX 月，他与 马林赫勒，一位计算机科学家，使用强大的计算能力来解决数学难题。 Subercaseaux 问 Heule 是否想尝试这个问题，开始了一项合作，该合作在今年 XNUMX 月达到高潮 证明 可以用一个数字来概括：15。

千方百计

2002年， 韦恩戈达德 克莱姆森大学的和一些志同道合的数学家正在组合学中吐口水，试图对这个领域的主要问题提出新的转折，即给定某些约束给地图着色。

最终他们找到了一个从网格开始的问题，就像一张永远持续下去的方格纸。 目标是用数字填充它。 只有一个限制条件：同一数字每次出现之间的距离必须大于数字本身。 （距离是通过将垂直和水平间距加在一起来测量的，这种度量称为“出租车”距离，因为它类似于在网格化城市街道上移动的方式。）一对 1 不能占据相邻的单元格，它们的出租车距离为 1，但它们可以放置在距离为 2 的直接对角线单元格中。

最初，戈达德和他的合作者想知道是否有可能用有限的数字集填充无限的网格。 但当他和他的四个合作者 发布了这个“包装着色”问题 在杂志 组合艺术 2008年，他们证明可以用22个数来解决。 他们也知道，光靠五个数字是解决不了的。 这意味着问题的实际答案——所需的最少数字——介于两者之间。

研究人员实际上并没有填充无限网格。 他们没有必要。 相反，只需要取一小部分网格——比如一个 10×10 的正方形——用数字填充它，然后显示填充子集的副本可以彼此相邻放置，就像你覆盖一个地板与瓷砖的副本。

当 Subercaseaux 第一次得知这个问题时，他开始使用笔和纸寻找瓷砖。 他会画出数字网格，把它们划掉，再试一次。 他很快就厌倦了这种方法，于是请一位朋友设计了一个类似于扫雷游戏的基于网络的工具，让他可以更快地测试组合。 经过几个星期的工作，他确信自己没有办法用八个数字组成一个网格，但他不能再进一步了——瓷砖可以采用的潜在形状太多了，而且太多了他们可以用不同的方式填充数字。

问题，正如后来变得清晰的那样，证明网格不能被一组特定的数字覆盖比证明它可以覆盖要困难得多。 “这不仅表明一种方法行不通，而且表明所有可能的方法都行不通，”戈达德说。

Subercaseaux 在 CMU 开始工作并说服 Heule 与他一起工作后，他们很快找到了用 15 个数字覆盖网格的方法。 他们还能够排除仅用 12 个数字来解决问题的可能性。 但他们的胜利感是短暂的，因为他们意识到他们只是重现了已经存在很长时间的结果：早在 2017 年，研究人员就知道答案不小于 13 或大于 15 .

对于一个拉拢一位知名教授来解决他的宠物问题的一年级研究生来说，这是一个令人不安的发现。 “我吓坏了。 我基本上已经在一个问题上工作了几个月而没有意识到这一点，更糟糕的是，我做了 Marijn 浪费他的时间！ 潜艇 写 在一篇回顾他们工作的博客文章中。

然而，Heule 发现过去的结果令人振奋。 这表明其他研究人员发现这个问题足够重要，可以继续研究，并向他证实，唯一值得获得的结果就是彻底解决这个问题。

他说：“一旦我们发现这个问题已经进行了 20 年的工作，情况就完全改变了。”

避免粗俗

多年来，Heule 一直致力于寻找有效的方法来搜索大量可能的组合。 他的方法称为 SAT 求解——“可满足性”的缩写。 它涉及构造一个长公式，称为布尔公式，它可以有两种可能的结果：0 或 1。如果结果为 1，则公式为真，问题得到满足。

对于包装着色问题，公式中的每个变量可能表示给定单元格是否被给定数字占用。 计算机寻找分配变量的方法以满足公式。 如果计算机可以做到，您就知道可以在您设置的条件下打包网格。

不幸的是，将填充着色问题直接编码为布尔公式可能会扩展到数百万项——一台计算机，甚至一组计算机，可能会永远运行，测试其中分配变量的所有不同方式。

戈达德说：“如果你天真地尝试使用这种蛮力，直到宇宙终结为止。” “所以你需要一些很酷的简化来将其简化为甚至可能的东西。”

此外，由于可能的组合相乘的方式，每次在包装着色问题中添加一个数字，它就会变得困难大约 100 倍。 这意味着如果一组并行工作的计算机可以在一天的计算中排除 12 个，则它们需要 100 天的计算时间才能排除 13 个。

在某种程度上，Heule 和 Subercaseaux 认为扩大蛮力计算方法是粗俗的。 “我们有几个有前途的想法，所以我们的心态是‘让我们尝试优化我们的方法，直到我们可以在集群上用不到 48 小时的计算解决这个问题，’”Subercaseaux 说。

为此，他们必须想出办法来限制计算集群必须尝试的组合数量。

“[他们] 不仅要解决它，而且要以令人印象深刻的方式解决它，”说 亚历山大·索弗 科罗拉多大学科罗拉多斯普林斯分校。

Heule 和 Subercaseaux 认识到许多组合在本质上是相同的。 如果你想用八个不同的数字填充菱形瓷砖，你放置的第一个数字是一个在中心方块的右边一个，还是一个在中间方块的左边一个，都没有关系。中心广场。 这两个位置彼此对称，并且以完全相同的方式限制您的下一步行动，因此没有理由同时检查它们。

Heule 和 Subercaseaux 添加了允许计算机将对称组合视为等价组合的规则，从而将总搜索时间减少了八分之一。 他们还采用了 Heule 在之前的工作中开发的一种技术，称为立方体和征服，这使他们能够同时测试更多的组合。 如果您知道给定的单元格必须包含 3、5 或 7，您可以拆分问题并在不同的计算机组上同时测试三种可能性中的每一种。

到 2022 年 13 月，这些改进使 Heule 和 Subercaseaux 能够在需要不到两天计算时间的实验中排除 14 作为包装着色问题的答案。 这给他们留下了两个可能的答案：15 或 XNUMX。

一大优点

为了排除 14 个——并解决问题——Heule 和 Subercaseaux 必须找到其他方法来加速计算机搜索。

最初，他们编写了一个布尔公式，将变量分配给网格中的每个单独的单元格。 但在 2022 年 XNUMX 月，他们意识到他们不需要逐个单元地进行。 相反，他们发现考虑由五个加号形状的单元格组成的小区域更有效。

他们重写了他们的布尔公式，让几个变量代表问题，例如：在这个加号形区域内的某处是否有一个 7？ 计算机不需要确定 7 在该地区的确切位置。 它只需要确定它是否在里面——这个问题需要的计算资源要少得多。

“事实证明，让变量只谈论加号而不是特定位置比在特定单元格中谈论它们要好得多，”Heule 说。

在 plus 搜索效率的帮助下，Heule 和 Subercaseaux 在 14 年 2022 月的一项计算机实验中排除了 13 个，最终运行时间比他们用来排除 XNUMX 个的实验花费的时间更少。他们在接下来的四个月里验证了这一点计算机的结论是正确的——几乎与他们让计算机首先得出该结论所花费的时间一样多。

“令人欣慰的是，我们在一些随机期刊中作为一种附带问题产生的问题导致一群人花费了几个月的时间来试图找出解决方法，”戈达德说。

对于 Subercaseaux，这是他研究生涯中的第一个真正的胜利。 虽然这可能不是他最初考虑从事数学工作时理想化的发现类型，但他发现最终，它有其自身的智力回报。

“你给我一块黑板，我可以告诉你为什么是 15，这不是对表格的理解，”他说。 “但我们已经了解了问题的限制是如何运作的，这里有 6 或那里有 7 有多好。 我们获得了很多直观的理解。”