26
$\begingroup$

The lion plays a deadly game against a group of $N$ zebras that takes place in the steppe (= an infinite plane). The lion starts in the origin with coordinates $(0,0)$, while the $N$ zebras may arbitrarily pick their starting positions. 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 1 unit away.
  • In the zebras move, one of the zebras moves from its current position to a position at most 1 unit away.

The lion wins if for any $\varepsilon\gt 0$, it can get within $\varepsilon$ of a zebra in finite number of moves. Otherwise the zebras win.

There're only 2 possibilities:

  1. Zebras win for all $N\geq 1 $.
  2. $\exists M$, such that lion wins for all $N\geq M$.

Which possibility is true? (Heuristics are welcome too)


Source: I found this lovely little game from here, where the case for $N=100$ is discussed but remains inconclusive. You may also want to check this, where the zebras have been shown to have a winning strategy if the $\varepsilon$ requirement is dropped (i.e. the lion needs to actually catch a zebra to win instead of just getting within $\varepsilon$ to it).


Edited the question following Ycor's advice in the comment.

$\endgroup$
17
  • 3
    $\begingroup$ Obviously the number $N$ of zebras and the distance (which can be renormalized) are unrelated. So we have one game for each $N$, and one can wonder about small values of $N$ ($N=100$ has no particular significance). For $N=1$ obviously the zebras win. For $N=2$ too (zebras start opposite at distance $>1$hm. $\endgroup$ – YCor Apr 21 '20 at 14:43
  • 4
    $\begingroup$ similar question with a 400 reputation bounty at puzzling.stackexchange.com/q/9155 $\endgroup$ – Carlo Beenakker Apr 21 '20 at 14:43
  • $\begingroup$ @YCor That's true. I copied the puzzle in its original form. It's large $N$ that we are interested in. Not too difficult to show that zebras win for $N=3$, too. So either there's a magical $N$ from which on the lion suddenly wins, or the trend continues and zebras always win. $\endgroup$ – Eric Apr 21 '20 at 15:20
  • 2
    $\begingroup$ Evidently, Eric, you know a lot more about this puzzle than you've included in your question. This leads to people wasting their time, and yours, telling you things you already know. I think you should edit your question to summarize what's already known about the puzzle. $\endgroup$ – Gerry Myerson Apr 22 '20 at 1:21
  • 1
    $\begingroup$ @GerryMyerson I genuinely know very little beyond the source I included in the question, from which my comments also originate. Even the $N=3$ case is a heuristic that I've not pinned down as a proof yet. I'll definitely update the question when I've got something worth to say. $\endgroup$ – Eric Apr 22 '20 at 2:12
8
$\begingroup$

Zebras win for all $N$.

I didn't realize Lawrence's answer in the source is actually sound (or so I think, when I really took some time to read it through this morning). Below I basically adopt Lawrence's strategy for $N$, with schematic drawings to make the argument easier to follow.

The following is a winning starting position for the zebras.

starting position

where $a$ is the distance, to be determined, at which the zebras are able to keep the lion away. Each lane is of width $4+2a$ with zebras horizontally centered.

Strategy for the zebras:

Each zebra mentally draws a square with itself at the center. We specify zebras' strategy to win in each possible situation below:

zebra strategy

  1. If the lion is at the boarder or outside of the square, stay put.
  2. As soon as the lion is inside the square but outside the $2a$ strip marked by the pair of dotted lines (boarder included), zebra move 1 unit vertically away from it.
  3. As soon as the lion is inside the square and the strip of dotted lines, zebra move 1 unit vertically away from it.

The lion never wins by staying in Situation $1$ and $2$.

Strategy under Situation $3$

Situation 3 merits more analysis, because there the zebra can't keep going indefinitely without the lion closing in eventually. How far can it keep going before falling into the $a$ radius of the lion? The answer is that it can go at least as far as $L$, as shown below:

situ3

By Pythagorus, we have $L=1+\frac{1}{2a}$. Notice $L$ can be made as large as we want by adjusting $a$ accordingly. Of course $L$ has to be an integer by zebras' strategy stated above. Let's give a wide margin and say it can go at least as far as

$$L^{*}=L/2=\frac{1}{2}+\frac{1}{4a} \;\;\;\;\; (1)$$

Now the idea for a strategy in situation 3 is this: the zebra choose some point $s$ along its vertical escape path (of length $L^{*}$), at which it flees horizontally away from the lion. The point $s$ should be chosen so that all the other zebras are far away enough from this horizontal escape path. In that case, if the lion changes target during its horizontal pursuit, the escaper would be able to escape to the center of an unoccupied vertical lane before the lion reaches the new target's square, thereby forcing the game back to situation $1$.

How can this be achieved? Notice to escape to the center of the nearest unoccupied lane, a zebra will have to cross a distance at most $N(4+2a)$. Let's take

$$L^{*}=2N(N(4+2a)+2+2a) \;\;\;\;\;(2)$$

Then by the pigeonhole principle, there exists $s$ along the vertical escape path whose nearest vertical distance to another zebra is at least $\frac{L^{*}}{2N}=N(4+2a)+2+2a$. If the zebra turns and flees horizontally at this $s$, the lion will be at least $N(4+2a)$ away vertically from any other zebra's square, as shown below.

horizontal escape

And we're done! If the lion keeps its horizontal chasing, the zebra just keeps running. The horizontal distance between the pair will always be greater than $1/2$ (by $(1)$). If the lion switches target during this chase, it can't reach its new target's square before the old target reaches the center of an unoccupied vertical lane, as shown above.

Solving $(1)$ and $(2)$ gives

$$a= \frac{\sqrt{256N^4 + 256N^3 + 48N^2 +1} + 1 - 16N^2 - 8N}{16(N^2 + N)}$$

The lion will not be able to get within this radius of any zebra.


If my calculation below is correct, by widening the lane (and enlarging the squares accordingly), the zebras can keep the lion at arbitrarily large distance. Let's take the size of the lane and squares to be $2k+2a$, equations $(1)$ and $(2)$ becomes

$$L^{*}=\frac{(a + k - 1)^2 - a^2}{4a}\;\;\;\;\;\;\;\;\;\;\;\;\; (1)'$$

$$L^{*}=2N(N(2k+2a)+k+2a)\;\;\;(2)'$$

Solving $(1)'$ and $(2)'$ for $a$ we have

$$a=\frac{\sqrt{q} + k - 8kN^2 -4kN - 1}{16N(N + 1)}$$

where

$$q= 64k^2N^4 + 64k^2N^3 + 16k^2N^2 + 8k^2N + k^2 - 16kN^2 - 24kN - 2k + 16N^2 + 16N + 1$$

Clearly, $\displaystyle{\lim_{k \to \infty} a(N,k) = \infty}$.

So it seems this game is really skewed to the zebras' side.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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