The moving sofa problem(en.wikipedia.org)
en.wikipedia.org
The moving sofa problem
https://en.wikipedia.org/wiki/Moving_sofa_problem
59 comments
That especially hurt me too read as just this morning I helped a friend move a couch. We had had to turn it pretty much every way possible and the only reason we kept trying was because we knew somehow she got it moved in. It's interesting that in so many different areas knowing there is a solution makes finding the solution easier.
In a related story my dad remodeled his house and put in a new wall blocking in a couch. When it came time to move it (years later) I thought it was going to be a permanent feature of that room. My dad came up with the solution of getting a saw and cutting the couch into pieces.
In a related story my dad remodeled his house and put in a new wall blocking in a couch. When it came time to move it (years later) I thought it was going to be a permanent feature of that room. My dad came up with the solution of getting a saw and cutting the couch into pieces.
This is such a common issue in NYC that we have a business (the couch doctor) that does nothing but take apart furniture and reassemble it in place. Friend of mine used them and they were apparently really impressive (he told them what sofa he had, the dimensions of his door, and they knew right away it wouldn't be a problem)
A number of years back I bought a couch from my brother. I promptly took off on a trip on which I managed to badly break my foot so he ended up dumping the thing at my house and it sat in my garage for months.
Once I was mobile again, I realized it was a tight fit and the sofa wasn't actually symmetrical. Fortunately, it was asymmetrical in the right way for the room but I had a momentary panic.
>we have a business (the couch doctor)
I also have to say that I just love how businesses get created to deal with especially largely localized problems and do a really good job at it. Even at a national level, I met with a specialist company yesterday to do something in my house and it was very refreshing.
Once I was mobile again, I realized it was a tight fit and the sofa wasn't actually symmetrical. Fortunately, it was asymmetrical in the right way for the room but I had a momentary panic.
>we have a business (the couch doctor)
I also have to say that I just love how businesses get created to deal with especially largely localized problems and do a really good job at it. Even at a national level, I met with a specialist company yesterday to do something in my house and it was very refreshing.
I once helped a friend move a mattress set up a tight stairway. We got the mattress to turn the corner by brute force squeezing and smashing, but the box-spring was too rigid for that.
We were stumped until we finally figured out that if we simply unscrewed the two wooden frame pieces that run lengthwise, what remained of the box-spring was wooden pieces that run crosswise and are attached to a network of springs. Then it was possible to fold it into a U shape.
To explain visually, the box-spring was built like this one:
https://mk0mattressclarcyl3h.kinstacdn.com/wp-content/upload...
We removed the two pieces of wood running along the left and right bottom edges, then we folded the whole thing so that the wooden cross pieces at the foot of the bed and head of the bed touched each other. The wire grid at the top was just flexible enough to handle a gentle arc.
We were stumped until we finally figured out that if we simply unscrewed the two wooden frame pieces that run lengthwise, what remained of the box-spring was wooden pieces that run crosswise and are attached to a network of springs. Then it was possible to fold it into a U shape.
To explain visually, the box-spring was built like this one:
https://mk0mattressclarcyl3h.kinstacdn.com/wp-content/upload...
We removed the two pieces of wood running along the left and right bottom edges, then we folded the whole thing so that the wooden cross pieces at the foot of the bed and head of the bed touched each other. The wire grid at the top was just flexible enough to handle a gentle arc.
If anyone hasn't read or has forgotten Douglas Adams 'Dirk Gently's Holistic Detective Agency' then I warmly recommend it. It includes, iirc, The Sofa Problem and the solution is classic Adams and all HNers will love it! :)
Is there an audiobook of the full book? I was only able to find the abridged version.
There was an unabridged audio of both Dirk Gently and Long Dark Teatime. Both read by Douglas and each 6 CDs.
A quick skim of Amazon doesn't find them so you might have to hunt eBay etc.
A quick skim of Amazon doesn't find them so you might have to hunt eBay etc.
Wondered if anyone would mention this, also if you haven't tried it the Netflix version of Dirk Gently is wonderful, departs from the books without departing from the characters.
The first season is delicious, the second one (unfortunately) veers too far off into the odd mix of fantasy, conspiracy theories and mysticism. I'm curious what the third one brings.
Casting-wise, I am not sure Elijah Wood was the best choice. Big name for impact maybe, but the role just feels ill-fitting.
Casting-wise, I am not sure Elijah Wood was the best choice. Big name for impact maybe, but the role just feels ill-fitting.
Unfortunately nothing, it's been cancelled.
https://www.google.com/amp/s/deadline.com/2018/03/dirk-gentl...
https://www.google.com/amp/s/deadline.com/2018/03/dirk-gentl...
Second season was a huge disappointment, but it also featured the best and most truthful portrayal of MDMA that I've ever seen on screen (under the guise of a "love" magic spell).
I really enjoyed the second season but yes the first season was better bordering on sublime.
Much better than the BBC version (and very different).
When I heard they where doing an american version I didn't expect much wondering how it would translate...it turns out, very well.
Much better than the BBC version (and very different).
When I heard they where doing an american version I didn't expect much wondering how it would translate...it turns out, very well.
It's sad sack similar enough to his role on Wilfred.
Caveats for people passing by: the Netflix version has little or no resemblence to the book series and its creator's career seems to have ended following accusations of rape and sexual abuse by more than 10 people[1].
1. https://en.m.wikipedia.org/wiki/Max_Landis#Sexual_assault_ac...
1. https://en.m.wikipedia.org/wiki/Max_Landis#Sexual_assault_ac...
[deleted]
Greatest book ever. Must read even if you're not into moving sofas across corridors...
And it is surprising how many readers completely miss the solution :-).
Generations upon generations of people will keep complaining that Douglas Adams is not part of the Moving Sofa Problem.
But to be fair, that one was about a regularly shaped sofa getting stuck by violating the laws of physics in the first place.
But to be fair, that one was about a regularly shaped sofa getting stuck by violating the laws of physics in the first place.
What I learned from this HN post is that Douglas Adams wasn't the original source of the sofa problem. I always thought he invented it.
Adams books are full of refs to other problems and theories. Don't have the books to hand so can't point out any more, but I don't think I am overfitting :)
Gibbs's computational approach is really interesting [1]. Keep the sofa still and move the corridor, and the optimal sofa shape is the intersection of all (well n, since it's a numerical approximation) the corridor shapes as they sweep around.
[1] https://www.researchgate.net/publication/311900489_A_Computa...
[1] https://www.researchgate.net/publication/311900489_A_Computa...
> ...describing sofas in terms of the translations and rotations as a function of time is by now a standard way of thinking about the moving sofa problem, and has been used in the attack on the problem by Joseph Gerver in his paper from 1992, and in my own recent paper, where among other thing I made precise your suggested notion of describing the sofa shape that results from the continuous intersection of corridors rotating and translating over time. See my paper (available here: https://www.math.ucdavis.edu/~romik/data/uploads/papers/sofa...), and especially Theorem 1 in section 2.
Dan Romik
Dan Romik
That link does not work for me, but this may be better : https://www.math.ucdavis.edu/~romik/movingsofa/
That is a different article. My link to Gibbs's article came from Wikipedia, but your link points to another copy: http://vixra.org/pdf/1411.0038v2.pdf
Maybe that one will work for you.
Maybe that one will work for you.
Kudos to the animation illustrator [0]. See also [1]. I'm collecting these for reasons.
[0] https://en.m.wikipedia.org/wiki/User:Rocchini
[1] https://news.ycombinator.com/item?id=15549197
[0] https://en.m.wikipedia.org/wiki/User:Rocchini
[1] https://news.ycombinator.com/item?id=15549197
The animation appears to be missing some frames, at the point where the couch starts to turn.
Someone with a moderate amount of time on their hands could probably patch it by mirroring frames from the end of the turn.
Someone with a moderate amount of time on their hands could probably patch it by mirroring frames from the end of the turn.
That particular guy appears to have a knack for geometry, 4-dimensionality and hyperbolic spaces. Topics that I feel like I have a foot in from watching my favorite Parker square videos...
This problem seems tame and uninteresting compared to the real-life 3D case.
Last christmas, I was moving a sofa on my mother-in-law's home, and it was stuck in the corridor. She told me "i seem to recall that you have to raise this side a bit". I replied something to the effect "no way, i am a mathematician and there's no way that this can possibly make a difference".
Of course she was right. I could only move the sofa by rotating it in 3D just so, so that the slightly protruding arm and leg could pass one after the other.
So the real question, not dealth with in the wikipedia page, is: what is the largest sofa that we can move through a unit corner, allowing it to rotate in 3D ?
Last christmas, I was moving a sofa on my mother-in-law's home, and it was stuck in the corridor. She told me "i seem to recall that you have to raise this side a bit". I replied something to the effect "no way, i am a mathematician and there's no way that this can possibly make a difference".
Of course she was right. I could only move the sofa by rotating it in 3D just so, so that the slightly protruding arm and leg could pass one after the other.
So the real question, not dealth with in the wikipedia page, is: what is the largest sofa that we can move through a unit corner, allowing it to rotate in 3D ?
I guess the answer might be to take the largest 2D sofa and just extrude it upwards 1, so that it fills the height of the corridor.
It will depend on how you define the "largest" sofa: total volume? surface area of the ground covered by it?
If it is the largest volume, you need to limit the height of the corridor (to be the same as the width? a multiple of it?). Otherwise, you can pass an arbitrarily long L that you turn side-wise on the corner.
If it is the largest volume, you need to limit the height of the corridor (to be the same as the width? a multiple of it?). Otherwise, you can pass an arbitrarily long L that you turn side-wise on the corner.
I was thinking of maximising the volume of the sofa in a corridor as tall as it is wide.
Somewhat related, but more counterintuitive and "solved": https://en.wikipedia.org/wiki/Kakeya_set
Nice numberphile vídeo on the subject:
https://youtube.com/watch?v=rXfKWIZQIo4
https://youtube.com/watch?v=rXfKWIZQIo4
[deleted]
Would proving this advance our knowledge in some related field such as mathematical topology? Since the values have already been brute forced (but unproven) there really isn’t any direct practical application for knowing the solution
[deleted]
[deleted]
> there really isn’t any direct practical application for knowing the solution
Oh, but math always seems that way. And often, it is. But sometimes, very rarely, your solution to the sofa problem explains a key detail to P vs NP, or allows a breakthrough in transistor design, or improves the airflow calculations allowing for faster jets, etc.
Math's true beauty is that it's never done playing games with us as we realize all the strange connections.
Oh, but math always seems that way. And often, it is. But sometimes, very rarely, your solution to the sofa problem explains a key detail to P vs NP, or allows a breakthrough in transistor design, or improves the airflow calculations allowing for faster jets, etc.
Math's true beauty is that it's never done playing games with us as we realize all the strange connections.
Depends on the proof. If it solves this specific problem more or less through perseverance, it won’t be more than a tiny footnote in the history of mathematical.
If, on the other hand, some abstract theory contains this as a special case (say by limiting the number of dimensions to 2 and the geometry to Euclidean), that theory could (but isn’t guaranteed to) have wider application, both inside mathematics and outside of it.
I would think the former is more likely than the latter, though.
If, on the other hand, some abstract theory contains this as a special case (say by limiting the number of dimensions to 2 and the geometry to Euclidean), that theory could (but isn’t guaranteed to) have wider application, both inside mathematics and outside of it.
I would think the former is more likely than the latter, though.
Kickstarter idea: Gerver's sofa in Italian leather.
It doesn't seem very practical as furniture - there's a big hole in the middle. Actual sofas can be moved in three dimensions, so can be more usefully shaped.
It might not be awful if it came with a matching coffee table for the middle section.
Even better - a detachable ottoman. It fills the hole when you want a sofa, and becomes a footrest when you don't.
Is there a 3 dimensional variant? Or n-dimensional?
Only found this: https://www.reddit.com/r/math/comments/6hui9p/is_the_sofa_mo...
I suppose you could have a sofa that your corkscrew around the corner?
I suppose you could have a sofa that your corkscrew around the corner?
As a wallet
Numberphile did a great video on this topic https://youtu.be/rXfKWIZQIo4
It would be great to someone create a game where you should calculate and create sofa in order to move sofa through the building passages
Can someone just put this in an ISO standard already, so I know how wide to make my hallways?
[deleted]
TimeBigot(1)
var numberOfMovers = (! hideABed) ? 3 : 0;
While a student, I looked after the apartment of a friend of mine, who was overseas.
When he moved there, we were _just_ able to eke his sofa around the last corner from the stairwell and through the door to his apartment. Just. After much cursing and several failed attempts.
So, what does a good (cough) friend do while the owner is overseas?
Get some hardwood mouldings/trimmings/whatever you call those long, thin pieces of wood typically put where wall transitions to ceiling or floor and nail them to the exterior doorframes, making both door openings perhaps 3/8" or so narrower, paint them in the color of the doorframe, sit back and wait.
Then, years later, as he is about to leave town, moving company comes along and everything runs smoothly until one item remains. The sofa. Obviously, it got in - so it'll (as obviously) come out. Only it doesn't.
We (everybody except the owner and the moving guys were in on the joke) managed to keep a straight face for several minutes.
The moving guys even laughed as they (eventually) left, mollified by a bottle filled with a Scottish export product which we'd kept on hand to ensure no feelings were hurt afterwards.