7 ms·

Math Puzzle: Lion in Circular Cage Puzzle

28 points by pratikpoddar 15y ago

zackzackzack 15y ago
For those curious about the mathematical objects involved: http://mathworld.wolfram.com/PursuitCurve.html http://mathworld.wolfram.com/PursuitCurve.html https://en.wikipedia.org/wiki/Pursuit_curve 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.
- aparadja 15y ago
  Related image from your first link http://mathworld.wolfram.com/images/gifs/purscir4.gif http://mathworld.wolfram.com/images/gifs/purscir4.gif
  - bradleyland 15y ago
    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.
    - gcp 15y ago
      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.
      - bradleyland 15y ago
        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.
- karamazov 15y ago
  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.
  - zackzackzack 15y ago
    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.
- beza1e1 15y ago
  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.
  - amirmc 15y ago
    "...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.
    - beza1e1 15y ago
      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.
- gcp 15y ago
  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?
  - deleted 15y ago
    [deleted]
- hythloday 15y ago
  is there a better word for that idea? Quantize. :)
  - zackzackzack 15y ago
    Thank you! I knew it had to be a word that I knew and had shamefully forgotten.
tylerneylon 15y ago
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: http://arxiv.org/pdf/0909.2524.pdf http://arxiv.org/pdf/0909.2524.pdf
- frooxie 15y ago
  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?
  - onemoreact 15y ago
    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.
    - SonicSoul 15y ago
      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.
Cry_Wolf 15y ago
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.
- gcp 15y ago
  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.
screwt 15y ago
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.
- yogsototh 15y ago
  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.
  - gcp 15y ago
    Nope, you're wrong.
    - skyo 15y ago
      Can you elaborate? I was wondering the same thing as yogsototh.
      - gcp 15y ago
        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)
philbarr 15y ago
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."
- shpoonj 15y ago
  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.
tomelders 15y ago
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.
- SonicSoul 15y ago
  the order does not matter because the Lion can move to any part of the cage before starting his pursuit.
  - tomelders 15y ago
    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.
troymc 15y ago
If the lion just waits, I bet the tamer will die of dehydration first.
SonicSoul 15y ago
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.
finnw 15y ago
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?
- spenceyboi 15y ago
  I believe you meant to say that the duck wins easily if they both move at the same speed.
  - finnw 15y ago
    You're right, sorry (too late to edit)
- pratikpoddar 15y ago
  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.

28 points by pratikpoddar 15y ago

For those curious about the mathematical objects involved: http://mathworld.wolfram.com/PursuitCurve.html http://mathworld.wolfram.com/PursuitCurve.html https://en.wikipedia.org/wiki/Pursuit_curve 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.

aparadja 15y ago
Related image from your first link http://mathworld.wolfram.com/images/gifs/purscir4.gif http://mathworld.wolfram.com/images/gifs/purscir4.gif
- bradleyland 15y ago
  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.
  - gcp 15y ago
    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.
    - bradleyland 15y ago
      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.
karamazov 15y ago
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.
- zackzackzack 15y ago
  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.
beza1e1 15y ago
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.
- amirmc 15y ago
  "...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.
  - beza1e1 15y ago
    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.
gcp 15y ago
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?
- deleted 15y ago
  [deleted]
hythloday 15y ago
is there a better word for that idea? Quantize. :)
- zackzackzack 15y ago
  Thank you! I knew it had to be a word that I knew and had shamefully forgotten.

tylerneylon 15y ago

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: http://arxiv.org/pdf/0909.2524.pdf http://arxiv.org/pdf/0909.2524.pdf

frooxie 15y ago
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?
- onemoreact 15y ago
  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.
  - SonicSoul 15y ago
    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.

Cry_Wolf 15y ago

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.

gcp 15y ago
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.

screwt 15y ago

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.

yogsototh 15y ago
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.
- gcp 15y ago
  Nope, you're wrong.
  - skyo 15y ago
    Can you elaborate? I was wondering the same thing as yogsototh.
    - gcp 15y ago
      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)

philbarr 15y ago

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."

shpoonj 15y ago
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.

tomelders 15y ago

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.

SonicSoul 15y ago
the order does not matter because the Lion can move to any part of the cage before starting his pursuit.
- tomelders 15y ago
  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.

troymc 15y ago

If the lion just waits, I bet the tamer will die of dehydration first.

SonicSoul 15y ago

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.

finnw 15y ago

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?

spenceyboi 15y ago
I believe you meant to say that the duck wins easily if they both move at the same speed.
- finnw 15y ago
  You're right, sorry (too late to edit)
pratikpoddar 15y ago
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.