本文經(jīng)AI新媒體量子位（公眾號(hào)ID:QbitAI）授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)聯(lián)系出處。

試想一下，如果你的褲子破了好幾個(gè)洞，每個(gè)洞形狀各異，但是寬度都不超過1厘米。

該如何設(shè)計(jì)一個(gè)通用的補(bǔ)丁，能夠把所有的洞都補(bǔ)上呢？

這個(gè)問題在數(shù)學(xué)上叫做：萬有覆蓋問題（universal covering problem)。

已經(jīng)讓數(shù)學(xué)家思考了一百年。

乍一聽上去，這像是一個(gè)很簡(jiǎn)單的問題。

但是稍微想一想，似乎又不那么簡(jiǎn)單。

比如一個(gè)邊長(zhǎng)為1的等腰三角形，和一個(gè)直徑為1 的圓形，兩者的直徑都為 1。

但是，這個(gè)三角形就不能被圓形覆蓋。

而最近，一個(gè)退休程序員，用高中方法取得了最新進(jìn)展。

為什么這么難？

這個(gè)難題的的提出者，法國著名數(shù)學(xué)家：勒貝格(Henri Léon Lebesgue)。

他提出了勒貝格積分，拓寬了積分學(xué)的研究范圍。

在1914時(shí)，他給好朋友Julius Pál（也是數(shù)學(xué)家）寫信時(shí)提了一個(gè)問題：

在一個(gè)平面上，找一個(gè)最小區(qū)域，讓它可以覆蓋直徑不超過1個(gè)單位的面積？

直徑不超過1個(gè)單位的任意形狀，就是一個(gè)封閉曲線的邊緣上，最遠(yuǎn)兩點(diǎn)的距離不超過1個(gè)單位。

這個(gè)問題最難的部分是：

無法窮舉所有直徑為1的形狀到底長(zhǎng)什么樣子。

直徑為1的形狀千千萬，到底用哪種萬能補(bǔ)丁才能全部覆蓋它們呢？

萬有覆蓋“通用”方法

但是這個(gè)問題并不難上手，只要你有高中數(shù)學(xué)基礎(chǔ)，就可以試一下。

接下來，讓我們一起看看數(shù)學(xué)家們目前解決這個(gè)問題的方法。

從直徑為1的需要覆蓋的區(qū)域R入手。

雖然不知道R長(zhǎng)什么樣子，能夠確定的一點(diǎn)是：它絕對(duì)不會(huì)超過1個(gè)單位的寬度。

那么就先假設(shè)它有2個(gè)點(diǎn)——A和B，距離為1個(gè)單位。

現(xiàn)在，我們假設(shè)除了A和B之外，在R區(qū)域內(nèi)還存在一個(gè)點(diǎn)C。

那么C可能在哪里呢？

它不可能大于A的1個(gè)單位，這意味著它必須在以A為圓心且半徑為1的圓中。

但另外一個(gè)問題是，C和B的距離也不能超過1個(gè)單位。

所以C也必須在以B為圓心且半徑為1的圓中。

所以，C的位置就確定在了兩個(gè)圓形的交集位置。

到A和B的距離不能超過1，這一條件不僅僅適用于點(diǎn)C，還適用于區(qū)域R中的每個(gè)點(diǎn)。

所以R中的每一個(gè)點(diǎn)都必須位于這兩個(gè)圓的交集區(qū)域中。

換句話說，這個(gè)區(qū)域可以覆蓋直徑為1的所有可能的R集，是一個(gè)萬有覆蓋區(qū)域。

但是這個(gè)區(qū)域不是最小面積，需要對(duì)它進(jìn)行一下修剪。

注意，圓的相交點(diǎn)形成兩個(gè)等邊三角形，頂點(diǎn)分別是是A、B，以及距離AB中點(diǎn)垂直距離為√3/2的上下兩個(gè)點(diǎn)。

因?yàn)?radic;3/2大于1/2，我們可以畫兩條平行線，與AB平行，距離AB 1/2個(gè)單位。

現(xiàn)在，考慮下圖中紅色的區(qū)域。

因?yàn)閮蓚€(gè)平行線之間的距離為1個(gè)單位，所以直徑為1的集合不可能同時(shí)出現(xiàn)在兩個(gè)紅色區(qū)域。就可以去掉一個(gè)。

這樣萬有覆蓋面積從原來的(2π/3)-(√3/2)≈1.228，減少到(π/2)-1/2≈1.071

從一個(gè)基本的萬有覆蓋開始，可以通過去掉一個(gè)無關(guān)緊要的部分，來縮小它的面積。

這就是數(shù)學(xué)家們得到最小萬有覆蓋的方法。

優(yōu)化方法：Pál六邊形

通過更先進(jìn)的技術(shù)，我們還能找到一些其他的簡(jiǎn)單形狀。

Pál利用定寬曲線的特性表明：

即使直徑為1的一組曲線，可能會(huì)從直徑1的圓中“伸”出來，它也總是可以通過移動(dòng)或旋轉(zhuǎn)，以適應(yīng)圍成這個(gè)圓的六邊形。

下圖就展示了Pál提出的，可以覆蓋各種形狀(直徑為1)的六邊形。

上圖中間的形狀是一個(gè)勒洛三角形(Reuleaux triangle)，這是一個(gè)與我們上一小節(jié)提到的萬有覆蓋密切相關(guān)的定寬曲線。

勒洛三角形是一個(gè)弧三角形，通過三個(gè)相同的圓可以獲得。

這個(gè)六邊形的面積是√3/2≈0.866，比我們上小節(jié)所得到的面積還要小。

