The Moving Sofa Problem
Okay so when you think of modern problems in mathematics and algorithms, you often think of really obscure things, like topology, artificial intelligence, etc. But there are actually a ton of problems that seem SUPER simple, but remain unsolved. For instance, moving furniture.
Consider the following question: What is the largest area of a 2D shape that can be maneuvered through an L shaped planar region with legs of unit width? In other words, if you have the following hallway, what is the maximum area of an object that can be moved through it?
This problem is known as the “Moving Sofa” problem, and was originally postulated in 1966. The answer to the question (the unknown maximum area A) is known as the sofa constant.
So, what is the elusive sofa constant? Well, we don’t currently know. However, some mathematicians have made some interesting progress on bounding the answer.
The most trivial lower bound is that of a unit square. Below is a gif that demonstrates this behavior. Clearly this lower bounds the sofa constant to 1.
But, we can do better. Below is another gif, this time demonstrating how a circle of half radius can move through the hallway. This lower bounds the area to π/2.
At this point, though, it gets a bit more interesting. A guy by the name of Jon Hammersley figured out that if you split a semi circle into two quarter circles, and then add a rectangular block in between with a semi circle cut out of it, you get another shape that can move through the hallway! He did all this in a paper called On the enfeeblement of mathematical skills by “Modern Mathematics” and by similar soft intellectual trash in schools and universities. Impressive stuff. Below is a depiction of Hammersley’s sofa:
Hammersley’s sofa improved the lower bound of the sofa constant to π/2+2/π. But, this is where it starts to get interesting. A guy named Gerver decided to go full YOLO and compose the shape below, in his very appropriately named paper On moving a sofa around a corner. You’ll note that it looks quite similar to Hammersley’s sofa. However, in fact, it is a shape made of 18 different arcs, each with a distinct formula. (the small demarcations on the shape pinpoint places where different arcs come into play)
Cool! So what’s the area of Gerver’s fancy 18 arc sofa? Well, that can be answered via some simple math, shown below:
I don’t understand it either. But, the result is that Gerver’s ridiculously complex sofa has an area of ~2.19…, which is approximately ~.013 higher than Hammersley’s sofa’s area. And as of today, this is the largest sofa proven to go through the unit length hallway.
Furthermore, it is believed that this may indeed be the optimal value (the elusive sofa constant). A discretized version of the problem was solved numerically in 2014 by Philip Gibbs. He adopted a somewhat interesting approach in doing this. Instead of constructing different shapes and seeing which could move through the hallway (this is extremely difficult computationally), he considered how a hallway could move around a fixed sofa. In other words, he used a computer to calculate all possible paths a hallway could take around a fixed sofa, in which case the maximum area which fits within the intersection of every hallway path would be the maximum size sofa that can fit in the hallway! (if that doesn’t quite make sense, you can read his paper here) Below is the figure he ended up getting:
This solution agrees with Gerver’s to 8 significant figures! But, because it is just a discretized version of the problem, we still do not have conclusive proof that this shape is indeed the optimal sofa. :(
There also exist generalizations of this problem that people are still investigating! For instance, what about a hallway that has BOTH a left turn and a right turn? A guy named Dan Romik found the below shape, which is the current best:
The area of this dumbell looking sofa can be calculated via the following fun formula:
But, it’s unknown whether this is a truly optimal shape or not. Either way, mathematicians will likely continue to ponder moving sofas through arbitrary spaces, and I can’t wait to see what crazy shapes come next.
