Math Puzzle: Lion in Circular Cage Puzzle
pratikpoddarcse.blogspot.in
pratikpoddarcse.blogspot.in
It's problem 1 in The Art of Mathematics by Béla Bollobás, a challenging puzzle book for serious math junkies. The solution in that book has a good explanation of (a) what you probably didn't think of, and sounds right; and (b) why it's wrong.
And just when you think Bollobás's book had the final word, you found out there are versions of the puzzle when both players can win. What? Don't take my word for it:
If on the other hand the man is moving +/- 1 X and or Y on an XY grid at (1,0) and the lion is at (0,0) then the man must move to (2,Y) or risk being eaten which means his X must increase which mean he will eventually hit a wall.
PS: If the lion can always get within striking distance of the man then there is no difference between moving at the same time and alternating, because the lion can chose randomly and then catch back up on a miss which enables him to win eventually.
The reason my example does not work for this puzzle is simply there is no distance closer the the center of the ring the lion can aim for and still get to eat him. At which point you need to think about what space looks like for points that are really close to each other.
> We split time into a sequence of intervals, of lengths t1, t2, t3, . . .. At the ith step the man runs for time ti in a straight line that is perpendicular to his radius vector at the start of the step. He chooses to run into the half plane that does not contain the lion (if the lion is on the radius then either direction will do). So certainly the lion does not catch the man in this time step. The man then repeats this procedure for the next time step, and so on.
EDIT: someone came just before me. http://news.ycombinator.com/item?id=3617030
For a problem like this when the first thing I did was have a picture of it in my head, I would have expected diagrams to be essential.
1. Lion runs to centre of ring
2. Lion moves toward tamer, but always staying directly between tamer and centre.
Eventually the tamer reaches the edge of the ring and can no longer move directly away. Then the lion can continue to move outward, always between the tamer and centre, until they meet, and the lion eats.
The paper linked elsewhere here gives an illustrative example where this happens in what is clearly finite time.
(This is if the tamer is on the border as parent claimed - the paper also shows that the lion can't win if he doesn't do this)
If you model this, you will probably get very different answers based on how well you discrete-ize (is there a better word for that idea?) the time and movement.
Also, it's not a turn based game, i.e. the man doesn't move and then the lion moves. They move together at the same time. I think if you could answer what happens if the man has his back to wall and the lion is as close as possible without catching him, then you would solve the problem. Because the lion has to predict where the person is going to move next, it feels like you won't ever know for sure what will happen. As time tends towards infinity, the lion will probably eat the guy due to sheer chance of both of them going the same direction at the right time.
Lions are highly adapted hunters that frequently take down prey that are much faster than them. It would seem that they would have to develop strategies for optimizing the distance-to-intercept in order to be successful as a species.
Thus, I believe the man is eaten rather quickly, even if the two are equal in speed.
How can the pursuer lead the target when the target moves randomly? At best, he can adjust his lead with an infinitesimal delay, but its not clear this allows him to catch the target in finite time.
I guess I'm struggling with understanding the value of the exercise. If we're talking inanimate bodies, I get it. This kind of physics is valuable. However, choosing arbitrary constraints in order to make interesting maths out of natural scenarios is low hanging fruit. I just don't see it as all that interesting.
The better strategy for the lion is your back-to-the-wall position. The lion should be able to get infinitesimally close to the tamer. Pragmatically and finally, the delta will be smaller the reach of the lion's pawns. Lion wins.
Can you expand on this? My thought was that if the lion 'zig-zagged' somewhat, it would effectively force the tamer to constantly change direction[1] and ultimately the lion would catch up. Is that what you meant by back-to-the-wall?
[1] Assuming that the tamer's only strategy is to maximise distance from the lion.
The lion has to move further to the side than the tamer, so the tamer switches directions after each "step". This works, because within a circle the tamer with his back to the wall has to move a little towards the lion while moving sideways. The lion moves a little bit more to the side a little bit less towards the tamer. Over time the lion comes closer and the steps become smaller. When it gets really close however, the round wall looks increasingly like a flat wall. Lion and tamer end up just moving sideways without ever touching? We need some more math for this.
This is all but obvious to me. I pick a random number from 0 to 2*Pi. If you guess my number correctly, you get to eat me. You can guess an infinite amount of times.
Who wins this game? Does the answer depend on the assumption of fundamental axioms?
Quantize. :)
In traditional pursuit curves, the region in which the chase happens is unbounded. Here, this isn't the case.
The best that the tamer can do if the lion uses this strategy is to move away from the lion. If at any point he is unable to do so (i.e. when he hits a wall of the cage) then the distance shrinks.
Depending on the speeds at which they can travel and the size of the cage, the lion will either catch the tamer in a finite amount of time, or he will asymptotically approach the tamer.
Given that they're point masses, I can't see how speed and size of the cage could affect the solution. Unless the initial distance between lion and tamer also factors in.
A duck is in the center of a circular lake. A fox is on the bank. The duck only needs to reach the bank (without simultaneously being caught by the fox) to win. The fox cannot swim.
If both move at the same speed, the fox wins easily. But what if the fox moves 4× as fast as the duck?
If the lion tamer is in the cage before when the lion enters, then it's unlikely the that the Lion will catch the tamer. Unless there's some other factor, like the lion has been starved, or is nervous.
It's for this reason that you'll never see a Lion tamer enter a cage full of lions. He or She will always enter the cage first, and the lions will follow.
It has no bearing on a hypothetical question, but in reality it would make a huge difference.
I remember as a kid, a math teacher carefully explaining to me why my answer to a question that involved cooking was wrong. The maths assumed you could just increase the quantity of ingredients proportionally to the number of people you were cooking for, but that's not always the case, and in this example I was right in reality, but wrong mathematically.