A History of the Moving Sofa Problem

Abstract

Mathematician Leo Moser proposed the following question in 1966, “What is the largest area region which can be moved around a right-angled corner in a “hallway” of width one?” Such a simple question would appear to have a fairly straightforward solution. However, as of 2017 the maximum area capable of translating the corner of width one unit has not been confirmed. It’s simple yet unbelievably complex nature has attracted many mathematicians such as Daniel Romik, Joseph Gerver, John Hammersley, Phillip Gibbs, Kiyoshi Maruyama, and Nicole Song. The goal of this post is not to present any new solutions but to consolidate and distill the existing solutions into a single reference so those interested in the problem do not have to toil reading dozens of papers. However, if the reader is interested in understanding specific concepts about a particular solution, I highly recommend refferring to the literature that corresponds with the solution in which you are interested. Sources will be cited at the end of the post making it easy to find the literature that corresponds with your solution of interest.

Introduction

Conditions of the Problem

There are a few basic conditions that must apply to shapes of area $T$ tested within the described hallway associated with Leo Moser’s original dilemma:

An area proposed to be a sofa $T$ , must be a bounded region within a plane whose boundary is a closed curve.

Figure 1: Labeled unit width hallway (N. Song)
The $90 \textdegree$ hallway is the set of points $(l,w)$ defined in such a manner that $l\leq1$ and $w\leq1$ and such that either $l\geq0$ or $w\geq0$ . $(l,w)$ will be used to describe points within the hallway or to refer to coordinates associated with hallway. Thus, $(l,w)$ will be named hallway coordinates. The region that we call a hallway is a region bounded by the union of four rays: $l=0$ , $l=1$ , $w=0$ , and $w=1$ . If we are to construct a traditional hallway, $w=1$ refers to the top wall, $w=0$ , is the bottom wall, $l=1$ is the right wall, and $l=0$ is the left wall. The origin $(0,0)$ describes the corner found within the hallway.
Sofa $T$ must have an axis of symmetry $S$ .
When sofa $T$ is not in the corner, axis of symmetry $S$ may be oriented perpendicular to the direction of the hallway.
Figure 2: Axis of symmetry coincident with $y$ -axis (L. Moser)
As sofa $T$ moves around the corner, the axis of symmetry $S$ becomes coincident with the line through the inner and outer vertices of the corner, the $y$ -axis.

Some Basic Sofas

The Unit Square

Before looking into the more complex sofas associated with the moving sofa problem it is important to recognize some of the most basic sofas that can be used to solve the problem, as they will provide some key intuitions when describing later sofas. As described previously we have already described the hallway in which the sofa resides using four infinite rays. However, we should notate this mathematically. The hallway can be described using the following:

$L_l = \{ (x,y) \} \in \Bbb{R}^2 : x \leq 1 , 0 \leq y \leq 1 \} \\ L_w = \{ (x,y) \} \in \Bbb{R}^2 : x \leq 1 , 0 \leq y \leq 1 \} \\ L = L_l \cup L_w$

Now that we have our hallway in mathematical notation let’s start playing around with some sofas. The most obvious sofa to start with is the unit square. Let’s say we put our unit square in the corridor of one of the hallways. According to the definitions of our hallway $L$ , the max length of our sofa can be is $1$ , otherwise, it will not be capable of traversing the corner of hallway $L$ . We can also determine that the max height is $1$ otherwise it would exceed the defined height of the corridor. Note our unit square meets all the conditions sets earlier: it is bounded by a region, fits within the confines of our hallway, including when it switches from translating horizontally to vertically in the corner, has multiple axis of symmetry, is perpendicular to the corridor at all times, and has an axis of symmetry $S$ that becomes coincident with the line through the inner and outer vertices of the corner in our hallway. Now that it has been confirmed that it fits the requirements of a sofa lets measure its area. We know that in a square $l=w=s$ . Indeed both $l$ and $w$ equal one. Thus, if $s=1$ , and the area of a square is $s^2$ than $A_s=1$ .

Figure 3: Unit square sofa (D. Romik)

Figure 4: Unit width one sofa traversing hallway (D. Romik)

The Semicircle

