返回资讯中心
外部精选
软件工程
#开发者实时流

数学爱好者用浏览器游戏呈现 Erdős 第659号问题的已验证最优解

来源标题:Show HN: A geometry puzzle from an Erdős problem, with every optimum proven

一个基于 Erdős 第659号问题的几何谜题网页游戏上线,玩家需在方格中放置点使距离重复出现,每个棋盘的最优解均经穷举分支定界搜索证明。该问题已于2026年1月由 Benjamin Grayzel 与 Gemini 合作解决,排除了最后一个例外情形。页面中每个正方形长度对应一根柱条,柱条越高表示共享该距离的点对越多。

Hacker News 最新hanczvs2026/11/16 · 今天8 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

每对点之间都有一个距离。把点摆好,让这些距离重复出现。每块棋盘都有一个已被证明的最小值。去达到它。

点击一个圆点即可放置或移除一个点。+2 表示新增两个距离;0 表示不增加新距离。

每条横条代表一个平方长度;横条越高,意味着共享该长度的点对越多。将鼠标悬停或点击横条,可以查看对应的点对,以及它们为何相等。

先放置两个点,形成你的第一个距离。

方阵网格上的点能很好地共享距离——好得过头了:正方形的四个角之间只有两个距离,即一条边和一条对角线。

Erdős 要求构造点集,使距离总数保持较低,同时任意四个点仍然至少确定三个距离。方阵网格会立刻违反这条规则。

将每一行拉伸 √2 倍,所有正方形就消失了,但距离仍几乎同样频繁地重复。这种格点此前已由 Moree 与 Osburn 以及 Lund 与 Sheffer 的工作所知。2026 年 1 月,Benjamin Grayzel 与 Gemini 合作,排除了最后一个可能的例外,从而解决了 Erdős 问题 #659。试试其他拉伸方式,看看哪些会失效。

对于每块棋盘和每个点数,穷举分支定界搜索已经检查过:不存在使用更少距离的排布。距离集合只会随点的加入而增大,因此,一个已经超出限制的部分排布,可以连同它的所有完成方式一起丢弃。这使得搜索规模小到足以完成。

7 × 7 棋盘上的 20 个点需要 17 个距离。选取这些点的方式共有 28,277,527,346,376 种。搜索在大约 170 万个节点后,用几秒钟就排除了 16 个或更少距离的情形。另一个 C 语言实现给出了相同结果。在这个项目的早期,同一块棋盘曾用局部搜索和五十万次邻域检查进行探测,但未能得出结论。

这些是某个有限拉伸网格的子集的最小值。它们并不说明平面中任意点的情况,也不是一个新定理。

本棋盘的证书 ↗ · 证明是如何运行的 ↗

标记为 (x, y) 的点位于 (x, √2 y)。两个网格点之间的平方距离是 dx² + 2dy²,始终是整数,因此两个长度相等当且仅当两个整数相等。其中不涉及浮点容差。

该网格上的任何选择都满足四点规则;仓库中的两个 Python 检查器也会枚举每块完整棋盘的每个四点子集。

导出的文件是供仓库中精确验证器使用的证书。保存文件并运行:

python3 -m few_distance verify witness.json

导出至少需要四个点。不会有任何数据离开你的浏览器:没有账户、服务器或分析工具。棋盘链接会把坐标存储在 URL 中。

发现了值得讨论的模式?请带上棋盘链接提交 issue ↗

Grayzel 的 "Solution to a Problem of Erdős Concerning Distances and Points"(2026)补全了对 Erdős 问题 #659 的解答。Moree 与 Osburn 统计了这种格点中的距离。那些数学成果属于他们;本项目只探索小型有限棋盘。

如果想追求相反的目标,可以试试 Oscar Cunningham 的 Unique Distancing Problem:让每个距离都不同。

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →