68年历史的移动沙发问题被解决

文摘   2024-12-05 08:25   加拿大  

这是我很久以前科普过[1]的一个问题,前情提要是:

(上图:《老师没教的数学》一书中关于移动沙发问题的章节)

1966 Leo Morser问:一个什么样的形状可以通过一个宽度为1的直角转角?这个形状的最大面积是多少?

这个问题类似于移动一个沙发通过转角,因此被称为移动沙发(Moving Sofa Problem)问题。

1968年,英国数学家John Hammersley给出了一个面积为 的形状,史称Hammersley沙发(如上图)。

1992年,Joseph Gerver找到了一个由18条线段组成的形状,把面积提高至2.2195,史称Gerver沙发:

2014年,业余爱好者Philp Gibbs用计算机程序,得到了与Gerver非常接近的结果。

2018年,Dan Romik证明此问题上界为2.37。

2024年7月,Deng Zhipeng[2]使用变分法,再次得到了与Gerver相同的结果。

以上这些结果都说明,Gerver的结果可能就是最优的,以上就是前情提要。

2024年11月2日,韩国延世大学的Jineon Baek上传了一份预印本论文[3],声称证明了Gerver沙发就是最优的沙发,从而解决了这个有58年历史的问题。

整篇论文长达119页,似乎就是Jineon Baek的博士学位论文。ChatGPT总结其要点如下:

这篇论文题为《Optimality of Gerver’s Sofa》(Gerver沙发的最优性),解决了一个经典数学难题——移动沙发问题。该问题研究如何在二维平面上通过一个单位宽直角走廊移动一块具有最大面积的连通平面形状(称为移动沙发)。作者证明了Joseph Gerver在1992年构造的沙发形状(面积为约2.2195)确实是这一问题的全局最优解。

论文的主要内容和贡献包括:

  1. 问题背景与定义

  • 移动沙发问题是由Leo Moser于1966年提出的,涉及运动规划和面积最大化两方面。
  • Gerver在1992年提出了面积为2.2195的候选解,但其是否为全局最优解一直未被证明。
  • 主要定理与结果

    • 作者证明了Gerver沙发在所有满足条件的移动沙发中确实具有最大面积。证明过程中无需计算机辅助,仅用到简单的数值计算。
  • 关键技术与方法

    • 单调沙发与上限估计:通过定义单调沙发和引入“凸面覆盖区域”的方法,作者将问题形式化为优化一个二次泛函的问题。
    • 注入性条件:引入了一种新性质,确保最大面积沙发的形状边界是一个Jordan曲线,从而可以利用Green定理计算面积。
    • 全局凹性:通过Mamikon定理和Brunn-Minkowski理论,证明了面积上界泛函在定义域上的凹性,确保了Gerver沙发的全局最优性。
  • 证明步骤

    • 通过对最大面积沙发的形状进行限制,逐步减少可能的候选解集合。
    • 证明Gerver沙发满足所有必要条件,包括注入性和局部最优性。
    • 构造面积的上界函数,并证明该函数在Gerver沙发处取最大值。

    其他术语我解释不了,不过看到一个有意思的“单调沙发”(monotone sofa)概念。它是Gerver提出的概念,它的大致意思如下。

    首先,我们把移动沙发过转角的过程,看做沙发不动,而是走廊转动的过程。比如,下图中,上排图片是沙发顺时针旋转过弯的过程。这个过程可以看做沙发不动,而是走廊逆时针转动的过程,如下排图片所示:

    那么最大沙发的形状就是所有这些走廊(Gerver称其为Supporting Hallway)的交集,Gerver把这个交集称为monotone sofa,单调沙发。叫它“单调”并非因为这个沙发不好看,而是因为在数学上,它符合“单调”的性质。虽然论文中没有直接指出Gerver所认为的单调性质,但至少有一点肯定的是,随着考察的走廊数量增多,对单调沙发的逼近过程总是单调的。

    基本上我对论文只能说这些了。这篇论文上传前,经过Dan Romik的审阅,我觉得其可靠度还是相当高的。唯一让人不太满意的是,这么一个相当美观的问题,有了一个不太美观的结果。为什么这个沙发偏偏是18段曲线相连?不能更平滑规整一些?

    但无论如何,这个有58年历史的问题能够被解决,也是数学中的一大进展。

    接下来可以考虑的一些相关问题有:

    既可以左转又可以右转的沙发有多大?目前最佳纪录由Romik发现:

    既可以左转又可以向上转的沙发体积有多大?可以上下左右过直角弯的沙发又是什么形状?这些问题还将等待人们去探索。

    最后是一些不切实际的联想:

    看到2017到2021年论文作者在韩国服兵役,后来于2024年获取了博士学位。而我的《老师没教的数学》一书恰好在2020年出版了韩文版:

    这本书中介绍过移动沙发问题。那么有没有一种可能,论文作者在2020年看到了我的这本书从而选择了移动沙发问题这个课题呢?我无从考证,只是一些联想,哈哈!

    参考资料

    [1]

    科普过: https://yunqi.qq.com/read/31391889/8

    [2]

    Deng Zhipeng: https://arxiv.org/abs/2407.02587

    [3]

    印本论文: https://arxiv.org/abs/2411.19826

    大老李聊数学
    “大老李聊数学”(喜马拉雅FM自媒体节目)粉丝公众号,不定期发布节目相关知识,讨论各类趣味数学问题。
     最新文章