However, surely there are other sofas that can achieve a larger area. Consider a semicircle of radius $1$ . For a semicircle to negotiate the corner within the hallway $L$ it must first translate horizontally, rotate by touching the inside surface of the hallway, and then continue by translating vertically. However, how can we prove that the semicircular sofa indeed traces the inside and outside corner without exceeding the boundary of the hallway? Employing Thale’s theorem, which states that if $A$ , $B$ , and $C$ are points on a circle where segment $\overline{AC}$ is the diameter, then $\angle ABC$ is a right angle, we can indeed state that the semicircle can rotate around the corner.

Figure 5: Thale’s theorem (Wikipedia)

It will do so touching the inner side in three places, while the remaining arcs of the original semi-circle each touch the outer side of the corridor in two further places. Furthermore, the sofa also meets all the conditions required for the area to be a sofa.

Figure 6: Semicircle sofa traversing hallway (D. Romik)

Now that we have confirmed, that the semicircle fits around the corner in the hallway, can we notate it mathematically and calculate its area? If we want to describe the the movement of this sofa we must remember that we are translating this sofa in two directions horizontally and vertically. However, what if we were to keep the sofa in a set location and rotate the actual pathway around the sofa? This would allow us to clearly locate the points in the hallway which come in contact with the sofa as well as the rotation path it would take around the corner. The movement of the sofa through the corridor is fairly straightforward, so we will be focusing on the portion of the hallway where the sofa translates, rotates monotonically from an angle of $0$ to $\pi/2$ . As a further note we will associate time $t$ , with an angle $\theta$ . As time passes the angle of rotation of the hallway changes. Thus, the parameter, time, will represent the angle of the hallway.

If $T\subseteq\Bbb{R}^2$ is a sofa, and $L$ is the hallway of $90 \textdegree$ , a path of rotation for sofa $T$ is a continuous pathway $\vec{M}:[0,\pi/2]\rightarrow\Bbb{R}^2$ in such a manner that $R_t(T)+\vec{M}(t)\subseteq L$ for all $t\in[0,\pi/2]$ . Here the concept of a rotation path is defined. In simple terms we say that if sofa $T$ is a subset or equal to the two dimensional real numbers and $L$ is the hallway of $90\textdegree$ , than $\vec{M}$ has a domain of $[0,\pi/2]$ and codomain of the two dimensional real numbers assuming that we consider our hallway $L$ is a subset or is equal to the translation of the rotational matrix and rotation path at time $t$ , where time $t$ must be in the domain of $[0,\pi/2]$ . This allows us to say that sofa $T$ can be rotated in hallway $L$ if $T$ has a rotation path. As I mentioned before however we want to rotate the hallway. From the point of reference of the sofa we are rotating the hallway $L$ in the opposite direction that the sofa $T$ would be rotated, thus we say the rotation path that the hallway carves out is in fact $\vec{M}(-t)$ .

Now that we have all the correct parameters we can define our sofa $T$ . Let $T$ be a sofa, $\vec{M}:[0,t]\rightarrow\Bbb{R}^2$ be a continuous pathway. The sofa of the greatest area with said parameters is $T=\bigcap_{t\in[0,\pi/2]}R_{-t}(L-\vec{M}(t))$ . In other words sofa $T$ is the intersection of all sets between $0$ and $\pi/2$ . These sets are defined as the rotational transformations that result when the difference is taken between the hallway $L$ and the rotation path $\vec{M}$ .

Now that we defined the maximum area associated with a sofa of specific parameters, let’s calculate the area. If $L$ is the hallway, $\vec{M}:[0,t]\rightarrow\Bbb{R}^2$ than the path is $\vec{M}(t)=(0,0)$ . Rotating around the hallway according to $\vec{M}(t)$ we will get our semicircular sofa of radius $1$ defined by $x^2+y^2\leq1$ and $x\geq0$ . Even though the semicircle must rotate around the corner implementing translational motion in the vertical and horizontal direction, its boundaries are strictly defined.

Figure 7: Intersection of $x^2+y^2\leq1$ and $x \geq 0$ (G. Goldenberg)

