昨晚，我在秋名山輸給了一個(gè)沙發(fā)，

它的排水溝過彎法是如此的出神入化。

雖然上面的開頭略顯詭異，但實(shí)際上設(shè)計(jì)沙發(fā)在狹窄的走廊里轉(zhuǎn)彎，到現(xiàn)在都是數(shù)學(xué)家們沒有解決的難題之一（數(shù)學(xué)家：不是我們不努力，奈何沙發(fā)太狡猾）。在網(wǎng)購(gòu)變得如此方便的今天，網(wǎng)上買個(gè)沙發(fā)啥的根本不是新鮮事。不過在買的床太大了進(jìn)不了門，買的沙發(fā)太長(zhǎng)了過不了走廊……看著買的東西進(jìn)不了自己的家門的時(shí)候，真的是忍不住想哇得一聲哭出來。

所以今天我們就來講一講，沙發(fā)過彎背后，不為人知的秘密。

沙發(fā)問題

沙發(fā)問題看起來真的是人畜無害，哪怕是小孩都看得懂這個(gè)問題在講些啥：

L 形的直角轉(zhuǎn)角的走廊內(nèi)，能通過的最大沙發(fā)的面積有多大？

另外這個(gè)問題要求沙發(fā)完整地在平面內(nèi)移動(dòng)，不要想什么擠一擠，壓一壓，拆開再組裝，更別想把沙發(fā)立起來這種騷操作了（否則就會(huì)問你最大體積了不是么）。這個(gè)問題最早在 1966 年由數(shù)學(xué)家 Leo Moser [1] 正式提出，從此就一直……一直駐留在了未解數(shù)學(xué)問題的名單上，直到現(xiàn)在還沒有解決……

像這種看起來很友好，但真正算起來的難度大的嚇人的堪稱史上最賤數(shù)學(xué)題?[2]?的遠(yuǎn)不止這一道，比如下面這個(gè)

用 ??，?? 和 ?? 分別代表三個(gè)正整數(shù)的不定方程，配合標(biāo)準(zhǔn)腦筋急轉(zhuǎn)彎的標(biāo)題撩撥你成為那 5%，不得不說效果非常地好。在繼續(xù)往下看之前，你有沒有興趣嘗試一下呢？

↓

↓

↓

↓

↓

↓

↓

↓

然而故事的真相一般都很殘酷，最小的三個(gè)正整數(shù)解為 3 個(gè)長(zhǎng)達(dá)八十幾位的天文數(shù)字……

a = 154476802108746166441951315019919837485664325669565431700026634898253202035277999

b = 36875131794129999827197811565225474825492979968971970996283137471637224634055579

c = 4373612677928697257861252602371390152816537558161613618621437993378423467772036

回到沙發(fā)問題上，如果把走廊的寬度設(shè)定為 1，那么此時(shí)通過的沙發(fā)的面積被稱為沙發(fā)常數(shù)（sofa constant）。

迄今為止人類對(duì)沙發(fā)問題的解決所做出的最成功的努力，就是求出了一個(gè)由 18 段曲線組成的沙發(fā)形狀，和比這個(gè)例子大了好多的沙發(fā)常數(shù)可能的最大值——沙發(fā)的面積一旦大于這個(gè)數(shù)，就一定不可能通過走廊了。

排水溝過彎法

為了方便大家更好地理解搬運(yùn)沙發(fā)的困難，我們可以把沙發(fā)想象成車輛，現(xiàn)在要做的事情是找到最大的可以過彎的車子。

簡(jiǎn)單起見，先從「正方形」入手 [3]。就和光滑斜面上的滑塊一樣，沙發(fā)可以輕松地通過這個(gè)轉(zhuǎn)角，其實(shí)這應(yīng)該也是最容易想到的方案。可惜，現(xiàn)在這個(gè)形狀的「沙發(fā)常數(shù)」只有 1。

可以看到，正方形的平移過彎法顯然已經(jīng)達(dá)到了平移的極限，無論是更長(zhǎng)的，還是更寬的沙發(fā)，都無法再塞進(jìn)這個(gè)轉(zhuǎn)角處。這個(gè)轉(zhuǎn)彎的過程也啟發(fā)我們充分發(fā)揮「車技」，讓整個(gè)沙發(fā)轉(zhuǎn)起來。

