wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> A new riddle? a barge in an L-shaped canal
(Message started by: UncleSerge on Aug 22nd, 2007, 2:16pm)

Title: A new riddle? a barge in an L-shaped canal
Post by UncleSerge on Aug 22nd, 2007, 2:16pm
25 years ago I came across a wonderful mathematical problem, and only now I was able to solve it.  ::)

So I wanted to suggest it here, if you still add new riddles.

Determine the maximum area (and the shape) of the barge that can pass the L-shaped canal of width 1. (The movement is strictly in the two-dimensional plane, and the turn is at the 90deg angle.)

The answer is known (and it is one of the most elegant values I've ever seen); the maximality proof is not very strict but I believe can be made.

Title: Re: A new riddle? a barge in an L-shaped canal
Post by UncleSerge on Aug 22nd, 2007, 2:25pm
Apparently, also known as a "sofa (or a table) in the corridor" problem.

It was mentioned here -
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1090518205;start=12#12

...but not discussed at any length

Title: Re: A new riddle? a barge in an L-shaped canal
Post by towr on Aug 22nd, 2007, 2:55pm
It has been a long time since riddles were last added to the 'main' site, but it seems like a perfectly good puzzle to ask on the forum (probably medium).
If you want I can move it there.


In the meanwhile I'll give the puzzle some thought.
(At the very least we can start with the minimum of a 1x1 square barge)

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Serge Batalov on Aug 22nd, 2007, 3:02pm
Sure thing. I'd even suggest - hard. Seriously.

It came up on our local forum (and then I remembered it from my youth) and it took 425 posts to get anywhere near the real answer. It was a big hit. (Of course approximately 300 posts there were nonsense, not helping the topic.)

P.S. Our forum is in Russian, so  there's little danger of users getting any luck "netting"/googling for the real solution. I did the web-search though, before getting a rather drastic approach to solving. Didn't find anything useful.

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Serge Batalov on Aug 22nd, 2007, 3:03pm
A hint: the answer is a number ...rather more than 2.

The other good starting point is a half-circle of R=1, so it's already > pi/2

Title: Re: A new riddle? a barge in an L-shaped canal
Post by mikedagr8 on Aug 22nd, 2007, 6:43pm

Quote:
The answer is known (and it is one of the most elegant values I've ever seen);


phi? Is approximately pi/2. Not quite, but it is close.

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Serge Batalov on Aug 22nd, 2007, 6:55pm
I retract the statement about elegance. I only recently learned that the answer that I had in mind, [hide]pi/2 + 2/pi (that's approx. 2.207...)[/hide] had been proven wrong. The true answer is larger still. However, it is excedingly ugly.

Still, if one tries to solve this problem without searching the internet and gets to the point of the value [hide]of pi/2 + 2/pi[/hide], I expect that one to be very pleased - not with the number! With the road traveled and with the form of the barge that leads to that answer.

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Barukh on Aug 23rd, 2007, 9:09am

on 08/22/07 at 18:55:37, Serge Batalov wrote:
The true answer is larger still. However, it is excedingly ugly.

Really?! I didn't know this problem is finally solved. It appeared on several "Unsolved Problems" lists, the last I saw dated Dec 1999.


Quote:
[hide]of pi/2 + 2/pi[/hide]

One of the papers written back in 1992 presents a solution with value [hide]2.2195...[/hide], and conjectures it's the unique optimal solution.

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Hippo on Aug 23rd, 2007, 1:08pm
Nice problem, easily googelded ... the solution with [hide]2/pi+pi/2[/hide] is visibly not optimal. The two corners touching the wall all the time will be skived.
This does not decrease the area much but now the sofa can go through the corner not touching the walls at all [edit]touch in the corridor corner it complicates, but not too much ... compare inner/outer curve lengths ... oops [hide]the area is increased by 2 not by outer length ... this is why 2/pi was chosen[/hide] so no such easy argumet[/edit] ... this allows you to add some material on much longer "opposit side". ... find (and check) the optimal solution is not so trivial and I vote for letting it in the hard section.

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Hippo on Aug 26th, 2007, 7:51am
Not a progres ... but formalism:

OK, if one insists on having two points which touch the inner wall all the time, the shape of the sofa is determined by their distance ... shape cut from convex closure is Thalet halfcircle, convex clousure is rectangle of 1xpoints distance unioned with 2 quadcircles with radius 1. The area can be easily established and optimised the points distance.

If we resign on the condition of two points touching all the time, the sofa is much harder to describe. I suggest to define two functions depending on time ... one is angle of the sofa going from 0 to pi/2, the other is "corner curve" ... possition of the point cut from the convex closure by the corridor corner.
In the above, one can use angle = time and the corner traveling the Thalet halfcircle with twice angle speed ...
... I expect, the corner is always touched in optimal solution, but I am not sure both inner walls are touched all the time in optimal solution.
This description determines the sofa, but computing its area is not easy. Finding optimal corner curve is not easy at all.

(Definition with 2 functions is needed as for one angle there can be a cutting line in general so dependency on angle is not a function in that case)

Title: Re: A new riddle? a barge in an L-shaped canal
Post by Bojan_Basic on Jan 27th, 2008, 1:33am
This problem is still open (that is, the largest known figure has not been proved optimal yet). You can find more information here (http://tinyurl.com/3zlt6s) and here (http://mathworld.wolfram.com/MovingSofaProblem.html).



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board