If we graph the inequalities, a defined area is produced. This area falls between the equations $x^2+y^2\leq1$ and $x \geq 0$ . It is clear to see that the radius of this circle has a radius that measures one unit, and we also know this area is semicircular, thus we can calculate the area quite simply:

$A_{semi}=\frac{\pi r^2}{2} \\ r=1 \\ A_{semi}=\frac{\pi(1)^2}{2} \\ A_{semi}=\frac{\pi}{2}=1.57079632679...$

In this case it was not necessary to use set theory or derive a system of equations, but in some of the more complex sofas it will be, and now we have a solid understanding of how sofas traverse the corner of the hallway.

Famous Sofas

Hammersley’s Sofa & Upper Bound

As stated earlier there have been many mathematicians who have been intrigued by the moving sofa problem, and one of these mathematicians was John Hammersley who provided many mathematicians with insight into the moving sofa problem. Hammersley is most well known for the sofa he proposed as the sofa of largest area that can traverse the Moser’s hallway. Though a better sofa was later discovered, Gerver’s in 1992, Hammersley’s sofa would provide the foundation of Gerver’s discovery.

Figure 8: Hammersley’s sofa traversing hallway (D. Romik)

Hammersley’s sofa is unique as it is bound by six curves. A Hammersley sofa can be constructed if radius $r$ , which is required to construct the sofa, falls in the interval $(0,1)$ . The six curves that bound Hammersley’s sofa are as follows:

A semicircular arc with radius $r$ spans from $0$ to $\pi$ , with its center at the origin $(0,0)$ . The arc starts at $(r,0)$ , and ends at $(-r,0)$ .
A line segment that connects $(r,0)$ to $(r+1,0)$ .
The arc of a quarter circle that begins at $\pi/2$ and ends at $0$ . Its center is located at $(r,0)$ . The quarter circle begins at $(r+1,0)$ and ends at $(r,1)$ .
A line segment that begins at $(r,1)$ and ends at $(-r,1)$ .
A quarter circle arc that begins at and ends at $\pi/2$ and whose center is $(-r,0)$ . This arc spans from $(-r,1)$ to $(-r-1,0)$ .
A line segment that starts at $(-r-1,0)$ and ends at $(-r,0)$ .

Unlike the other shapes we have seen, this shape doesn’t seem as if it should translate the corner. How can it be proved that it indeed fits? If we have a radius $r$ we can claim claim that the points on our rotational path are $r(-\cos t,-\sin t)$ . Essentially we are scaling the points on the rotation path by the length of our radius $r$ . Why can this be stated? The sofa only touches the top wall, corner, and right wall as it rotates around the corner, thus we merely must prove these three portions are tangent to the corner and employ Thale’s theorem.

Figure 9: Labeled Hammersley’s sofa (N. Song)

The line tangent to the corner is easier to prove since if we only have to show that point $O$ is the midpoint of segment $\overline{AB}$ . Based on our visual, we can state that points $\odot A$ and $\odot B$ have coordinates with the following value: $(-2r\cos t,0),(0,-2r\sin t)$ . Assuming that we are following convention where time $t$ represent angle $\theta$ , $t$ will represent the angle with which the sofa rotates around center of rotation $O$ . Then $\angle{ACO}=\angle{OAC}=t$ . This can be concluded since both $\overline{OA}$ and $\overline{OC}$ are radii of the the arc $\stackrel \frown{AB}$ . Thus the coordinates of $O$ are in fact $r(-\cos t,-\sin t)$ . From here we just need to check that both quarter circles that are in contact with hallway $L$ are tangent to the corner. However, the quarter circles are the same arc just reflected over a vertical axis of symmetry. Thus if we prove one is tangent, than we can prove the other. It turns out that both exterior arcs are tangent. This can be concluded since both arcs are quarter circles of radius one rotating about point $\odot A$ . $\odot A$ is also translating along the $x$ -axis as it was just proved that there is always a line tangent to the corner. Via Thale’s theorem, we can confirm that Hammersley’s sofa can traverse the hallway $L$ .

