5 ms·

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 puz

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.
    - onemoreact 15y ago
      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.
- deleted 15y ago
  [deleted]
- andylei 15y ago
  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.
ranit8 15y ago
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 http://news.ycombinator.com/item?id=3617030
- yogsototh 15y ago
  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.
- screwt 15y ago
  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.
nonce43 15y ago
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.
andrewingram 15y ago
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.

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.
  - onemoreact 15y ago
    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.
deleted 15y ago
[deleted]
andylei 15y ago
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.

ranit8 15y ago

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 http://news.ycombinator.com/item?id=3617030

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

nonce43 15y ago

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.

andrewingram 15y ago

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.