破洞牛仔裤中的几何学：简单理解万有覆叠问题

数学算法俱乐部

日期 ： 2021年06月05日

正文共 ：3514字

来源 ：机器之心

对于特定宽度的几何形状，我们是否可以找到一个面积最小的能覆盖所有可能形状的特定形状？这个名为「万有覆叠」问题的答案还不为人所知。但通过高中几何，我们可以离它更近一步。

「嘿，我的牛仔裤破洞了。你能帮我补一补吗？」你的朋友正发消息向你寻求帮助，他知道你的针线活做得很不错。

「没问题，那很简单。」你回复说，「这些洞有多大？」

「它们形状都很奇怪，但宽度都不超过一英寸。我待会儿就到，请做好准备！」

你在你的针线包中拿出一些圆形补丁，每个都是直径 1 英寸。「这个应该能行。」你这样想。但真是如此吗？直径为 1 英寸的圆形补丁真的可以覆盖任何方向上都最大为 1 英寸的任何洞吗？

你在你的针线包中看到了另一块补丁——一个边长为 1 英寸的等边三角形。你观察到这个三角形中任何两个点之间的距离都不超过 1 英寸，所以你朋友的牛仔裤上的洞可能是这个形状的。但当你想用一个圆形补丁来覆盖它时，你发现这个圆形补丁只能遮住三角形的两个顶点，第三个顶点则伸在外面。

基本的几何计算也能确认这一点：三角形的高为 √3/2 英寸，大于圆的半径 1/2 英寸。因此，这个圆无法完全遮盖这个三角形，而这个三角形也无法遮盖这个圆。因为一个洞可以是其中任何一种形状，所以这就意味着这两种补丁无法应对你朋友牛仔裤上每一种可能性的破洞。

为了确保可用，你可以直接使用一个非常大的补丁，但你可不想浪费宝贵的布料。那么问题来了：如果要遮盖一个宽度最大为 1 英寸的洞，所需的最小补丁应该是怎样的？其实这也是当今的数学家们正在探索的一个问题：他们已经找了最小面积的通用覆盖形状 100 多年。他们还没有找到答案，但近期的研究结果已经让我们离这一理想形状更近了一步。

这个问题被称为万有覆叠问题（universal covering problem），最早由数学家昂利·勒贝格（Henri Lebesgue）于 1914 年写给其朋友数学家久拉·帕尔（Julius Pál）的一封信中提出。该问题可以用多种不同的方式表述，但其核心概念是直径为 1 的一个区域：这是平面上的一个点集，其中任何两个点之间的距离都不超过 1 个单位，就像我们的牛仔裤缝补问题中宽度不超过 1 英寸的破洞一样。

如果一个点集可以放在另一个点集中，那么我们就说第二个点集能「覆叠」第一个，就像一个补丁能覆盖一个洞。「万有覆叠」是指能用一个区域覆盖满足某个条件的形状（就像直径为 1 的所有形状）的整体集合。勒贝格的万有覆叠问题问的是如何找到能做到这一点的最小凸区域。（「凸」的大概意思是覆盖形状没有凹陷，「最小」则是指面积最小。）

你可能很惊讶，这个看似如此简单的问题竟然 100 多年了还未得到解决。这个问题为什么这么困难？部分原因是我们难以完全确定直径为 1 的所有形状。正如我们之前所见到的那样，对于我们难以完全想象的事物，要证明相关的定理是极其困难的。

在覆盖直径为 1 的形状方面，我们已经知道很多形状都能完成这项任务，但我们所知的形状都不是最小的。我们来简单了解一下为什么数学家难以解决这个问题。

首先，我们将直径为 1 的区域记为 R。我们并不清楚 R 可能是什么样子；我们只知道就像我们试图覆叠的洞一样，它的宽度永远不超过 1 个单位。但既然其直径为 1，那么我先定义两个点 A 和 B，并使它们之间的距离为 1 个单位。

现在，假设 R 包含第三个点 C。那么 C 可能位于什么位置呢？它与 A 的距离不能超过 1，也就是说它肯定在以 A 为圆心的半径为 1 的圆盘之内。你可以使用圆规画出这个范围。

同时，C 与 B 的距离也不能超过 1，所以其也位于以 B 为圆心的半径为 1 的圆盘内。同样可以继续画出。

这就意味着 C 点必然位于这两个圆盘的重叠区域中。

这个论证不仅适用于点 C；而且适用于 R 中每个可能的点。因此 R 中的每个点都必然位于这两个圆的交集之中。换句话说，这个区域能够覆盖直径为 1 的每个可能区域 R，因此这是一个万有覆叠区域。

但这个万有覆叠区域并不是最小的。我们来将其修建一下。

注意，这两个圆的交集中有两个同时包含 A 和 B 点的等边三角形。每个三角形的高都为 √3/2。

因为 √3/2 > 1/2，所以我们可以在离 AB 线相距 1/2 的位置画两条平行线，如下所示：

我们先来看看下图中用红色标识的两个区域。