但Pál也表示，并不需要整個(gè)六邊形。

他通過巧妙的旋轉(zhuǎn)，去掉了一些無關(guān)部分。

首先，將兩個(gè)Pál六邊形堆疊在一起。

其中一個(gè)六邊形繞中心旋轉(zhuǎn)30度。

出現(xiàn)了6個(gè)紅色小三角形。

每個(gè)紅色小三角形，都處在未旋轉(zhuǎn)六邊形的外部，以及旋轉(zhuǎn)六邊形的內(nèi)部。

由于每個(gè)六邊形平行對(duì)邊的距離是1個(gè)單位，所以對(duì)著的兩個(gè)紅色小三角形中的點(diǎn)距離肯定大于1個(gè)單位。

也就是說，一組直徑為1的形狀不可能同時(shí)出現(xiàn)在兩個(gè)相對(duì)的紅色小三角形中。

按照上一小節(jié)的思路，可能會(huì)覺得應(yīng)該能從6個(gè)小三角形去掉3個(gè)小三角形，但實(shí)際上是不行的。

因?yàn)橐粋€(gè)六邊形旋轉(zhuǎn)60度，或者對(duì)稱翻轉(zhuǎn)一下，都不會(huì)發(fā)生形狀的改變。

所以從相對(duì)的一對(duì)中選擇一個(gè)紅色三角形只有兩種不同的方法：

3個(gè)三角形可以是連續(xù)的，也可以是交替的。

但是，我們可以去掉2個(gè)這樣的小三角形。Pál就是這么做的。

他從他的六邊形上切下兩個(gè)三角形，得到一個(gè)保證能覆蓋所有直徑為1的區(qū)域的新形狀。

這種新的萬有覆蓋的面積是2-2/√3≈0.8453，比六邊形面積略小一些。
但是Pál六邊形并不是最優(yōu)解。

在此基礎(chǔ)上，數(shù)學(xué)家和數(shù)學(xué)愛好者們繼續(xù)修修剪剪。

在1992年，數(shù)學(xué)家Roland Sprague和HC Hansen在Pál六邊形上減去了三個(gè)小細(xì)條。

使面積縮小為0.844137708416。

Sprague減少了0.001單位面積，Hansen減少了0.00000000004單位面積。

退休程序員用高中幾何，兩次逼近極限

然后二十年過去了，這個(gè)問題毫無進(jìn)展。

直到2014年，一位叫做Philip Gibbs的退休軟件工程師嘗試解決這個(gè)數(shù)學(xué)問題。

他利用自己的編程背景優(yōu)勢(shì)，嘗試用電腦解來解決。

Gibbs首先對(duì)200個(gè)隨機(jī)生成的直徑為1的形狀進(jìn)行了計(jì)算機(jī)模擬。

這些模擬結(jié)果表明，他或許能夠修剪一個(gè)最小萬有覆蓋空間頂部角落的一些區(qū)域。

隨后，他證明了新的覆蓋對(duì)所有可能的直徑為1的形狀都適用。

2015年2月，Gibbs和兩位共同研究者將論文發(fā)表在了網(wǎng)上。

他們把最小萬有覆蓋面從0.8441377減少到0.8441153單位面積。

他的策略是將所有直徑為1的形狀移到他早些年發(fā)現(xiàn)的萬有覆蓋的某一角。

然后把對(duì)角部分剩下的任何區(qū)域都去掉；然而從節(jié)省面積測(cè)量的角度來說，卻是非常精確的。

雖然此次減小的單位面積只有0.0000224，但這卻幾乎是漢森在1992年減少的面積的100萬倍！

然而，這并未阻止他進(jìn)一步的“裁剪”。

2018年10月，Gibbs獨(dú)自又發(fā)布了一篇文章，再次將最小萬有覆蓋面積縮小。

要知道，在Gibbs的基礎(chǔ)上再縮小覆蓋面積實(shí)屬不易。正如來自加州大學(xué)河濱分校的數(shù)學(xué)家約翰·貝茲所說：

你不可能真的把這些碎片畫出來，因?yàn)樗麄兌际窃哟笮〉摹?/p>

而Gibbs卻再次突破了極限，堪稱原子剪刀。

這一次他的著手點(diǎn)是上圖中的點(diǎn)A和點(diǎn)E。

最終，通過這次研究，得到的最小面積就是0.8440935944。

值得一提的是，實(shí)驗(yàn)方法基本都屬于高中幾何知識(shí)。

正如貝茲所評(píng)價(jià)：

從數(shù)學(xué)角度來說，這只是高中幾何難度，但是它幾乎讓人為之瘋狂。

極限挑戰(zhàn)，仍將繼續(xù)

問題雖然還沒有最終解決，但是在2005年的時(shí)候，有數(shù)學(xué)家計(jì)算出了這個(gè)問題的理論下限，萬有覆蓋范圍不能小于0.832單位面積。

抵達(dá)終點(diǎn)最后一步步依舊等待人來跨越，困難之處依舊在于，直徑唯一的形狀千變?nèi)f化，最后給出的范圍需要涵蓋所有可能性。

如果你做到了，名字就將載入數(shù)學(xué)史。

傳送門

QuantaMagazine博客：
https://www.quantamagazine.org/how-simple-math-can-cover-even-the-most-complex-holes-20200108/
https://www.quantamagazine.org/amateur-mathematician-finds-smallest-universal-cover-20181115/

GitHub項(xiàng)目地址：
https://github.com/guadaran/lebesgue-universal-covering-problem