试解"移动沙发问题"

故侯瓜

　　今有一个走廊，宽度为1，它有一个直角拐弯。如果在此走廊里移动一个沙发并通过那个拐弯，那么这个沙发最大可允许多大呢？（此问题提出于1966。）

所求的是沙发的平面投影面积。它的数值(平方米)叫做"沙发常数"。图1示这样的走廊和所求得的沙发轮廓。据报道，Hammersley 用圆和矩形拼接后得出的这个形状，其沙发常数为2.2074。而Gerver则用18根曲线拼接，得出沙发常数2.2195。

　　我对此题做了试探，暂且将它称为"模板试验"。简介于下。

图2示走廊和沙发模板。这个矩形模板代表外形可被塑造的沙发。我们将它放入走廊的一边并推着它移动，转弯，再到另一边。这个移动是虚拟的，它认定周围是无障碍空间，可以随意到达。假如在模板行进中，有部分被"推"出了走廊，就出现不合理或错误。那也无妨，它只显示在平面上模板与走廊相交叠的图影异常。此时，我们只需将超出走廊边界的模板切掉，这个错误就被改正了。虚拟操作也就能被视为现实的。但模板一旦被切就不能恢复，尽管此部位随后可能又回到走廊内。模板试验的概念大致如此。

实际上模板试验就是对模板作外形加工处理。因此，做了本试验后的模板，若让它再走一遍走廊，显然就能毫无障碍地通过了。至于经过本试验后的模板大小如何，就请继续阅看下文吧。

　　图3示将一块宽度1，长度3.5的模板横着放入走廊内并推到最右边。这模板正好填满了长廊的一段。这是模板的初始状态。图3中有标志+及相应符号c,c1,c2，解释如下。

　　c 是矩形模板的中心，它不因模板随后的被切削而变，

c1 是模板初始状态下c在走廊上的投影，

c2 是模板竖着放入走廊拐弯角时c在走廊上的投影。

下面开始让模板转弯。这里的转弯包含平移和旋转。我们设计的转弯，是让模板中心c由起点c1，沿着线段c1c2，逐渐地平移，直到终点c2。在c的平移过程中，整个模板也随着平移，并围绕c作均匀的旋转。这个转弯走的路程可总结为，整个模板平移了c1c2距离，同时绕c "自转" 了90°。图4示这个转弯的某一瞬间。

　　假设我们用16步去完成这个转弯，那么就要将线段c1c2等分成16小段，将角度90°等分成16份。这样，每一个小转弯都包含两个动作：将c和模板平移一小段，再将模板围绕当前的c旋转一小角度。

图4示c因平移离开了c1到达新点，整个模板也随着平移并以c为中心旋转了一些。此时有部分模板超出了走廊边界（绿色部分），这些超出部分将立即被削除掉。

（注意到这里的平移和旋转，它们的参考点是不同的，平移是在包含走廊在内的坐标系内进行的，而旋转则是围绕流动点c进行的）

试验数据

走廊宽度 1 （可以用单位米，下同）。

模板尺寸 3.5*1，代表模板的数组(101，351)

每单位长100点，每1平方单位10000点

初始面积3.5451

转弯后 32步，面积2.2195 （模板粗削?）

64步，面积2.2059 （模板精削? 此

差异待研究）

图形（64步） 见图5（数据点数目太大，经抽

稀成图）

小议几句：

模板试验法的结果（沙发常数和图示）与Hammersley的结果甚为一致。这表明本方法是成功的。我们看到两种不同的解题途径走到一起了，令人兴奋不已。

本试验方法的关键点是在转弯过程模板中心c的平移路线的选定。本试验采用的平移路线是直线线段c1c2。虽然它的起讫点必须是c1和c2，但线段c1c2不必是直线，它可以是弧。弧还可以上凸，可以下凹。凹凸程度也可不同。一旦选定某一种弧作为平移路线，整个模板的转弯路径将跟着变动，模板被切削的那三块（左上，右上，中下）将随着被调整。我们期待的当然是被切三块总和为最小值的那一解。（本文结束）