52
$\begingroup$

The lion plays a deadly game against a group of 100 zebras that takes place in the steppe (= an infinite plane). The lion starts in the origin with coordinates $(0,0)$, while the 100 zebras may arbitrarily pick their 100 starting positions. The the lion and the group of zebras move alternately:

  • In a lion move, the lion moves from its current position to a position at most 100 meters away.
  • In a zebra move, one of the 100 zebras moves from its current position to a position at most 100 meters away.
  • The lion wins the game as soon as he manages to catch one of the zebras.

Will the lion always win the game after a finite number of moves? Or is there a strategy for the zebras that helps them to survive forever?

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ If zebras choose a place at an infinite distance,then lion can never catch them even if zebras arent allowed to move, for a simple reason that 100m covered by lion is a finite number & he needs to catch zebras in a finite no of moves, so the product of two finite numbers(100 & #no of moves) can never be infinite.So this would make the puzzle itself meaningless.So it must be mentioned that zebras can take position at a finite distance from lion only. $\endgroup$
    – Sumedh
    Commented Feb 16, 2015 at 20:16
  • $\begingroup$ I think the above solutions ignore the fact that the zebra the lion is chasing chasing is not necessarily the one it will catch eventually. He needs to employ a strategy where he is approaching the majority of the Zebras at some stage. There are 99 zebras not moving. In the "solution" above the Lion would chase one zebra until above the rest and the majority were below and to the right (for example). Then come back down straight at the nearest zebra. The goal to force the nearest zebra towards other zebras. A soon as that zebra branched away the lion changes it attention to pushing another zeb $\endgroup$
    – user9584
    Commented Feb 17, 2015 at 5:26
  • 8
    $\begingroup$ @Sumedh All positions on an infinite plane are at a finite distance from the origin. There is no need to mention that. $\endgroup$
    – JiK
    Commented Feb 17, 2015 at 7:41
  • 2
    $\begingroup$ @JiK,yes you're right,but some of the answers given below consider initial distance between lion & zebras infinite.thats the reason the need arises to explicitly mention, as not everyone understands it implicitly. $\endgroup$
    – Sumedh
    Commented Feb 17, 2015 at 12:13

4 Answers 4

Reset to default
62
$\begingroup$

Zebras win.

Here is the strategy:

The zebras choose 100 vertical strips on the steppe, each of width 300m. The strips do not intersect. Each zebra promises to stay horizontally centered on its own individual strip.

 

If the lion enters a strip, then the zebra in that strip flees vertically away from the lion until the lion leaves the strip.

It works because:  

The lion cannot kill a zebra on the turn it moves into a strip, because the strips are too wide. And if it is already inside a strip, then the zebra in that strip has just moved 100m away from it, so it cannot catch the zebra.

Improve this answer
$\endgroup$
16
  • 1
    $\begingroup$ +1 Simple, beautiful, gives a concrete explicit strategy, and shows why it is correct. $\endgroup$
    – JiK
    Commented Feb 16, 2015 at 15:14
  • 3
    $\begingroup$ I have a counterquestion. What if the lion's victory condition is not to catch a zebra, but instead to get within a leisurely 1mm of one? If no one sees an obvious answer to this, I'm going to post it as a separate puzzle. $\endgroup$
    – Lopsy
    Commented Feb 16, 2015 at 15:48
  • 3
    $\begingroup$ @Joshua If the zebras adopt this strips strategy, then it is possible for the lion to get 1mm from a zebra. The lion enters a strip at the closest point to one of the zebras, and then chases the zebra vertically at a very very slight diagonal. $\endgroup$
    – Lopsy
    Commented Feb 16, 2015 at 17:27
  • 4
    $\begingroup$ @MichaelRize To give an explicit example: The zebras number themselves $1,2,\dots,100$. The zebra $i$ starts at the position $(300i,0)$ (units are meters here and in what follows). When it is the zebras' turn, they will decide their move by the following algorithm: If the lion's $x$ coordinate is (strictly) larger than $300i-150$ and (strictly) smaller than $300i+150$ for an integer $i$ in $1,2,\cdots,100$, the $i$th zebra will move. Note that this cannot be true for two different values of $i$. (cont'd) $\endgroup$
    – JiK
    Commented Feb 16, 2015 at 17:32
  • 3
    $\begingroup$ @MichaelRize The fact that the lion can go across various strips is considered in the answer. The zebra in the current strip is always more than 100 meters away, and if the lion changes a strip, the zebra in the new strip will immediately jump so that it is more than 100 meters away. $\endgroup$
    – JiK
    Commented Feb 17, 2015 at 6:54
13
$\begingroup$

This is not an answer, but rather a counter to Micael Rize's answer. I don't intend for this to be picking on him, but it is too difficult to explain in a comment, and there are many arguments about his answer, so hopefully this will be persuasive.

In my example, I am going to use only 16 zebras, but it should be obvious that this is can extend to 100 zebras as well.

This is the starting configuration.

Initial configuration

Now, lets say the lion chases the zebra to the east. After the first move, that zebra is the closest, so it will move directly away from the lion. Subsequent moves will bring the lion closer to the zebras adjacent to the zebra being chased, so they will have to move as well, always directly on a path from the origin according to the strategy. After a while (trillions of years), you will have the following setup.

Chased away

Even though the lion looks close to the zebra, since the starting configuration was so immensely large, they are still light years apart and this zebra is in no danger of being eaten. The only reason the lion caught up is that the lion made many more moves than this zebra because the other zebras were forced to move at one point. Now, however, the zebra is able to move every time the lion moves, so can stay in front indefinitely.

In any event, this is where the lion changes tactics. Instead of chasing down the current zebra (pointless), he heads straight north. The zebra will continue to move outwards since it is still the closest. Eventually, you will get to the point where it is no longer the closest zebra, like so.

New Target

Now the lion turns back to the pack and chases the closest zebra in the circle (Red). According to the strategy, this zebra can only move outwards from the origin which gets closer to the lion obviously allowing the lion to capture it. The other option along this path is to move closer to the origin. While this is away from the lion, it will eventually meet and surpass the other zebra in red on the opposite side of the circle. Even if we ignore the fact that the other zebras will all move a bit as the lion runs through the centre of the circle, the lion is now chasing two zebras. According to the strategy, they can only move away from the origin, so they will always stay together. Thus, the lion is twice as fast as them and will catch one eventually.

There are probably different strategies that this zebra can take to avoid capture (e.g. taking different paths not directly from the origin), but the current answer is not sufficient to explain how to stay away from the lion.

Improve this answer
$\endgroup$
0
3
$\begingroup$

Later: At the time, I was thinking of a solution similar to Lopsy's, but instead of vertical stripes I had an idea of circular sectors. Each zebra would thus have its own angle of 3,6°. Here is how I put it to words back then:

Zebras can win.

This is not a rigorous proof, but a good proof nonetheless.

The game is lost, if a lion can pick a new point $P$, such that at least two zebras are contained in a circle with a center at $P$ and radius of 100m. That is obvious, then only one zebra can escape in the next turn and at least one gets eaten.

So our objective is: after every zebra move, all zebras have to be more than 100m away from each other - this guarantees lion cannot make a move that would capture two zebras in the same 100m radius circle.

Since a zebra can move 100 meters, that just means it has to have some free space in some direction, e.g. it can move to a new point, not falling into 100m radius of another zebra.

This is easily achievable if we initially place zebras on the border of any convex shape, such as a circle of a square of an adequate size (adequate means each zebra is more than 50m apart).

Improve this answer
$\endgroup$
5
  • $\begingroup$ "all zebras have to be more than 50m away" Presumably you mean 200 m? $\endgroup$
    – JiK
    Commented Feb 16, 2015 at 14:00
  • $\begingroup$ I guess that the lion can start chasing one zebra and get outside the convex shape formed by other 99 zebras, and then it can start chasing one of the other zebras, forcing it to go inside the shape, so the shape would not be convex anymore. Am I missing something? $\endgroup$
    – JiK
    Commented Feb 16, 2015 at 14:02
  • $\begingroup$ I mean 100m apart. Thanks. Let me think a little. :) $\endgroup$
    – Rok Kralj
    Commented Feb 16, 2015 at 14:03
  • $\begingroup$ Keep in mind the zebra ALSO has to be 100m away from the lion :) $\endgroup$
    – Duncan
    Commented Feb 16, 2015 at 15:03
  • $\begingroup$ As JiK said, the zebras will need to stay more than 200m apart in order for there not to exist a point P that is within 100m of each of them. Also, you don't prove that it's not possible for the lion to force a zebra to jump within 200m of another zebra. Just being a convex shape won't do it, as the lion should be able to eventually get outside (as only one zebra can move at a time) and start chasing the zebras in toward each other. $\endgroup$
    – glibdud
    Commented Feb 19, 2015 at 20:08
