The lion and the zebras II: The lion with millimeter-long claws

Question

This is a variant of this excellent question. The rules of the lion-zebra hunger games are exactly the same:

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 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 difference? The lion's victory condition is not to catch a zebra, but instead to get within a leisurely 1mm of one. Who wins, the lion or the zebras? Disclaimer: I don't know the answer to this version. I'm legitimately interested.

Point of advice: non-rigorous ideas are super welcome, but I advise you label them as such. The original question has three deleted answers and two answers with a negative score. Tread carefully, lest ye trip over the pile of skeletons lining your path.

Answer 1

Zebras can always win if the lion claw length $r=0$, but the lion wins with claws $r>0$. When the lion has claws, the safety-buffer distance $b$ would have to grow with the number of chasing turns $n$, which would mean the zebras would need to define infinitely large buffer zones to never be caught. Alternatively, if the zebras know the lion will get-bored/tired/starve-to-death within $n$ turns, then they could still always win even when $r>0$ (however finite-$n$ rules would allow a large number of other simpler solutions like "everyone stand $(n+1)R$ from the lion").

(This solution just writes up the math of @Lopsy's $r=0$ solution to show how it kind-of works with claws. Originally my solution here (incorectly) stated that the zebras could always win, but there was a math goof in that proof [as pointed out by @Veedrac @Lawrence @Sophit] that has now been fixed to show that this strategy only works for declawed lions.)

Re-stated rules:

The lion "team" and the zebras teams take turns moving (assume the lion moves first). During any team's turn only one team member may move. Both the lion and the zebras can move distance $R$ during their turn. If a lion gets within distance $r$ of any zebra at the end of either team's turn, then any such zebra becomes lunch and the lion wins.

Zebra's Strategy Playbook:

1. All of the zebras will line up along an east-west line with a distance of at least $2(R+b)$ between every two adjacent zebras; make sure everyone starts at least $(R+b)$ away from the lion. (Everyone chooses the same distance $b>\sqrt{2nRr+r^2}$)
2. The land between the points $(R+b)$ east and $(R+b)$ west of each zebra's starting location is considered part of that zebra's zone; all zones continue northward and southward without end. If the lion ends its turn in any zebra's zone*, then that zebra will use the zebra team's turn to escape by running either due north or due south, whichever direction will end up further from the lion**.

*If the lion ends its turn between two adjacent zebra zones (zebra zones cannot overlap but could be separated by excess distances), then whichever zebra is currently closest to the lion will run away, in the event that both are equally far from the lion, then the western-most of the two will run (either is fine, but we want to flesh out the zebra algorithm).

**If the lion ends its turn directly east (or directly west) of the about-to-run zebra such that escaping either north or south will lead to an equal separating distance at the end of the zebra's turn, then the default tiebreaker choice is to run south.

How It Works:

Every time the lion ends its turn the Zebra's algorithm chooses a move that will put a nearby zebra further down it's predetermined escape path by the maximum distance allowed by the distance-per-turn rule. Because all zebras have their individual non-overlapping zones, no two zebras will ever have to fight over a turn and because all escape paths are parallel no lion-move will force a zebra into any area that might jeopardize another zebra.

By defining their zebra zones as infinite north-south strips of land with $(R+b)$ to both east and west directions the zebras are ensuring that the lion never comes closer than the distance $b$ to any zebra at the end of the lion's enter-a-zone step. This is because the lion, when entering a zone from distance $s$ south of the zebra's current latitude and distance $w$ west of the zebra, starts at a distance $h=\sqrt{(R+b+w)^2+s^2}$ away and can move at most $R$ toward the zebra. Because the four variables are all real distances, $h$ is minimized when $s\to0$ and $w\to 0$ and the lion is entering a zone by moving perpendicular to its edge. This zebra will then move north-or-south as per the algorithm in order to put more distance between the lion and itself. At this point the lion can either pursue this zebra, or try its luck moving to another zone.

(This diagram is rotated so that the image resolution wouldn't be super tall and weird.)

Once a lion is in a zone and perusing a single zebra, the following condition occurs: The north-west distance between the lion and zebra $b$ forms the base of a right triangle, and the distance the chased zebra travels makes the side of the right triangle with distance $nR$ (where $n$ is the number of turns un-captured). The lion travels the shortest distance by moving along the hypotenuse distance $nR$ in $n$ turns, but because of its claws $r>0$ will win if $(nR+r)>b^2+(nR)^2$ (the zebras would need for the $n$th red circle as shown in the picture above to have radius larger than $r$). Solving the equation for the buffer distance gives $b>\sqrt{2nRr+r^2}$ for a zebra win. However, this safety-buffer distance requires the zebras knowing the game will end in a finite number of turns; because the game is assumed to allow an infinite number of turns this means that this zebra north-south strategy will fail for any $r>0$ (though it will definitely still work for any choice of $b>0$ in a $r=0$ game).

Answer 2

Zebras win with an up (or down) and across strategy.

Start with Lopsy's idea of vertical strips, with each strip 400m wide. We call a strip empty if it contains no zebras (it may contain the lion). For convenience, referring to a strip without qualification refers to the middle of the strip. The lion is near a zebra if it is within 100m of the zebra horizontally and vertically. The lion approaches a zebra if it is within 100m of getting near the zebra. The lion departs from a zebra if it moves from near to not near the zebra across a pair of consecutive lion-moves.

Reset state: the lion is not near any zebra, each zebra is in the middle of an otherwise empty strip, and it is the zebras' turn to move. Due to the distribution of zebras, $l$ cannot approach more than one zebra simultaneously from a reset state.

Start the game in a reset state. Zebras win if either the lion makes an infinite but unsuccessful pursuit or the animals re-establish a reset state.

Consider a reset state and let $z$ be the first zebra that the lion $l$ approaches. Set $t=0$ when $l$ first approaches $z$, and increment $t$ after each turn. Let $v(t)$ and $h(t)$ be the respective vertical and horizontal separation of $l$ and $z$ upon completion of turn $t$.

Case 1: $v(0) > 1$mm: $z$ flees vertically to maintain or increase vertical separation. So $l$ either continues pursuit indefinitely or re-establishes a reset state by departing from $z$.

Case 2: $v(0) \leq 1$mm, whence $h(0) \geq 100$m (definition of 'approach'). Then $z$ flees vertically for up to a distance $d$ to a point (call it $s$), where it flees horizontally. From my other answer to this puzzle, it suffices to have $d < 5000$km. We can apply a safety margin of 10% and require $d < 4500$km (call this Condition $c_d$), at which point the horizontal separation is at least 10m, give or take up to 1mm (call this Condition $c_h$).

First, we find the minimum horizontal distance $m_h$ from $s$ to an empty strip. In the worst case, $z$ is the last zebra on either side of the herd, the herd occupies 100 adjacent strips, and $l$ chases $z$ through the herd. So $m_h = 100 * 400$m, i.e. 40km.

Assuming we found $s$, if $l$ departs from $z$ on the horizontal run and moves to between 200m and 300m vertically from $z$, $z$ is free to run to the nearest empty strip on either side. By the pigeon-hole principle, the nearest empty strip on one side will be at most $m_h/2 = 20$km away. When $z$ arrives, $l$ is at most 20.3km away vertically from $z$. Accounting for $v(0)$ and a 200m buffer between $l$ and its new target, let's allow 21km vertically between $z$ and the zebra nearest to it. With zebras vertically spaced most inconveniently at intervals of just under double this distance from each other (42km), $z$ will find $s$ within $100 * 42 = 4200$km of its starting point, so $d = 4200$km. This satisfies Condition $c_d$, so $s$ exists for any distribution of zebras in a reset state.

We now continue by breaking case 2 into 3 sub-cases.

Case 2a: $l$ departs from $z$ while $z$ is still fleeing vertically (before $z$ reaches $s$). This re-establishes a reset state.

Case 2b: $l$ never stops pursuing $z$. Then $z$ runs vertically to $s$ and flees horizontally towards the nearest empty strip and keeps going. From Condition $c_h$, $z$ can then maintain a separation of at least 10m indefinitely.

Case 2c: $l$ pursues $z$ to a horizontal run, then departs to pursue some other zebra: $z$ keeps going until $l$ is between 200m and 300m away vertically, then proceeds up to 20km from there to the nearest empty strip on either side. Upon $z$'s arrival, $l$ is at least 680m away from its new target. Even if we allowed an additional safety margin of another 200m, this re-establishes a reset state. Note that since $l$ is more than 100m away vertically from $z$ at the time of $z$'s final up-to-20km horizontal dash, $l$ cannot catch $z$ by retargeting $z$ during that dash due to similar reasoning to that which established Condition $c_d$.

So the zebras win.

Answer 3

This answer just formalises Lopsy's description to help explore alternatives.

In the scenario Lopsy intended, the zebras are confined to the centre line of strips parallel to the $y$-axis. The strips are any width over 200m. The zebras start with a $y$ coordinate of more than 100m and the lion starts at (0,0).

Let's recast the problem so we can ignore most of the zebras. The lion still starts at (0,0), but this time, the zebras start with $y=0$ and either $x>100$ or $x<-100$, that is, at least 100m away from the lion. The lion's first move is to enter one of the strips along the $x$-axis.

The problem now essentially resets every time the lion changes strips, so without loss of generality, the problem reduces to a single lion chasing a single zebra along an arbitrarily wide strip, with the lion starting at (0,0) and the zebra starting anywhere else on the $x$-axis, with the zebra going first.

The question is whether the lion can get within a fixed distance of the zebra by following a path almost parallel to the zebra's, given the same speed for both animals.

Consider the triangle formed by the two trajectories and the x-axis. Let $l$ and $z$ be the lengths of the sides along the lion's and zebra's trajectories respectively, and let $b$ be the initial distance between the two animals, also the length of the base of the triangle. By Pythagoras' theorem, $l^2 = z^2 + b^2$. Since $b$ is constant, given the angle $\theta$ opposite the base, $z$ is unbounded as $\theta$ approaches $0$. So $\lim_{\theta \rightarrow 0} l = z$.

That is, the lion can get arbitrarily close to the zebra, so the lion wins.

Let's look at some actual values.

If we have $l-z = 0.001$ and $b=100$, then from $l^2 - z^2 = b^2$, we have
$$ (l-z)(l+z) = b^2, $$ and substituting known values, we have $$ l+z = 10^7 . $$

So given $l \approx z$, each animal would have had to run about 5000km.

If the lion was level with the zebra and 100m away horizontally at the start, the critical point occurs when the zebra is 0.5mm shy of 5000km. So if both animals always took maximal 100m steps on constant trajectories towards the critical point, the zebra would be fine up to the step before 5000km (i.e. at 4999.9km) even after the lion's next move, but on reaching 5000km, the zebra would be caught on the lion's next move.