This is a problem you can be sure you've solved, only to find a twist in the road.
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:
Am I missing something? My reasoning is that the lion will easily catch the lion tamer by moving straight towards him/her. If the tamer moves in the same direction, he/she will eventually hit a wall. If the tamer moves in any other direction, the lion will be able to move at least slightly closer to it. Repeat until caught. Or?
The above link pretty much answers everything. Please, skim the first two pages before replying. It explains why 'curve of pursuit' is the wrong strategy, how the lion can win if the tamer stays on the circumference, why the tamer should not stay on the circumference, and how to make this all mathematically rigorous.
Sorry, i'm too lazy to deeply check teh article. What happens if the lion starts from the center and always moves as to keep the center, himself and the tamer in a straight line? It should do some kind of spiral, but does it take infinite time to catch the tamer?
Assuming both players react instantaneously, and space is modelled as continuous (not discrete), I think the following strategy always wins for the lion.
1. Lion runs to centre of ring
2. Lion moves toward tamer, but always staying directly between tamer and centre.
(2) is always possible, as the arc the lion has to move around to keep between tamer and centre is always shorter than any arc the tamer can move along since the lion is closer in. As a corollory, the lion can always get closer to the tamer unless the tamer moves direclty away from the 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.
I believe it works only if the Lion and the tamer have a non null size (not represented as point). I am not sure of this, but if you represent the Lion and the tamer as points, the Lion can go as close as it want to the tamer, but never really reach him. Of course considering the tamer is on the border.
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.
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.
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?
The pursuit curve assumes that the lion always moves directly towards the tamer.
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.
Letting time go to infinity won't affect the answer - if the tamer has a strategy that allows him to avoid getting eaten, he's going to implement it all times, rather than risk making random movements.
You can conclude that the tamer will be eaten if the lion simply moves towards the tamer.
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.
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.
I have seen a variant of this (but cannot remember where I saw it):
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?
Mathematics aside, is this one of those puzzles where the answer is "of course the lion tamer is not caught - because he's a lion tamer and therefore the lion does not chase him."
There are many holes in the question... Such as asking if it is POSSIBLE. We know that all things are possible, however improbable, so the answer is yes.
I hate questions being phrased like this. I always end up thinking of things like "who entered the cage first", which is important in reality but has no bearing on the mathematical nature of the question.
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.
all the lion has to do is travel directly towards the tamer. any turns that the tamer does create an angle that the lion can cut through.
of course this is the obvious answer, so i'm probably missing something.
[+] [-] tylerneylon|14 years ago|reply
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:
http://arxiv.org/pdf/0909.2524.pdf
[+] [-] frooxie|14 years ago|reply
[+] [-] nonce43|14 years ago|reply
[+] [-] andrewingram|14 years ago|reply
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.
[+] [-] ranit8|14 years ago|reply
EDIT: someone came just before me. http://news.ycombinator.com/item?id=3617030
[+] [-] screwt|14 years ago|reply
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.
[+] [-] yogsototh|14 years ago|reply
[+] [-] zackzackzack|14 years ago|reply
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.
[+] [-] aparadja|14 years ago|reply
[+] [-] hythloday|14 years ago|reply
Quantize. :)
[+] [-] gcp|14 years ago|reply
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?
[+] [-] beza1e1|14 years ago|reply
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.
[+] [-] karamazov|14 years ago|reply
[+] [-] Cry_Wolf|14 years ago|reply
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.
[+] [-] gcp|14 years ago|reply
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.
[+] [-] finnw|14 years ago|reply
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?
[+] [-] pratikpoddar|14 years ago|reply
[+] [-] spenceyboi|14 years ago|reply
[+] [-] philbarr|14 years ago|reply
[+] [-] shpoonj|14 years ago|reply
[+] [-] tomelders|14 years ago|reply
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.
[+] [-] SonicSoul|14 years ago|reply
[+] [-] SonicSoul|14 years ago|reply
[+] [-] troymc|14 years ago|reply