Now that we have proved Hammersley’s sofa let’s get its area. The simple way to think about its area is by reverting to our investigation of the semicircular sofa. Hammersley’s sofa is simply a variation of the semicircular sofa. He splits the semicircle in half, adds a rectangular block in between the the two quarter circles and removes a small semicircle from the center of the added block. It turns out the empirical formula for said shape is $A_{Hamm}=\pi/2+2r-\pi r^2/2$ . This assumes the radius $r$ falls in the interval $[0,1]$ . Using some basic calculus we can determine the max area of said equation by taking the derivative and finding its max:

$\frac{dA}{dr}=2-\pi r \\ 2-\pi r=0 \\ r=\frac{\pi}{2} \\ A_{max}=\frac{\pi}{2}+\frac{2}{\pi} \\ A_{max}=2.20741609916...$

Hammersley also contributed to the moving sofa problem by determining the upper bound for the area of a sofa declaring it was $2\sqrt{2}$ . He was able to do so with the following method:

Figure 10: Determing upper bound of maximal area (Mathematics Stack Exchange)

If we consider the situation when the sofa is rotated by $\pi/2$ , in order for the sofa to pass through the straight portion of the corridor, the sofa must be able to lie within the confines of the dotted lines. This represents the straight corridor. We can translate the dotted lines vertically but one must fall within the inner and outer corners. If it does not meet this requirement the sofa will either vanish or break into pieces. The max area is found when the topmost dotted line comes into contact with the inner corner. If $h$ is used to denote distance from the outer corner to the upper dotted line, the shaded region is defined in the following manner:

$A(h) = \begin{cases} 2h+1 & 0\leq h \leq\sqrt{2}-1 \\ 2\sqrt{2}+2+2\sqrt{h}-h^2 & \sqrt{2}-1\leq{h}\leq{\sqrt{2}} \end{cases}$

$A(h)$ reaches its max, $2\sqrt{2}$ , at the upper limit, $h=\sqrt{2}$ .

Gerver’s Sofa

Mathematician Joseph Gerver is the current mathematician whose sofa holds the record for the largest area. His sofa is actually quite similar when compared to Hammersley’s sofa as the both share the same Shepard piano shape, however Gerver optimized his sofa using set theory, system of equations, and differential equations to determine the absolute maximum area that could fit around the corner.

Figure 11: Labeled Gerver sofa (J. Gerver)

Remarkably, Gerver’s sofa is bounded by 18 different curves. Parts $V$ , $XIII$ , and $XVIII$ are straight segments. Parts $I$ , $VI$ , $XI$ , $XVII$ are circular arcs of radius $h$ . Parts $II$ , $III$ , $VII$ , $XI$ , $XV$ , and $XVI$ are involutes of circles and $V$ and $XIV$ are involutes of involutes of circles. Involutes, sometimes called evolvents, are curves produced using another given curve via connection of an imaginary taut wire to the given curve and tracing its free end as it is coiled onto the given curve.

Figure 12: Example of an involute (Wikipedia)

Gerver’s sofa negotiates the corner in the moving sofa problem differently than other sofas, such as Hammersley’s. As Gerver’s sofa negotiates the curve from $0$ to $\pi/2$ , it does so in a number of steps:

In the first stage of rotation, Gerver’s sofa touches the hallway $L$ in parts $XII$ and $XVII$ . It continues to move horizontally until it reaches the hallway $L$ or part $VII$ of the sofa. Then hits point $\odot G$ .
In the second stage the sofa touches the hallway along four different parts of the sofa $XI$ , $VIII$ , $IV$ , and $XVI$ , and then hits $\odot G'$
In the third stage the sofa comes into contact with hallway $L$ at parts $X$ , $V$ , $IX$ , and $III$ and then complete stages two and one in reverse respectively.

Now that we have discussed its movement lets calculate its area. Gerver in his paper generates a system of equations which he derives by attempting to locally optimize the shape of the sofa. The derivation of these equations is quite tedious and difficult to follow, however Gerver produces four equations which are in terms of constant $A$ , $B$ , $\phi$ , and $\theta$ . These equations allow us to determine the values of the terms which determine the local optimalities of the curves of which the sofa is constructed. While studying Gerver’s sofa, we will use his notation to avoid confusion between his notation and the notation used in this post:

