wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The Lion and the Lion Tamer
        
(Message started by: Eric Yeh on Aug 2^nd, 2002, 2:37pm)

Title: The Lion and the Lion Tamer
Post by Eric Yeh on Aug 2^nd, 2002, 2:37pm

Another fave:

A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted
by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.)

Happy Puzzling,
Eric

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by Jonathan the Red on Aug 2^nd, 2002, 3:50pm

No, of course not. All the lion tamer has to do is stand perfectly still. To catch him, the lion would first have to cover half the distance, then 1/4 the distance, then 1/8 the distance, and so on over an infinite series of midpoints, so he'll never reach him ;)

The serious answer: I haven't really churned the math, but I believe the lion can catch the tamer. First, the lion heads directly for the center of the cage. Then, for each infinitesimal timeslice, the lion moves to position himself on the radius of the circle the tamer is on, plus move himself as closer to the tamer as possible. (Since the lion is closer to the center of the circle than the tamer, he'll have less distance to cover to move to the new radius than the tamer did, so he'll be able to bring himself ever-closer to the tamer.) Since the distance between lion and tamer is constantly decreasing, the lion will catch the tamer. Hope the tamer's got his chair and whip handy.

Side puzzle: why would someone who could run as fast as a lion forgo fame and fortune as the fastest human being who ever lived in favor of joining the circus?

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by Eric Yeh on Aug 2^nd, 2002, 4:00pm

Heh! Jonathan, I like your sense of humor! You're a funny guy. ;)

As far your solution goes: Hmmm, I think you'd better "churn out the math". Ever decreasing distances don't always converge to zero, and even when they do, they do not always do so in finite time (so actually, you're leading joke was quite relevant as an analogy!!!!! :D ).

As far as your side puzzle: How do you know that the lion isn' just old and sickly? ;)

But more seriously, do you have any other puzzles to share?

Best,
Eric

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by tim on Aug 2^nd, 2002, 4:13pm

I've churned the math :)

The lion can catch the tamer with this method, in no more time than it would take the tamer to run a quarter-circle of the cage. It's fairly simple maths:

Let r(t) be the distance of the lion from the center with r(0)=0, and choose units in which the radius of the cage is 1 and so are their speeds.

Then dr/dt = sqrt(1 - r^2) in the worst case,
so r = sin(t). i.e. r=1 when t=pi/2, and the lion has caught the tamer.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by Eric Yeh on Aug 2^nd, 2002, 4:24pm

Nice job guys! Wow, maybe I will start having to post harder stuff!! ;) :)

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by william wu on Aug 6^th, 2002, 1:11am

on 08/02/02 at 16:13:03, tim wrote:

Sorry I don't understand ... I guess I'm a little slow. Particularly the line that says "dr/dt = sqrt(1 - r^2) in the worst case". I guess we're applying Pythagoras? I'm not sure what kind of geometric picture I'm supposed to be envisioning. Why is there a right triangle? Could someone elaborate?

Very interesting problem BTW.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by tim on Aug 6^th, 2002, 4:13am

Yes, it's sort of Pythagorean.

Basically the velocity can be split into two components, radial v_r (in/out, i.e. dr/dt) and tangential v_t (around). These are at right angles to each other, and combine in a vector sum so that the total speed is sqrt(v_r^2 + v_t^2) = 1. This might be easier to see if you draw a diagram for how far inward and around the lion travels per tiny bit of time whenever it moves at an angle.

Now, the lion tamer doesn't want to get any closer to the lion, so his best option is to use all his speed to run around the outside of the cage. Anything else speeds his demise. (I can prove this but hope I don't have to ;) )

The tangential velocity of the lion must then be r to maintain the same angle as the tamer, which increases from 0 at the centre to 1 at the edge. Plugging in v_t = r and using the fact that v_r is a synonym for dr/dt, gives the formula
dr/dt = sqrt(1 - r^2).

There are many other paths that will enable the lion to catch the tamer, I just picked this one because I already knew the solution to the resulting differential equation ;)

Besides, with this strategy the final picture of the lion's path is a nice neat semicircle, which I find elegant :)

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by AlexH on Aug 6^th, 2002, 7:49am

Actually I'd like to see the proof that the tamer can't do better vs. the radial approach you describe. It seems to me he can stretch things out some by playing smarter.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by Eric Yeh on Aug 6^th, 2002, 7:54am

on 08/06/02 at 01:11:20, william wu wrote:

Very interesting problem BTW.

Thx!!! :D

on 08/06/02 at 04:13:58, tim wrote:

Now, the lion tamer doesn't want to get any closer to the lion, so his best option is to use all his speed to run around the outside of the cage. Anything else speeds his demise. (I can prove this but hope I don't have to ;) )