在這個(gè)轉(zhuǎn)角的地方，我們需要轉(zhuǎn)過 90 度。我們可以充分地發(fā)揮利用這個(gè)轉(zhuǎn)角，使用排水溝過彎法，讓沙發(fā)卡住轉(zhuǎn)角的頂點(diǎn)處，從而整個(gè)轉(zhuǎn)過去。此時(shí)可以通過的整個(gè)沙發(fā)是半圓形。我們的沙發(fā)常數(shù)也一下子可以躍升到 1.57，也就是圓周率的一半。

在半圓形的沙發(fā)中，我們利用 1/2 個(gè)圓周完成過彎。但其實(shí)，我們可以把這個(gè) 1/2 圓周再一分為二，從一輛普通轎車升級(jí)成一輛加長(zhǎng)豪華轎車，從正常過彎變成漂移過彎。

當(dāng)然，這種思路是可行的，數(shù)學(xué)家 John Hammersley 就提出了一個(gè)更像沙發(fā)的沙發(fā)。他把上面的半圓形沙發(fā)整體拉長(zhǎng)，然后再在中間根據(jù)頂點(diǎn)處所需要的空間摳掉一部分。最后的整體形狀就像下面這張圖這樣。

中間的挖掉的半圓半徑其實(shí)可以在 0 到 1 中間任意取值，這些沙發(fā)都可以穿過 L 形的走廊。通過對(duì)一個(gè)二次函數(shù)取極值，我們就能求出最終沙發(fā)中間部分的半徑應(yīng)當(dāng)取為 2/pi ，那么這時(shí)沙發(fā)的沙發(fā)常數(shù)就變成了

實(shí)在是比起之前大了很多，排水溝過彎法是真的好使。在這之后，1992 年由 Joseph Gerver [4] 提出了一個(gè)稍微大那么一點(diǎn)點(diǎn)的沙發(fā)形狀，把沙發(fā)常數(shù)整整往上提升了 0.5%。而這已經(jīng)是迄今為止知道的能通過的最大的沙發(fā)了。思路其實(shí)說起來也很簡(jiǎn)單，利用微擾的想法，如果一個(gè)沙發(fā)曲線的面積是最大的，那么沙發(fā)曲線「附近」的曲線面積也是最大的面積。由此，他得到了一共由 18 段曲線構(gòu)成的沙發(fā)形狀，其沙發(fā)常數(shù)達(dá)到了 2.2195。

其中 V, XIII 和 XVIII 三段是線段, I, VI, XII, 和 XVII 是圓弧, II, III, VII, XI, XV 和 XVI 是圓的漸開線， IV 和 XIV 是圓的漸開線的漸開線。不過，他依舊沒法證明得到的這個(gè)沙發(fā)曲線是最優(yōu)的沙發(fā)曲線。

水果忍者

在討論啥是最優(yōu)秀的沙發(fā)曲線的過程中，也出現(xiàn)過一段烏龍。在有段時(shí)間內(nèi)，Hammersley 一度認(rèn)為自己想出來的沙發(fā)形狀已經(jīng)是這個(gè)問題的最優(yōu)解了，不過顯然他想錯(cuò)了。

在最大沙發(fā)的證明過程中， 2.8284，也就是兩倍的根號(hào) 2，一度被認(rèn)為是沙發(fā)常數(shù)的可能的最大值——沙發(fā)的面積一旦大于這個(gè)最大值，就一定不可能通過走廊了。一直到 2017 年，才由 Yoav Kallus 和 Dan Romik [5,6] 打破這個(gè)塵封已久的記錄，一下子把沙發(fā)常數(shù)可能的最大值縮小到了 2.37，向著這個(gè)問題的成功解決邁了一大步。

說起來他們解決這個(gè)問題，其實(shí)就和我們平時(shí)削水果差不多。如果換一個(gè)參考系，把我們固定在沙發(fā)上，沙發(fā)通過走廊的問題其實(shí)就變成了走廊墻壁圍著沙發(fā)旋轉(zhuǎn)的問題了。想象有一個(gè)蘋果，此時(shí)用一個(gè) L 形的刀圍著蘋果不斷地旋轉(zhuǎn)著切，多余的部分一定不能通過這個(gè)走廊，只有剩下的部分才有可能通過這個(gè)走廊，由此我們就得到了沙發(fā)常數(shù)可能的最大值。

