昨晚，我在秋名山輸給了一個沙發……_風聞
中科院物理所-中科院物理所官方账号-2018-12-23 14:56
原創：Cloudiiink 中科院物理所
昨晚，我在秋名山輸給了一個沙發，
它的排水溝過彎法是如此的出神入化。
雖然上面的開頭略顯詭異，但實際上設計沙發在狹窄的走廊裏轉彎，到現在都是數學家們沒有解決的難題之一（數學家：不是我們不努力，奈何沙發太狡猾）。在網購變得如此方便的今天，**網上買個沙發啥的根本不是新鮮事。**不過在買的牀太大了進不了門，買的沙發太長了過不了走廊……看着買的東西進不了自己的家門的時候，真的是忍不住想哇得一聲哭出來。
《老友記》S05E16，羅斯搬家，找了瑞秋和錢錢來幫忙
所以今天我們就來講一講，沙發過彎背後，不為人知的秘密。
沙發問題
Moving Sofa Problem
沙發問題看起來真的是人畜無害，哪怕是小孩都看得懂這個問題在講些啥：
L 形的直角轉角的走廊內，能通過的最大沙發的面積有多大？
另外這個問題要求沙發完整地在平面內移動，不要想什麼擠一擠，壓一壓，拆開再組裝，更別想把沙發立起來這種騷操作了（否則就會問你最大體積了不是麼）。這個問題最早在 1966 年由數學家 Leo Moser [1] 正式提出，從此就一直……一直駐留在了未解數學問題的名單上，直到現在還沒有解決……
像這種看起來很友好，但真正算起來的難度大的嚇人的堪稱**史上最賤數學題****[**2] 的遠不止這一道，比如下面這個
用 🍎，🍌 和 🍍 分別代表三個正整數的不定方程，配合標準腦筋急轉彎的標題撩撥你成為那 5%，不得不説效果非常地好。在繼續往下看之前，你有沒有興趣嘗試一下呢？
↓
↓
↓
↓
↓
↓
↓
↓
然而故事的真相一般都很殘酷，最小的三個正整數解為 3 個長達八十幾位的天文數字……
a=154476802108746166441951315019919837485664325669565431700026634898253202035277999
b=36875131794129999827197811565225474825492979968971970996283137471637224634055579
c=43736126779286972578612526023713901528165375581616136186214379933784234677720
回到沙發問題上，如果把走廊的寬度設定為 1，那麼此時通過的沙發的面積被稱為沙發常數（sofa constant）。
迄今為止人類對沙發問題的解決所做出的最成功的努力，就是求出了一個由 18 段曲線組成的沙發形狀，和比這個例子大了好多的沙發常數可能的最大值——沙發的面積一旦大於這個數，就一定不可能通過走廊了。
排水溝過彎法
Drift Cornering
千萬不要小看送豆腐的
為了方便大家更好地理解搬運沙發的困難，我們可以把沙發想象成車輛，現在要做的事情是找到最大的可以過彎的車子。
簡單起見，先從**「正方形」**入手 [3]。就和光滑斜面上的滑塊一樣，沙發可以輕鬆地通過這個轉角，其實這應該也是最容易想到的方案。可惜，現在這個形狀的「沙發常數」只有 1。
可以看到，正方形的平移過彎法顯然已經達到了平移的極限，無論是更長的，還是更寬的沙發，都無法再塞進這個轉角處。這個轉彎的過程也啓發我們充分發揮**「車技」**，讓整個沙發轉起來。
在這個轉角的地方，我們需要轉過 90 度。我們可以充分地發揮利用這個轉角，使用排水溝過彎法，讓沙發卡住轉角的頂點處，從而整個轉過去。此時可以通過的整個沙發是半圓形。我們的沙發常數也一下子可以躍升到 1.57，也就是圓周率的一半。
在半圓形的沙發中，我們利用 1/2 個圓周完成過彎。但其實，我們可以把這個 1/2 圓周再一分為二，從一輛普通轎車升級成一輛加長豪華轎車，從正常過彎變成漂移過彎。
貓和老鼠（Tom and Jerry）第 128 集憂鬱的貓中被超長豪華轎車無情碾壓的湯姆
當然，這種思路是可行的，數學家 John Hammersley 就提出了一個更像沙發的沙發。他把上面的半圓形沙發整體拉長，然後再在中間根據頂點處所需要的空間摳掉一部分。最後的整體形狀就像下面這張圖這樣。
中間的挖掉的半圓半徑其實可以在 0 到 1 中間任意取值，這些沙發都可以穿過 L 形的走廊。通過對一個二次函數取極值，我們就能求出最終沙發中間部分的半徑應當取為 2/pi ，那麼這時沙發的沙發常數就變成了
實在是比起之前大了很多，排水溝過彎法是真的好使。在這之後，1992 年由 Joseph Gerver [4] 提出了一個稍微大那麼一點點的沙發形狀，把沙發常數整整往上提升了 0.5%。而這已經是迄今為止知道的能通過的最大的沙發了。思路其實説起來也很簡單，利用微擾的想法，如果一個沙發曲線的面積是最大的，那麼沙發曲線「附近」的曲線面積也是最大的面積。由此，他得到了一共由 18 段曲線構成的沙發形狀，其沙發常數達到了 2.2195。
説實話，不仔細看的話真的感受不到和上面 Hammersley 提出的那種沙發形狀有什麼區別
其中 V, XIII 和 XVIII 三段是線段, I, VI, XII, 和 XVII 是圓弧, II, III, VII, XI, XV 和 XVI 是圓的漸開線， IV 和 XIV 是圓的漸開線的漸開線。不過，他依舊沒法證明得到的這個沙發曲線是最優的沙發曲線。
圓的漸開線，指的是將一根繞在圓上的繩子不斷拉直展開，其頂點走過的曲線，圖片來自 Hyrodium’s Graphical MathLand
水果忍者
Fruit Ninja
在討論啥是最優秀的沙發曲線的過程中，也出現過一段烏龍。在有段時間內，Hammersley 一度認為自己想出來的沙發形狀已經是這個問題的最優解了，不過顯然他想錯了。
在最大沙發的證明過程中， 2.8284，也就是兩倍的根號 2，一度被認為是沙發常數的可能的最大值——沙發的面積一旦大於這個最大值，就一定不可能通過走廊了。一直到 2017 年，才由 Yoav Kallus 和 Dan Romik [5,6] 打破這個塵封已久的記錄，一下子把沙發常數可能的最大值縮小到了 2.37，向着這個問題的成功解決邁了一大步。
現實版水果忍者
説起來他們解決這個問題，其實就和我們平時削水果差不多。如果換一個參考系，把我們固定在沙發上，沙發通過走廊的問題其實就變成了走廊牆壁圍着沙發旋轉的問題了。想象有一個蘋果，此時用一個 L 形的刀圍着蘋果不斷地旋轉着切，多餘的部分一定不能通過這個走廊，只有剩下的部分才有可能通過這個走廊，由此我們就得到了沙發常數可能的最大值。
論文中的「刀具」和「原材料」示意圖
用更加數學一點的語言來説，這樣的構造可以讓沙發問題從一個無限維的優化問題轉化為一個有限維的優化問題。原問題需要解決切無數刀時候的情況，但是如果連在切有限刀的情況下都無法通過的話，更談不上通過原來的走廊了。而有限維優化的事情，計算機再擅長不過。
在我們的現實生活中數學家們需要處理各種各種的優化問題，上圖所示為優化一個網絡中團簇的數量的算法示意圖，圖片來自 anvaka，reddit
在沙發問題裏面還有另一個有趣的事情，人們至今還沒有證明滿足最大沙發常數的沙發在通過轉角處時一定要轉過 90 度。
其他的遐想
Other Thoughts
在原來的沙發問題求而不得的情況下，人們也去研究了其他的更為一般的情況。比如修改一下轉角的角度，讓它不再是 90 度。或者增加往另外一個方向拐的轉角，看其沙發形狀應該是啥樣的。
比如這個由 Dan Romik 提出的眼鏡形的沙發 [7]，就可以連續地通過往左旋轉 90 度和往右旋轉 90 度的轉角。
在沙發問題的背後，或許還有着更為深刻的數學，更為神奇的方法等待着人們去發掘。
不過現在，在這個冬天的週日，就先懶洋洋地在沙發上躺一會吧。
參考文獻及鏈接：
[1] L. Moser, Problem 66-11: Moving furniture through a hallway, SIAM Rev., 8 (1966) 381.
[2] 史上最賤的數學題，這類擁有一個或者幾個變量的整係數方程被稱為丟番圖方程。文章裏包含了完整的數學解答，裏面涉及了較為複雜的數學知識，諸如橢圓曲線等。
[3] Dan Romik 的主頁。這上面不僅詳細地介紹了沙發問題的歷史，還有他自己製作的關於沙發問題的科普視頻，他也把為了研究方便用來 3D 打印各種沙發的工程文件掛在了主頁上。
[4] Gerver, Joseph L. (1992). “On Moving a Sofa Around a Corner”. Geometriae Dedicata. 42 (3): 267–283.
[5] Wagner, Neal R. (1976). “The Sofa Problem” (PDF). The American Mathematical Monthly. 83 (3): 188–189.
[6] Kallus, Yoav, and Dan Romik. “Improved Upper Bounds in the Moving Sofa Problem.” Advances in Mathematics 340 (December 2018): 960–82.
[7] Romik, Dan (2017). “Differential equations and exact solutions in the moving sofa problem”. Experimental Mathematics. 26 (2).
