(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 at time t because remember he is running at top speed 1 m/s..
Where is the lion ? He is at [because he should be on the line joining the center and the man which has slope .] 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.
, giving us the differential equation (after some manipulation)
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 . Armed with this guess, you can either do some simple high school trignometry/geometry to check that this satisfies the differential equation.
Namely . Here’s a terribly drawn picture to convince you that the semicircle travels distance t in time t (hence the speed is 1m/s)
So after 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 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 seconds. So now he is at a distance for from the center. Here’s a picture to explain that :
Then he does this again and runs for 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 (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 . And also he should stay inside the circle, so it is better that be finite (we can scale to make it land inside the circle). And of course, you should think of the harmonic series, namely for .
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]
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
Use because clearly is bounded by . So you get that and hence
This is a separable differential equation . or . This leads to the solution which gives us or .
Thus or .