$A(\cos \theta - \cos \phi) - 2B\sin \phi + (\theta - \phi - 1)\cos \theta - \sin \theta + \cos \phi + \sin \phi = 0 \\ A(3\sin \theta + \sin \phi) - 2B\cos \phi + 3(\theta - \phi - 1)\sin \theta + 3\cos \theta - \sin \phi + \cos \phi = 0 \\ A\cos \phi - \left ( \sin \phi + \frac{1}{2} - \frac{1}{2} \cos \phi + B\sin \phi \right)=0 \\ \left (A + \frac{\pi}{2} - \phi - \theta \right) - \left [B-\frac{1}{2}(\theta - \phi)(1 + A) - \frac{1}{4}(\theta - \phi)^2 \right] = 0$

I used GNU Octave to solve the system of equations. My calculated values matched those found in Gerver’s paper and other available literature:

$\phi = 0.03918 \\ \theta = 0.68130 \\ A = 0.09443 \\ B = 1.39920$

Gerver defines $r(\alpha)$ , $u(\alpha)$ , $D_{u}(\alpha)$ , and $s(\alpha)$ in the following manner:

$r(\alpha) = \begin{cases} \frac{1}{2} & 0 \leq \alpha < \alpha \\ \frac{1}{2}(1 + A + \alpha - \phi) & \phi \leq \alpha < \theta \\ A + \alpha - \phi & \theta \leq \alpha < \frac{\pi}{2} - \theta \\ B - \frac{1}{2} \left ( \frac{\pi}{2} - \alpha - \phi \right )(1 + A) - \frac{1}{4} \left (\frac{\pi}{2} - \alpha -\pi \right)^2 & \frac{\pi}{2} - \theta \leq \alpha < \frac{\pi}{2} - \phi \end{cases}$

$u(\alpha) \equiv \begin{cases} B - \frac{1}{2}(\alpha - \phi)(a + A) & \phi \leq \theta - \frac{1}{4}(\alpha - \phi)^2 \\ A + \frac{\pi}{2} - \phi - \alpha & \theta \leq \alpha < \frac{\pi}{4} \end{cases}$

$D_{u}(\alpha) = \frac{du}{d \alpha} \begin{cases} - \frac{1}{2}(1 + A) - \frac{1}{2}(\alpha - \phi) & \phi \leq \alpha \leq \theta \\ -1 & \theta \leq \alpha < \frac{\pi}{4} \end{cases}$

$s(\alpha) \equiv 1 - r(\alpha)$

If we want to calculate the area beneath the curves we must now define our functions:

$f_{1}(\alpha) \equiv 1 - \int^{\alpha}_{0} r(x)\sin(x)dx \\ f_{2}(\alpha) \equiv 1 - \int^{\alpha}_{0} r(x)\sin(x)dx \\ f_{3}(\alpha) \equiv 1 - \int^{\alpha}_{0} r(x)\sin(x)dx - u(\alpha)\sin(\alpha)$

If we now plug in the appropriate intervals for each set of equations and complete some $u$ substitution in the last of the three previous equations we get:

$A_{1} = 2\int^{\frac{\pi}{2} - \phi}_{0} f_{1}(\alpha)r(\alpha)\cos(\alpha)d\alpha + 2\int^{\theta}_{0} f_{2}(\alpha)s(\alpha)\cos(\alpha)d\alpha \\ A_{2} = 2\int^{\frac{\pi}{4}}_{0} f_{3}(\alpha)[u(\alpha)sin(\alpha) - D_{u}(\alpha)\cos(\alpha) - s(\alpha)cos(\alpha)]d\alpha \\ A_{1} + A_{2} = 2.2195...$

In Summary

The moving sofa problem is the quintessential example of a problem that may look simple on the outside, but is unbelievably complex. It’s simplicity and real life applications toy with your mind. To date no one has found a sofa with a larger area, and although his solution is only a conjecture, it seems probable that Gerver may have found the sofa of maximal area, however, the search continues.

