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
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:
- 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}$)
- 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).
No comments:
Post a Comment