技术作者nor用GPT-6 Astra证明N=15至18及20的圆盘装圆最优解
此前仅N≤14和N=19获严格证明;nor称人类贡献包括确定可行性、引导模型、修复问题并手动验证,证明过程由5步几何论证构成。
技术作者nor使用GPT-6 Astra严格证明了「摆圆」问题中N=15、16、17、18和20这5种情况的最优性。此前,只有N≤14和N=19的情况已得到严格证明。
「摆圆」问题指:给定N个半径为1的圆盘和一个半径为R的大圆,将所有小圆盘完全放入大圆内且互不重叠,求大圆半径R的最小值。寻找最优排列之外,难点在于严格证明该排列已达到极限。
nor在博客文章中写道,他作为人类的贡献包括:确定问题的可行性、引导模型、与漏洞百出的网页用户界面作斗争、忍受糟糕的文案、修复细微问题、反复推敲阐述、手动验证其有效性,以及使用Astra和Opus 5.5重新检查所有内容。
证明如何推进
nor采取了循序渐进的方式:先让GPT-6 Astra处理N=15的情况,模型解决之后,再让它把同样的方法推广到16、17,以及18和20,GPT-6 Astra均成功给出证明结果。
据量子位报道,GPT-6 Astra的核心思路是:不再直接寻找最优解,而是通过几何约束把无限多种可能的排列缩减为有限的情况,再用计算机逐一排除,最终严格证明经典排列已经最优。
- 把靠外的圆盘推向边界,将圆盘分成边界上的一组和内部的一组
- 利用角度关系排除大量排列:如果某种排列要求的角度总和超过360°,就可以直接排除
- 让计算机枚举剩余可能,检查圆盘到圆心的距离区间及其环绕次序
- 用几何刚性证明精确最优,把「非常接近」提升为「严格一致」;15个圆盘的情况使用了另一种奇数环论证
- 还原原始排列,证明原始排列中必然至少有一个圆盘接触外圆边界,从而完成最优性证明
问题背景与进展
1968年,美国数学家葛立恒证明了N≤7的情况。1969年,数学研究者Udo Pirl把证明范围推进到10个圆盘,并进一步研究了11至19个圆盘的排列方案。一直到2003年前后,N≤14以及N=19的情形才被严格证明。
nor是一位长期研究数学、机器学习和优化算法的技术作者,多次公开参与AI辅助数学研究。他本人在十多年前就关注到了这个题目。他在博客中表示,N到20并非AI的极限,只是他没想着往下证。