It is worthy to note that the moving sofa problem has also inspired a few other spin-off problems. In 2016 Daniel Romik conjectured he had found the sofa of maximal area in a problem called the ambidextrous sofa problem. This problem is similar to the moving sofa problem, but the sofa must be able to negotiate two right angled corners where the hallway takes on a z-like shape. Nicole Song constrcuted a spin-off problem where the corner angles of the hallway(s) in the problem were smaller or larger than $\pi/2$ . Other mathematicians such as Kiyoshi Maruyama and Phillip Gibbs have experimented with different methods of shape extraction by using numerical sequences and angular steps and limits respectively. Though the problem may never be solved, as long as there are mathematicians there will be curious individuals attempting to solve the moving sofa problem.

Figure 13: Ambidextrous sofa traversing hallway (D. Romik)

“Pivot! Pivot! Pivot!”

—Ross, “The One With the Cop,” Friends

References

Wikipedia contributors. Moving sofa problem. Wikipedia, The Free Encyclopedia. Online resource: https://en.wikipedia.org/w/index.php?title=Moving_sofa_problem&oldid=791382852. Accessed August 21, 2017.

D. Romik. Differential equations and exact solutions in the moving sofa problem. (2016), 8. Online resource: https://www.math.ucdavis.edu/~romik/data/uploads/papers/sofa.pdf. Accessed August 21, 2017.

D. Romik. MovingSofas: A companionMathematica package to the paper problem “Differential equations and exact solutions in the moving sofa problem.” Online resource: https://www.math.ucdavis.edu/~romik/publications#companionfiles.

D. Romik. The Moving Sofa Problem. Online web article (2016): https://www.math.ucdavis.edu/~romik/movingsofa/. Accessed August 21, 2017.

Numberphile, Daniel Romik. The moving sofa problem. Online web video (2017): https://youtu.be/rXfKWIZQIo4. Accessed August 21, 2017.

Weisstein, Eric W. Moving Sofa Problem. MathWorld–A Wolfram Web Resource. Online resource: http://mathworld.wolfram.com/MovingSofaProblem.html. Accessed August 21, 2017.

P. Gibbs. A computational study of sofas and cars. (2014), 1-3. Online resource: http://vixra.org/pdf/1411.0038v2.pdf. Accessed August 21, 2017.

J. L. Gerver. On moving a sofa around a corner. (1992), 268. Online resource: http://newweb.tlsh.tp.edu.tw/mediafile/2042/fdownload/216/219/2015-4-14-2-7-23-219-nf1.pdf. Accessed August 21, 2017.

J. Baez. Hammersley sofa. (2015). Online resource: http://blogs.ams.org/visualinsight/2015/01/15/hammersley-sofa/. Accessed August 21, 2017.

Multiple contributors. What’s the upper bound for sofa problem? (2016). Online resource: https://math.stackexchange.com/questions/1847453/whats-the-upper-bound-for-sofa-problem. Accessed August 21, 2017.

Steven Finch. Moving sofa constant. (2002). Online resource: http://web.archive.org/web/20080107101427/http://mathcad.com/library/constants/sofa.htm. Accessed August 21, 2017.

K. Maryuyama. An approximation method for solving the sofa problem. (1971), 15-23. Online resource: https://archive.org/stream/approximationmet489maru#page/n7/mode/2up. Accessed August 21, 2017.

N. Song. A Variational Approach to the Moving Sofa Problem. (2016), 12-22. Online resource: http://math.bard.edu/belk/projects/NicoleSong.pdf. Accessed August 21, 2017.

Multiple contributors. Modelling the “Moving Sofa”. (2017). Online resource: https://math.stackexchange.com/questions/1787466/modelling-the-moving-sofa. Accessed August 21, 2017.

L. Moser. Problem 66-11: Moving furniture through a hallway. SIAM Rev. 8 (1966), 381.

Multiple contributors. The moving sofa problem. (2014). Online resource: https://plus.google.com/+johncbaez999/posts/DXb7RuQH8wc. Accessed August 21, 2017.

Multiple contributors. The moving sofa problem. (2014). Online resource: https://www.reddit.com/r/math/comments/2145c0/the_moving_sofa_problem/. Accessed August 21, 2017

A. P. Goucher. Complications of furniturial locomotion. (2014). Online resource: https://cp4space.wordpress.com/2014/01/09/complications-of-furniturial-locomotion/. Accessed August 21, 2017.

CategoriesMathematics

TagsMathematics