Oh, I'm sure you'd have no problem Tim. :) Anyway, it's as simple as saying that any of his velocity that the tamer uses on radial velocity is wasted, since it can only close the (initially worst-case) distance which the lion is trying traverse.

on 08/06/02 at 04:13:58, tim wrote:

There are many other paths that will enable the lion to catch the tamer, I just picked this one because I already knew the solution to the resulting differential equation ;)

Besides, with this strategy the final picture of the lion's path is a nice neat semicircle, which I find elegant :)

But on the other hand, it's also worth saying that this method is optimal in time (if the tamer uses an optimally lengthening strategy).

Best,
Eric

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by AlexH on Aug 6^th, 2002, 8:11am

Nothing was said about the tamer having to start at one of the edges. Also its not quite that simple: as the lion gets closer to the tamer his dr/dt drops so we need to look more closely than that to really prove anything. I don't have any time this morning but I'll try to come back tonight to elaborate.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by anshil on Aug 6^th, 2002, 9:05am

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by CCCP on Aug 6^th, 2002, 3:18pm

I came up with the same math solution, but then thought of one without any math.

Both the tamer and the lion occupy a certain amount of space (so they shouldn't be reprisented with dots on paper :P). The lion can run around a concentric circle with a smaller diameter than the cage itself, while the tamer runs on the very outside. This is similar to tracks on a stadium, where the inside runner has the least distance to run around a turn. Since the lion has a smaller circumference to run, he'll get closer to the tamer, and eventually be right next to him, at which point the tamer is caught.

And about the tamer not starting at the edge: running away from the lion will eventually put him at the edge. He could also be running in a smaller circle, which is then the same problem with a "cage" of smaller diameter. The only 3rd option is running toward the center, which would just end in a quicker victory for the lion :)

CCCP

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by AlexH on Aug 6^th, 2002, 4:50pm

Just because the tamer will eventually run out toward the rim doesn't mean he can't do better than just staying out there the whole time. This is one of those cases where just because something is obvious doesn't mean its true. ;)

Here is an example:

Lets have the lion start at the center, and the lion tamer start at some point with distance c from the rim. The tamer runs at top speed in an outward spiral such that the ratio of the his distance to the rim and the lion's distance to the rim remains constant. (More generally we could have the tamer determine his vector by some function of the distance of the lion with only a few restrictions.)

For any c in (0,1), assuming my calculations are correct, the tamer actually lasts a little longer than the pi/2 "worst case". After a little algebra we wind up with
dr/dt = sqrt(1 - r^2(1-c^2) / ((1-c+cr)^2 - r^2c^2)))
This is less than sqrt(1-r^2) for all r in (0,1).

I'm not sure what the actual best strategy is for the tamer-- I'll have to look at the problem some more--but just running around on the edge is not optimal.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by tim on Aug 6^th, 2002, 8:15pm

Yes, if the tamer starts off away from the edge then the lion should choose a different strategy. However, the lion's best strategy in such a case kills the tamer even faster than if he starts at the edge.

Remember: the lion gets to choose the origin of the rays he uses to pin the tamer. The center of the cage is not the only choice. If the tamer is not at the edge of the cage already, the lion can choose an origin that gives a more prompt lunch.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by anshil on Aug 6^th, 2002, 10:17pm

What would be the minimum speed the tamer needs to run, so he is save from the lion?

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by tim on Aug 6^th, 2002, 11:24pm

Any speed greater than that of the lion will do. The tamer can circle indefinitely. Consider the lion's speed to be 1-d, and the tamer on the outer edge.

In order to catch the tamer, the lion has to reach r = 1 and have angular position equal to that of the tamer. The trouble is that when the lion exceeds r = 1-d it can no longer keep angular pace with the tamer, and no walls are ever going to get in the tamer's way.

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by Barukh on Jul 31^st, 2003, 2:27am

This problem has a very interesting history. It was proposed by Richard Rado (German mathematician) in the middle of 1920s. For a long time, it was believed that the lion always catches the man :(, and the solution generally accepted was that the lion L should stay on the line joining the man M to the center O of the arena. But in the early 1950s mathematician Abram Besikovitch proved that the right answer is just the opposite: the man could always escape :), although the lion would come arbitrarily close.

All this and more is presented in a wonderful little book “A Mathematician’s Miscellany” by John E. Littlewood. The following is the sketch of the proof in the special case mentioned above, i.e. L always stays on the radius OM. The man runs through the curved path M₀M₁M₂... with the following properties:

1. M_NM_N+1 is straight.
2. M_NM_N+1 is perpendicular to OM_N.
3. The length of M_N-1M_N is given by cN^-p, where c, p are constants and 0.5 < p < 1.

