昨晚，我在秋名山输给了一个沙发……_风闻
中科院物理所-中科院物理所官方账号-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).
