十三 赖可 发自 凹非寺
　　量子位 报道 公众号 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单位面积。

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

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