Then, OM_N² = OM₀² + c*SUM _m<=N m^-2p, and choosing c accordingly, the path is enclosed in the arena’s circle. Also, since for every N, lion is on the radius OM_N, the man will not be caught while he is on M_NM_N+1, which is perpendicular to OM_N. Finally, the length of the path is infinite, so the man stays alive for infinite time.

For more details and discussion of the general case, please see the following book:

http://books.cambridge.org/052133702X.htm

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by James Fingas on Jul 31^st, 2003, 10:29am

If I understand correctly, the gist of that solution is that as long as the man's radius is increasing, the lion cannot catch him by staying on the radius OM.

The man makes sure that his radius from the center of the cage is always increasing, using an exponential decay for his radial speed. This takes up only a finite amount of radial distance, but allows him to move radially outwards for an infinite time.

Now we just have to show that there is no way that the lion can change his strategy to beat the man. This should be simple: if the lion is not on the line OM, then the man will use this to his advantage by decreasing the radial distance to the center of the cage.

***** ** ** * * * * * L--O * * \ 7 * * M * ** ** *****

The man runs in the direction indicated by the arrow ('7'), and the angle between the line segment OM and the direction he runs is (90 degrees minus half the angle OML). This ensures that the man, although running towards the center, does not get closer to the lion. This fails gracefully when the lion is diametrically opposite the man, in which case the man will stand still.

While the man is doing this, he maintains the current value of N, so that he can resume his previous strategy if the lion gets back on the line OM.

Who would have guessed that the man could escape?

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by Barukh on Aug 2^nd, 2003, 11:47pm

on 07/31/03 at 10:29:19, James Fingas wrote:

If I understand correctly, the gist of that solution is that as long as the man's radius is increasing, the lion cannot catch him by staying on the radius OM.

James, thank you very much for replying to my posting.

on 07/31/03 at 10:29:19, James Fingas wrote:

***** ** ** * * * * * L--O * * \ 7 * * M * ** ** *****

The man runs in the direction indicated by the arrow ('7'), and the angle between the line segment OM and the direction he runs is (90 degrees minus half the angle OML). This ensures that the man, although running towards the center, does not get closer to the lion. This fails gracefully when the lion is diametrically opposite the man, in which case the man will stand still.

This needs some more clarification… Because the direction of the lion is not known, the only thing the man can do to keep his distance from the lion, is to run away on the line OM. But then, he may find himself too close to the outside of the arena.

Besikovitch’s approach doesn’t concern with the distance of the lion to the man. It simply ensures that at each of countably many stages the man won’t be caught.

The same approach works surprisingly well in the general case: the man keeps in mind the path M₀M₁M₂…, but runs through another path M₀R₁R₂… which depends on the lion’s positions L₀, L₁, L₂, … at the end of the stages (a drawing may be helpful here):

1. R_NR_N+1 is perpendicular to L_NR_N (R₀ coincides with M₀).
2. Let O_N be the orthogonal projection of O onto the line R_NR_N+1. Then, R_N+1 is chosen so that O_NR_N+1 equals to M_NM_N+1.

It is immediate from the above, that the lion can not catch the man on the N-th stage for every N. Also, R_NR_N+1 >= M_NM_N+1, so the new path is also infinite. Finally, it’s easily shown that OR_N² <= OM_N², and the man always stays inside the arena.

on 07/31/03 at 10:29:19, James Fingas wrote:

Who would have guessed that the man could escape?

Besikovitch loved to find unexpected answers to hard problems. Here’s another problem of this kind (solved by him in late 1920s):

What is the minimal area of the figure having the following property: a unit length segment can make a full turn (360 degrees) inside it by a continuous motion?

Title: Re: NEW PROBLEM: The Lion and the Lion Tamer
Post by James Fingas on Aug 5^th, 2003, 10:48am

Zero.

I'm still thinking about Besikovitch's solution to the general case. It looks fairly solid ... but I still think mine may work.

Title: Re: The Lion and the Lion Tamer
Post by titan on Oct 15^th, 2013, 11:13pm

In Besikovitch's solution,
1) Why shud tamer move at a path, a line perpendicular to the line joining tamer and lion, that gets him closer to the center of cirlce when he has two options?
2) Why have the increments been chosen to be the terms of a harmonic series?

Title: Re: The Lion and the Lion Tamer
Post by Grimbal on Oct 22^nd, 2013, 12:04pm

1) because there is more space on that side. The fact that the tamer might choose his side guarantees that the lion cannot make a shortcut to catch the tamer. If the lion is a bit ahead, the tamer just turns to the other direction and the lion is behind.
2) Because the sum of the terms diverges, giving an infinite distance to run. But the sum of the squares converges, which means if he gets squeezed to the border, it is only by a finite distance.