因为这两条平行线之间的距离为 1，所以直径为 1 的区域不可能同时出现在两个红色区域中。所以我们其实不需要同时具备两者就能得到一个通用覆叠区域。那么我们去掉其中一个。

我们原来的覆盖区域（两个圆的重叠区域）的面积为

，现在的新区域的面积则为

。从一个初级万有覆叠区域开始，我们可以通过移除多余的部分来找到更小的区域。

这实际上正是数学家找到当前的最小万有覆叠区域的方法。使用更加先进的技术，我们可以一开始先找到其它简单一些的形状。举个例子，可以证明 1×1 的正方形是一个万有覆叠区域。对于勒贝格提出的这个难题，帕尔的回应是使用所谓的等宽曲线（curves of constant width）的性质——即使直径为 1 的区域可能会伸出直径为 1 的圆，但这个区域必然能够拟合到与该圆相切的正六边形中：

下面我们展示了帕尔给出的六边形所覆盖的几种不同的直径为 1 的形状。其中中间那个形状被称为勒洛三角形（Reuleaux triangle），这是一个与我们上面构建的例子密切相关的等宽曲线。（在上面的例子中，我们可以用圆规以两个圆的上面一个交点为圆形，以 1 为半径画出 A 和 B 点之间的圆弧，即可得到一个勒洛三角形。）

这个六边形的面积为 √3/2≈ 0.866，比我们上面构建的区域小，也小于边长为 1 的正方形的面积。但帕尔也证明我们并不需要整个六边形。通过以下巧妙的证明，他发现这个六边形的某些部分可以去除。

首先，我们先将两个帕尔六边形重叠在一起。

并将其中一个绕中心旋转 30 度。

这种操作能创造很多有意思的结果——比如这两个六边形的重叠区域是一个正十二边形。但我们最感兴趣的是红色所示的六个小三角形。

每个红色小三角形都位于原始六边形中，又位于旋转后的六边形之外。因为每个六边形的每对对边之间的距离都是 1 个单位，所以位于两个相对的红色三角形中的点之间的距离必然都超过 1。正如之前的论述：因为直径为 1 的区域不可能同时出现在两个相对的三角形区域中，所以万有覆叠区域无需同时具备它们。那么我们就可以移除其中一些。乐观估计，我们可以移除其中三个：每一对去掉一个。但不幸的是，我们不能在移除三个三角形之后还能处理直径为 1 的所有可能形状。为什么呢？

正六边形可以在旋转 60 度后与自身重合，也可以沿对称线翻转之后与自身重合，所以从每对相对的三角形中选出一个实际上只有两种不同的方式：要么是连续选择，要么是交替选择。如下图所示，其中加点的三角形是直径为 1 的区域可能占据的三角形。

如果我们需要覆盖的集合包含了三个连续的三角形（如左图所示），那么其无法覆叠我们通过交错方式去掉三个三角形的形状（如右图所示）。反过来也一样，如果我们覆盖的集合包含三个交错的三角形，那么结果又无法覆叠有三个连续三角形的情况。因此，无论以哪种方式移除三个三角形，都会有一个直径为 1 的形状集合无法覆叠。也就是说，我们不能移除三个红色三角形。

但我们可以移除两个。如果我们移除两个既不相邻也不相对的红色三角形，则上述两个有问题的集合都能被覆盖。这也正是帕尔的做法。

帕尔从那个正六边形切除了两个三角形，得到了一个新形状，并证明这个形状能覆盖所有直径为 1 的区域。这个新的万有覆叠区域的面积为

，略小于帕尔六边形。

削减还在继续。数学家 Roland Sprague 和 H.C. Hansen 分别在 1936 和 1992 年都分别成功移除了更小的区域。几年前，业余数学家 Philip Gibbs 受数学家 John Baez 的一篇博客文章的启发，提出了一些新的可切除部分。他与 Baez 和另一位合作者一起将 Sprague 和 Hansen 的技术进行了归纳，实现了对形状的进一步切割，为直径为 1 的最小凸区域面积大小创造了新的世界最小记录。很快 Gibbs 本人又进一步推进，成功切除了更多部分。

好消息是我们不断找到帕尔六边形上新的可切除部分。坏消息是这些部分都非常小。Sprague 将区域面积减小了大约 0.001 平方单位，Hansen 则仅减小了 0.00000000004 平方单位。Gibbs 及其合作者在 Hansen 的基础上又减小了大约 0.00002 平方单位，相比而言已经是相当大一块了。

面积还能继续减小多少？2005 年，Peter Brass 和 Mehrbod Sharifi 已经证明万有覆叠区域面积不可能低于 0.832 平方单位（http://www.cs.cmu.edu/~mehrbod/UC05.pdf），所以我们知道再切也不能切太多了。但如果你可以想出新的技术或新的起点，你也许还能让我们进一步接近那个最小的万有覆叠区域，把你自己也切进数学史中。只要记住一点，这个问题最难的部分是思考直径为 1 的区域的无限多种可能的形状。如果你也打算研究这个问题，一定要确保能够覆盖所有的可能性。

参考链接：

https://www.quantamagazine.org/how-simple-math-can-cover-even-the-most-complex-holes-20200108/