返回

文章详情

N=17正方形打包的另一个更好的下界

Hacker News2026年8月21日 16:50

这个想法是改进近期的结果,并证明 4.5058 (?) ≤s(17) 使用这些权重:但我们首先得定义一下 s(17)。引用一下关于这个主题的旧文章:让 s(n) 表示我们可以打包 n 个单位正方形的最小正方形的边长。对于 n=16,以 4x4 的数组当然是最好的,因此 s(16)=4。对于 n=15,显然同样可以在 4x4 的正方形中围住这 15 个单位正方形,所以 s(15)≤4。证明更小的正方形并不明显。无论如何,埃里希·弗里德曼于 1999 年证明了这一点,因此 s(15)=4。对于 n=17,显然包围的正方形是 5x5,但在 1998 年,约翰·比德威尔发现了一个例子,显示一个边长为 4.6756… 的正方形就足够了,因此 s(17)≤4.6756… 这是一个非常有趣的正方形排列,所以值得去查看这个集合以及其他数字的版本。另一方面,特雷弗·格林于 2000 年证明了 4.4452…≤s(17)(更多细节稍后)。因此存在一个巨大的间隙 4.4452…≤s(17)≤4.6756… 几周前,萨姆·伯恩斯使用 ChapGPT 5.6 Sol 改进了下界。新的界限仍未经过社区的审查。我看了一下,它非常合理,我认为是正确的,但我可能在证明或附带的程序中遗漏了某个小角落案例,或者可能遗漏了一个巨大的漏洞。我会在数字旁边加个小 (?) 以防万一,但我相当乐观并且自信这是正确的,所以我只会使用半个字号。因此,目前的下界是 4.4452…≤4.4811 (?) ≤s(17)≤4.6756… 我对萨姆·伯恩斯的主要异议是这确实值得一个漂亮的图形!所以我的第一步是给这里添加一个好图形。另外,经过对程序的几次改进,我找到了一个新的下界,即 4.5058。因此我们现在有 4.4452…≤4.4811 (?) ≤4.5058 (?) ≤s(17)≤4.6756… 我新的例子和代码的修改在这里,但关于寻找新下界的更多技术细节属于第二篇文章。特雷弗·格林的下界。特雷弗·格林的旧证明的想法是 (19+40*sqrt(2))/17≅4.4452…≤s(17),选择了在边长为 4.4452… 的正方形中选取 16 个非常有趣的“不可避免”的点,然后他利用大量几何证明任何单位正方形必须包括其中至少一个。因此,如果我们尝试在这里放入 17 个单位正方形,至少两个单位正方形必须共享 16 个有趣点中的一个。这个构造从 4x6 网格中选择 16 个点。我只找到了旧文章中点的图像,但找不到其解析定义。查看正方形的边长公式,使用某个规则和一些猜测,我认为空的左右边距为 0.5,空的上下边距为 sqrt(2)-1/2≅0.9142… 使用这些选择,原始图形中的对角线段长度为 1,这是一个非常有用的数字,可以构建具有不可避免点作为顶点的三角形。(我很乐意听到确认。)它使用了一个 6x4 网格,空边距为 0.9142… 和 0.5000,网格的总尺寸为 2.6168… 和 2.4452…。为了将这个构造与更新的构造进行比较,最好将其对称化。在这个对称版本中,每个单位正方形至少包括 4 个点,但有些点更粗,它们算作双倍点(稍后提供更多细节)。萨姆·伯恩斯的下界。萨姆·伯恩斯使用 ChatGPT 发布的证明 4.4811 (?) ≤s(17) 的想法是选择 268 个在边长为 4.4811 的正方形中相对有趣的点。这些点具有不同的权重,总权重只有 16.9476。经过一些简化,仅需测试有限数量的方向,他们使用 Python 编写的程序测试“所有”可能的“几乎单位”正方形(实际上为 .9973),并验证每个正方形内部的权重和至少为 1(实际上为 1.0003)。因此,如果我们尝试在这里放入 17 个单位正方形,至少两个单位正方形必须至少共享 268 个相对有趣的点中的一个。(更多细节见第二篇文章。)这种方法有误报。如果它验证了一个解,则它肯定是正确的,但如果程序失败,则有微小的可能性是错误的。这是确保权重证明下界的好方法。不清楚这些权重是如何选择的。将这个解决方案与旧文章中的所有例子进行比较,0.5 的边距太窄,因为大多数例子使用 ~1.0 或 ~9.1 或类似的东西。权重的选择与我一致,网格的第一行/最后一行/列的所有权重为零。在我简单的理解中,倒数第二行/列也应该为空,但网格中的(1,11)非零权重,希望在更好的例子中不必要。倒数第三行/列相当满。它更靠近边界,而不是在旧示例中,所以看起来在边界附近添加更多点可能是提升下界的好主意。我使用 Racket 和 Metapict 包绘制图像。每个圆的半径根据权重计算为 r = sqrt(weight^(1/gamma)) * scale 其中 gamma = 1.0 的面积与权重成正比,但小的边距可以影响结果。

赞助内容

NordVPN Next-gen Antivirus

本站免费、广告极少。如果觉得有帮助,可以请我们喝杯咖啡 —— 任何金额都对持续运营有实际帮助。

请我喝杯咖啡