Fork me on GitHub

一个退休程序员,用高中几何方法,让百年数学难题逼近理论极限

  十三 赖可 发自 凹非寺
  量子位 报道 公众号 QbitAI

  试想一下,如果你的裤子破了好几个洞,每个洞形状各异,但是宽度都不超过 1 厘米。

  该如何设计一个通用的补丁,能够把所有的洞都补上呢?

  这个问题在数学上叫做:万有覆盖问题(universal covering problem)

  已经让数学家思考了一百年。

  乍一听上去,这像是一个很简单的问题。

  但是稍微想一想,似乎又不那么简单。

  比如一个边长为 1 的等腰三角形,和一个直径为 1 的圆形,两者的直径都为 1。

  但是,这个三角形就不能被圆形覆盖。

  而最近,一个退休程序员,用高中方法取得了最新进展。

  为什么这么难?

  这个难题的的提出者,法国著名数学家:勒贝格(Henri Léon Lebesgue)。


Henri Léon Lebesgue

  他提出了勒贝格积分,拓宽了积分学的研究范围。

  在 1914 时,他给好朋友 Julius Pál(也是数学家)写信时提了一个问题:

在一个平面上,找一个最小区域,让它可以覆盖直径不超过 1 个单位的面积?

  直径不超过 1 个单位的任意形状,就是一个封闭曲线的边缘上,最远两点的距离不超过 1 个单位。

  这个问题最难的部分是:

无法穷举所有直径为 1 的形状到底长什么样子

  直径为 1 的形状千千万,到底用哪种万能补丁才能全部覆盖它们呢?

  万有覆盖“通用”方法

  但是这个问题并不难上手,只要你有高中数学基础,就可以试一下。

  接下来,让我们一起看看数学家们目前解决这个问题的方法。

  从直径为 1 的需要覆盖的区域R入手。

  虽然不知道R长什么样子,能够确定的一点是:它绝对不会超过 1 个单位的宽度。

  那么就先假设它有 2 个点——A和B,距离为 1 个单位。

  现在,我们假设除了A和B之外,在R区域内还存在一个点C。

  那么C可能在哪里呢?

  它不可能大于A的 1 个单位,这意味着它必须在以A为圆心且半径为 1 的圆中。

  但另外一个问题是,C和B的距离也不能超过 1 个单位。

  所以C也必须在以B为圆心且半径为 1 的圆中。

  所以,C的位置就确定在了两个圆形的交集位置。

  到A和B的距离不能超过1,这一条件不仅仅适用于点C,还适用于区域R中的每个点。

  所以R中的每一个点都必须位于这两个圆的交集区域中。

  换句话说,这个区域可以覆盖直径为 1 的所有可能的R集,是一个万有覆盖区域

  但是这个区域不是最小面积,需要对它进行一下修剪。

  注意,圆的相交点形成两个等边三角形,顶点分别是是A、B,以及距离 AB 中点垂直距离为√3/2 的上下两个点。

  因为√3/2 大于1/2,我们可以画两条平行线,与 AB 平行,距离 AB 1/2 个单位。

  现在,考虑下图中红色的区域。

  因为两个平行线之间的距离为 1 个单位,所以直径为 1 的集合不可能同时出现在两个红色区域。就可以去掉一个。

  这样万有覆盖面积从原来的(2π/3)-(√3/2)≈1.228,减少到(π/2)-1/2≈1. 071

  从一个基本的万有覆盖开始,可以通过去掉一个无关紧要的部分,来缩小它的面积

  这就是数学家们得到最小万有覆盖的方法

  优化方法:Pál六边形

  通过更先进的技术,我们还能找到一些其他的简单形状。

  Pál利用定宽曲线的特性表明:

即使直径为 1 的一组曲线,可能会从直径 1 的圆中“伸”出来,它也总是可以通过移动或旋转,以适应围成这个圆的六边形。

  下图就展示了Pál提出的,可以覆盖各种形状(直径为1) 的六边形。

  上图中间的形状是一个勒洛三角形(Reuleaux triangle),这是一个与我们上一小节提到的万有覆盖密切相关的定宽曲线。

  勒洛三角形是一个弧三角形,通过三个相同的圆可以获得。

  这个六边形的面积是√3/2≈0. 866,比我们上小节所得到的面积还要小。

  但Pál也表示,并不需要整个六边形。

  他通过巧妙的旋转,去掉了一些无关部分。

  首先,将两个Pál六边形堆叠在一起。

  其中一个六边形绕中心旋转 30 度。

  出现了 6 个红色小三角形。

  每个红色小三角形,都处在未旋转六边形的外部,以及旋转六边形的内部。

  由于每个六边形平行对边的距离是 1 个单位,所以对着的两个红色小三角形中的点距离肯定大于 1 个单位。

  也就是说,一组直径为 1 的形状不可能同时出现在两个相对的红色小三角形中。

  按照上一小节的思路,可能会觉得应该能从 6 个小三角形去掉 3 个小三角形,但实际上是不行的。

  因为一个六边形旋转 60 度,或者对称翻转一下,都不会发生形状的改变。

  所以从相对的一对中选择一个红色三角形只有两种不同的方法:

3 个三角形可以是连续的,也可以是交替的。

  但是,我们可以去掉 2 个这样的小三角形。Pál就是这么做的。

  他从他的六边形上切下两个三角形,得到一个保证能覆盖所有直径为 1 的区域的新形状。

  这种新的万有覆盖的面积是2-2/√3≈0. 8453,比六边形面积略小一些。

  但是Pál六边形并不是最优解。

  在此基础上,数学家和数学爱好者们继续修修剪剪。

  在 1992 年,数学家 Roland Sprague 和 HC Hansen 在Pál六边形上减去了三个小细条。

  使面积缩小为0. 844137708416

  Sprague 减少了 0.001 单位面积,Hansen 减少了 0.00000000004 单位面积。

  退休程序员用高中几何,两次逼近极限

  然后二十年过去了,这个问题毫无进展。

  直到 2014 年,一位叫做 Philip Gibbs 的退休软件工程师尝试解决这个数学问题。

  他利用自己的编程背景优势,尝试用电脑解来解决。


Philip Gibbs

  Gibbs 首先对 200 个随机生成的直径为 1 的形状进行了计算机模拟。

  这些模拟结果表明,他或许能够修剪一个最小万有覆盖空间顶部角落的一些区域。

  随后,他证明了新的覆盖对所有可能的直径为 1 的形状都适用

  2015 年 2 月,Gibbs 和两位共同研究者将论文发表在了网上。


论文地址:https://arxiv.org/abs/1502.01251

  他们把最小万有覆盖面从 0.8441377 减少到0. 8441153单位面积。

  他的策略是将所有直径为 1 的形状移到他早些年发现的万有覆盖的某一角。

  然后把对角部分剩下的任何区域都去掉;然而从节省面积测量的角度来说,却是非常精确的。

  虽然此次减小的单位面积只有 0.0000224,但这却几乎是汉森在 1992 年减少的面积的100 万倍

  然而,这并未阻止他进一步的“裁剪”。

  2018 年 10 月,Gibbs 独自又发布了一篇文章,再次将最小万有覆盖面积缩小


论文地址:https://arxiv.org/abs/1810.10089

  要知道,在 Gibbs 的基础上再缩小覆盖面积实属不易。正如来自加州大学河滨分校的数学家约翰·贝兹所说:

你不可能真的把这些碎片画出来,因为他们都是原子大小的。

  而 Gibbs 却再次突破了极限,堪称原子剪刀

  这一次他的着手点是上图中的点A和点E。

  最终,通过这次研究,得到的最小面积就是0. 8440935944

  值得一提的是,实验方法基本都属于高中几何知识

  正如贝兹所评价:

从数学角度来说,这只是高中几何难度,但是它几乎让人为之疯狂。

  极限挑战,仍将继续

  问题虽然还没有最终解决,但是在 2005 年的时候,有数学家计算出了这个问题的理论下限,万有覆盖范围不能小于0. 832单位面积。

  抵达终点最后一步步依旧等待人来跨越,困难之处依旧在于,直径唯一的形状千变万化,最后给出的范围需要涵盖所有可能性。

  如果你做到了,名字就将载入数学史。

来自:
量子位(ID:QbitAI)

作者:Johnson
原创文章,版权所有,转载请保留原文链接。