The Lion and the Man

(apparently was known as the Lion and the Christian)

Attended a really nice colloquium about this problem at school yesterday. So the problem is as follows :

A lion and a man are placed in a circular arena of radius 1m (think ancient Rome). Both can run at equal top-speed 1 m/s say. Imagine the man and the lion to be points. The lion wants to catch the man and the man wants to escape being caught by the lion. Let’s assume that after time T, both man and lion are so tired that they decide to not move anymore. So er.. the “game” ends when the lion wins (catches the man) or after time T, the man is still alive (not caught by the lion). Is there a winning strategy for the man, is there a winning strategy for the lion, is there perhaps no winning strategy for either player or are there winning strategies for BOTH ?? (can that ever be possible)

Of course, being a mathematician, you allow your arena to be any compact metric space and wonder what happens if the space is not compact etc etc. And if you are interested, you can also see by what distance the man escapes the lion throughout the game, and what happens if you allow T to become larger and larger … i.e., the unbounded time game

This problem came into being in the early 1900s, after being posed by a mathematician called Rado and was tackled by the amateur mathematicians with great enthusiasm. Here are a few early attempts. (Let’s say the lion is at the center of the circle) :

  • Say the Lion decides to just run straight towards the man, wherever he is. That is an obvious strategy, but maybe it is not very good for the Lion though. If the man decides to keep running around the circumference of the circle, say. Then what happens ?
  • It was widely believed that the best the man could do was run around the circumference of the arena at his top speed. But then the Lion could have the following (better) strategy. It decides to be on the line joining the man and the center always, running at top speed 1 m/s …

Let us see what happens in this case [high school trig alert]. Assume the man starts at (1,0). Then at time t, he is at (\cos t, \sin t) at time t because remember he is running at top speed 1 m/s..

man

Where is the lion ? He is at (f(t), f(t)\tan t) [because he should be on the line joining the center and the man which has slope \tan t.] The question is, what is f(t) ? Note that the lion’s top speed is 1m/s. So the “magnitude” of his derivative would be 1.

\sqrt{f'^2 + (f\tan t)'^2 }=1, giving us the differential equation (after some manipulation)

(f'+f\tan t)^2+f^2=\cos^2 t

At this point, I have forgotten how to solve this differential equation. Is there a nice substitution trick which leads to the solution ? Update : Check the end of the post for a solution

 

But even if you don’t solve the differential equation, with a little vague plotting, you can guess that the Lion will trace a semicircle centered at (0,\frac{1}{2}). Armed with this guess, you can either do some simple high school trignometry/geometry to check that this satisfies the differential equation.

Namely f(t)=\sin t\cos t =\frac{\sin 2t}{2}. Here’s a terribly drawn picture to convince you that the semicircle travels distance t in time t (hence the speed is 1m/s)

 Lionandman

So after \pi/2 seconds, the Lion catches the man. And it was believed that the Lion could always catch the man since the man’s best would be to run around the circle at top speed..

  • It was in 1952, that Besicovitch, a mathematician pointed out that the man could do much better, in fact he has a winning strategy, which is quite pretty to describe.

The man’s strategy is to do the following. Let us say at the beginning, he finds the radius on which he is standing (say he is at distance r_1 from the center) and checks on which side of the radius the Lion is and runs perpendicular to the radius on the opposite side for t_1 seconds. So now he is at a distance for \sqrt{r_1^2+t_1^2} from the center. Here’s a picture to explain that :

Manstrategy1

Then he does this again and runs for t_2 seconds exactly as above .. And if it happens that the lion is on the SAME radius that he is, he makes a choice (say he runs right if this happens at any point in time). Note that therefore it is not a “continuous” strategy, because even if the lion a teeny weeny bit to the right of his radius, he runs left, but if the lion is on the radius, he runs right.

Now, we have to determine t_1,t_2,\ldots (ie, for how long his first run is and how long his second run is etc) Let’s in fact assume we are in the unbounded time game, so the man and the lion run forever, and the man wins if we can prove he will never get caught.

Obviously, we don’t want the man to get caught, so \sum t_i = \infty. And also he should stay inside the circle, so it is better that r^2 + \sum t_i^2 be finite (we can scale to make it land inside the circle). And of course, you should think of the harmonic series, namely \sum \frac{1}{n} for t_i.

Now, is it clear that the man wins? Here’s a picture to illustrate why the Lion can never catch the man. [Note that everything is squared to make avoid square roots in the distances in the picture]

whymanwins

So the man has a winning strategy, yaay!

Now the question the colloqium proceeded to ask and address was whether the Lion could also have a winning strategy… Er, this is a bit weird, how can both players have winning strategies? What is each plays his winning strategy, then you get a contradiction ..? Yes?

Well, this “let each player play his strategy” is not well-defined apparently. If man’s strategy is called S, it means he takes the lion’s path “l” so far and S(l) tells him what happens to his own path “m”. And similarly, if the lion’s strategy is G, then G(m)=l.

The question then would be, why are we guaranteed paths “l”, “m” so that G(m)=l and S(l)=m? That is there is no contradiction in each player having a winning strategy .. (This still blows my mind).

And it turns out for the circle arena, the lion DOES NOT have a winning strategy, but there are compact metric spaces for which both players have winning strategies .. It involved some nice analysis concepts like Ascoli Arzela etc, Brower’s fixed point theorem etc. But for now, let’s be content with Bescovitch’s ingenious solution.

And here’s the paper on arxiv [Lion and Man –Can both win ?] if you are curious.


 

Thanks to Fred, here’s a way to solve the differential equation (f'+f\tan t)^2+f^2=\cos^2 t

 Use f(t) = v(t)\cos t because clearly f(t) is bounded by \cos t. So you get that f'=v'\cos t - v\sin t and hence v'^2 \cos^2 t + v^2\cos^2 t = \cos^2 t \implies v'^2 + v^2 = 1

This is a separable differential equation . \frac{dv}{dt}=\pm \sqrt{1-v^2}\implies \frac{dv}{\sqrt{1-v^2}}=\pm dt or v=1. This leads to the solution sin^{-1}v = \pm t + c which gives us v = sin(\pm t +c) or v=1

Thus f(t)=\sin(\pm t+c)\cos t or f(t)=\cos t.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s