Math Puzzle: Lion in Circular Cage Puzzle(pratikpoddarcse.blogspot.in)
pratikpoddarcse.blogspot.in
Math Puzzle: Lion in Circular Cage Puzzle
http://pratikpoddarcse.blogspot.in/2012/02/lion-in-circular-cage-puzzle.html
44 comments
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?
It really just depends on how you model time and space. Assume that the lion and man are on a hex grid and the lion is 1 unit from the man. The man can now move to 3 spaces without being caught and change his orientation relative to the lion, which assuming the grid is reasonably large allows for him to move along a closed loop though space which means he can stay alive.
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.
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.
what part of this question makes it a possibility that they're on a grid and can only move in 4 directions? in regular world (which is used to host this riddle) humans and animals can move diagonally as well.
Let's change the rules slightly. Take a ring one mile in diameter and assume the lion needs to get within 1 foot of the tamer. They both move at 1 inch per tick of game clock in any direction. To make things simple the the lion goes to the center of the ring, then aims for 2 inch closer to the ring than the tamer. Well the tamer will either go closer to the wall or the lion get's closer to him every second. But while he runs along the wall the lion takes a shorter path closer to the center of the ring, catches him and eats him. Also, if the tamer ever goes closer to the center of the ring in any turn the lion get's closer to him that turn because the lion stays on a line between the center of the ring and the tamer.
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.
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.
[deleted]
from the article:
> 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.
> 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.
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.
28 pages and not a single diagram. This is why I always struggled reading academic papers.
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.
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.
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?
EDIT: someone came just before me. http://news.ycombinator.com/item?id=3617030
EDIT: someone came just before me. http://news.ycombinator.com/item?id=3617030
There's an alternate strategy that relies on time moving in discrete chunks, and both players moving simultaneously. But it's completely dependent on how the space is modelled, which indicates (to me) that this isn't a satisfying / robust / realistic solution.
I believe the Lion can go as close as he wants to the tamer but never have both the same position. If you consider the Lion and the tamer have a size, then in a finite time, the Lion reach 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.
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.
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.
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.
Nope, you're wrong.
Can you elaborate? I was wondering the same thing as yogsototh.
Basically there is nothing preventing the lion from reaching the tamers' coordinates exactly, i.e. it's not a case of the distance only closing "in the limit".
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)
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)
For those curious about the mathematical objects involved:
http://mathworld.wolfram.com/PursuitCurve.html
https://en.wikipedia.org/wiki/Pursuit_curve
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.
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.
Related image from your first link http://mathworld.wolfram.com/images/gifs/purscir4.gif
My problem with this representation is that it assumes the pursuer is unable to "lead" its target. The pursuit curve, as modeled in mathematical representations constrains the pursuer to traveling only on a path that points directly at the pursued.
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.
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.
My problem with this representation is that it assumes the pursuer is unable to "lead" its target.
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.
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.
And yet Lions catch faster prey all the time. Just because something occurs randomly doesn't mean it always results in a net loss for the pursuer. All the time spent in pursuit on an optimized (leading) path results in closed distance. Within the constraints of the cage the pursued can only choose to zig or to zag, so if the lion uses a leading path, and is correct in anticipating directional changes only half the time, he's still going to have lunch sooner rather than later. There are visual "tells" that allow the lion to anticipate directional shifts on the part of their prey, so I'd argue that his percentages will be significantly better.
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.
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.
is there a better word for that idea?
Quantize. :)
Quantize. :)
Thank you! I knew it had to be a word that I knew and had shamefully forgotten.
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?
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?
[deleted]
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.
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.
"...back-to-the-wall position."
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.
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.
Yes, I also have the zig-zag in mind. However, as a point, the lion will never catch him.
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.
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.
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.
I was thinking in terms of the man making random movements at some point. I don't really believe there is a strategy that allows him to avoid getting eaten so the best thing he could do is 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.
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.
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?
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?
That is a different problem as the fox cannot enter the water body. Here both the tamer and the lion can go anywhere in the cage.
I believe you meant to say that the duck wins easily if they both move at the same speed.
You're right, sorry (too late to edit)
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.
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.
the order does not matter because the Lion can move to any part of the cage before starting his pursuit.
my point is, I always mix the real with the hypothetical and get hooked up on details that prevent me from answering questions like this. Lions are very territorial, and respectful of territory. If a lion tamer enters a a cage with a lion already in it then he is invading a lions territory. If a lion enters a cage with a lion tamer in it, the the lion understands that he is invading someone else's territory and is highly unlikely to attack.
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.
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.
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.
If the lion just waits, I bet the tamer will die of dehydration first.
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