-13
$\begingroup$

Answer

Quick answer: The zebras would survive forever.

Simple explanation:

The key concept here is "infinite plane". Since the plane is infinite, positioning is irrelevant, except for the fact that the zebras are placed at great distances from each other and the lion. The closest zebra from the lion simply moves away from the lion in a direction that does not bring it near the path of another zebra. Because the plane is infinite, the zebras can be a nearly infinite distance from each other, thus making their escape paths very easy to avoid other zebras.

Improve this answer
$\endgroup$
66
  • 4
    $\begingroup$ The lion could go round a nearby deer (100-200m) such that 2 deer lie on the same line. Then he could chase the near one, and eventually encounter the far one. The angle of choice of direction for a particular deer is determined by its distance from the lion, so a more elaborate proof will be required. $\endgroup$
    – ghosts_in_the_code
    Commented Feb 16, 2015 at 12:57
  • 3
    $\begingroup$ "trillions of light years away" <> infinity :) $\endgroup$
    – dmg
    Commented Feb 16, 2015 at 13:23
  • 4
    $\begingroup$ For all intents and purposes, 10km (100km) is the same as "trillions of light years" in this case. $\endgroup$
    – No. 7892142
    Commented Feb 16, 2015 at 13:34
  • 14
    $\begingroup$ @MichaelRize We are trying to do something constructive - trying to help you see why we think this is not a complete and convincing answer to the question. $\endgroup$
    – JiK
    Commented Feb 16, 2015 at 17:37
  • 5
    $\begingroup$ You're describing what a strategy should do, but you're not actually providing one. $\endgroup$
    – glibdud
    Commented Feb 21, 2015 at 16:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.