The lion and the zebras

Question

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.

Answer 1

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.

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:

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:

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.

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.