用更加數(shù)學(xué)一點(diǎn)的語言來說，這樣的構(gòu)造可以讓沙發(fā)問題從一個(gè)無限維的優(yōu)化問題轉(zhuǎn)化為一個(gè)有限維的優(yōu)化問題。原問題需要解決切無數(shù)刀時(shí)候的情況，但是如果連在切有限刀的情況下都無法通過的話，更談不上通過原來的走廊了。而有限維優(yōu)化的事情，計(jì)算機(jī)再擅長(zhǎng)不過。

在沙發(fā)問題里面還有另一個(gè)有趣的事情，人們至今還沒有證明滿足最大沙發(fā)常數(shù)的沙發(fā)在通過轉(zhuǎn)角處時(shí)一定要轉(zhuǎn)過 90 度。

其他的遐想

在原來的沙發(fā)問題求而不得的情況下，人們也去研究了其他的更為一般的情況。比如修改一下轉(zhuǎn)角的角度，讓它不再是 90 度?；蛘?span id="s0sssss00s" class="color-purple-01">增加往另外一個(gè)方向拐的轉(zhuǎn)角，看其沙發(fā)形狀應(yīng)該是啥樣的。

比如這個(gè)由 Dan Romik 提出的眼鏡形的沙發(fā) [7]，就可以連續(xù)地通過往左旋轉(zhuǎn) 90 度和往右旋轉(zhuǎn) 90 度的轉(zhuǎn)角。

在沙發(fā)問題的背后，或許還有著更為深刻的數(shù)學(xué)，更為神奇的方法等待著人們?nèi)グl(fā)掘。

不過現(xiàn)在，面對(duì)即將到來的周末，就先懶洋洋地在沙發(fā)上躺一會(huì)吧。

參考文獻(xiàn)及鏈接：

[1] L. Moser, Problem 66-11: Moving furniture through a hallway, SIAM Rev., 8 (1966) 381. https://www.jstor.org/stable/2028218

[2]?史上最賤的數(shù)學(xué)題，這類擁有一個(gè)或者幾個(gè)變量的整系數(shù)方程被稱為丟番圖方程。文章里包含了完整的數(shù)學(xué)解答，里面涉及了較為復(fù)雜的數(shù)學(xué)知識(shí)，諸如橢圓曲線等。 https://mp.weixin.qq.com/s?__biz=MzA5NzA1NjE4Mw==&mid=2650183932&idx=1&sn=3ea7a990ef4bcb2f6443eb54d641d046&scene=21#wechat_redirect

[3] Dan Romik 的主頁(yè)。這上面不僅詳細(xì)地介紹了沙發(fā)問題的歷史，還有他自己制作的關(guān)于沙發(fā)問題的科普視頻，他也把為了研究方便用來 3D 打印各種沙發(fā)的工程文件掛在了主頁(yè)上。 https://www.math.ucdavis.edu/%7Eromik/movingsofa/

[4] Gerver, Joseph L. (1992). "On Moving a Sofa Around a Corner". Geometriae Dedicata. 42 (3): 267–283. https://link.springer.com/article/10.1007%2FBF02414066

[5] Wagner, Neal R. (1976). "The Sofa Problem" (PDF). The American Mathematical Monthly. 83 (3): 188–189. http://www.cs.utsa.edu/%7Ewagner/pubs/corner/corner_final.pdf

[6] Kallus, Yoav, and Dan Romik. “Improved Upper Bounds in the Moving Sofa Problem.” Advances in Mathematics 340 (December 2018): 960–82.? https://linkinghub.elsevier.com/retrieve/pii/S000187081830416X

[7] Romik, Dan (2017). "Differential equations and exact solutions in the moving sofa problem". Experimental Mathematics. 26 (2).? https://www.tandfonline.com/doi/abs/10.1080/10586458.2016.1270858?journalCode=uexm20

[8] Moving Sofa Problem: https://en.wikipedia.org/wiki/Moving_sofa_problem

>> 熱門文章推薦 <<