Precision Tag - can the lion win?

Question

This is a spin-off motivated by Lopsy's interesting variant of Gamow's lion and zebras puzzle. It arose from a line of enquiry that tried to extend the vertical run past 5000km (or characterise the distribution of zebras to limit the run to within 5000km). That line of inquiry was eventually discarded but the spin-off puzzle seemed interesting in its own right.

---

Imagine a one-dimensional universe inhabited by 101 spots. Every so often, they play their own friendly variant of the 'lion and zebras' game of precision tag.

One spot is selected as the lion and the other spots (zebras) scatter to wherever they wish.

Goal At the start of the game, the lion nominates a position for each zebra. The lion wins if the zebras occupy those positions simultaneously. The zebras win if they can force the game to continue indefinitely without the lion winning.

Target Zebra One zebra is selected as the target to start the game. At any time, the lion may change the target to any zebra that is between 100m and 200m away, inclusive. For example, it may target a zebra 100m or 150m away, but not one 50m, 99m, 201m or 1km away. There is exactly one target at any given time.

Moves The spots take turns to move up to 100m per turn. On the odd turns, only the lion may move. On the even turns, only the zebra that was the target at the start of the turn may move.

Zebra Move Constraint 1: Non-crossing The target must use its turn to ensure its own position never crosses to the other side of the lion during that turn and during the lion's next turn. For example, if the lion is 50m away and the target starts moving towards it and moves for 80m, their positions cross during that move. Other than this restriction, spots may pass through each other with no consequence. Note that it is permissible for the target to end up at the same position as the lion - this constraint just prohibits crossing to the other side of the lion.

Zebra Move Constraint 2: Attractor The zebras are friendly. Within the positions allowed by the non-crossing constraint, the target will move to the position that minimises its distance to the last zebra it passed.

Can the lion win? If so, how? If not, why not?

Does it make any difference if the targeting distance was slightly modified so that the lion cannot tag zebras exactly 100m or 200m away (that is, change it from a closed interval to an open interval)?

---

Here is an example of placing one zebra at its target point. The game starts with lion $L$ and zebras $X,Y,Z$, with initial target $X$ and initial positions $[L,X,Y,Z] = [-150,0,-100,120]$. All other zebras are far away. The nominated position for $X$ is 140.

Use the notation $L+x$ and $L-x$ to mean $L$ moves $x$ meters towards the positive or negative end respectively. Then we play this out as follows:

$L+100,X+100,L+100$ takes $[L,X]$ to $[50,100]$.

$X$ must move to somewhere between 150 $(=L+100)$ and 200 $(=X+100)$ and therefore passes $Z$. The nearest position to $Z$ in that range is 150, so $X$ only moves $X+50$ to 150. The spots are now at $[L,X,Y,Z] = [50,150,-100,120]$ and $Z$ is the last zebra seen by $X$.

$L-10$ allows $X$ to get closer to $Z$, which it does with $X-10$, bringing $X$ to its target position 140. $L$ is now at 40, and it changes the target to $Y$, which is now in range. This freezes the position of $X$.

In this example, $Y$ and $Z$ are at convenient positions. In the general case, each zebra starts at a random position.

Answer 1

Edited because for some reason everything below gets flagged as spam in a de novo post, but not in edits made to an existing post!

The answer is that

The lion wins.

A discussion (below) of the generality and assumptions of the solution might reveal the answer.

This solution need not assume that the lion knows anything about the positions of the zebras when it nominates the target points. However, it relies on the assumption that the lion may change the target zebra at the end of the lion's turn; i.e. the lion's turn does not immediately and automatically end when the lion completes its move.

To motivate the solution, note the following (lemmas 1 and 2 can be read as hints; 3 and 4 might reveal the solution).

Lemma 1

The lion can always cross to the other side of a group of zebras in a finite number of moves. To accomplish this, the lion needs only to pass the first (stationary because it is non-target) zebra, then designate that zebra as the target and pass the remaining zebras.

Lemma 2

The lion can drive an arbitrary-sized group of zebras ahead of it. To accomplish this, the lion approaches the rearmost zebra until it is close enough to nominate that zebra. Call this zebra "A". The lion nominates A, and continues to move as close to A possible at every turn until the lion and A approach the position of the second-rearmost zebra. Call this new zebra B. The lion drives A past B in the normal way, but on the turn after A passes B, the lion withdraws to a position 100m behind B and nominates B at the end of the turn. After B moves, the lion at the beginning of its next turn nominates whatever zebra is rearmost, and repeats the process.

Lemma 3

A lion driving two zebras A and B ahead of it can place one of them (the lion does not care which one) on any arbitrary single point, with the other still between the target and the lion. To accomplish this, imagine that while driving the zebras in the normal way, A crosses the target first. Note that A has also passed B in this move. Then the lion moves 100m away from the target, so A moves back to the target. The lion then moves 100m away from B and nominates B.

Lemma 4

Continuing from 3, the lion (if it wishes) can then place B on the same target point as A, as follows: If B's next move does not carry it to the target point, the lion moves to within 100m of the target point forcing B past the target point. The lion then retreats to 100m (or more) away, and B moves to the target.

The solution

Solution 1: Target points for different zebras are allowed to coincide. The lion nominates an arbitrary single point for the entire group of zebras. The lion first crosses to one side of the entire group of zebras (possible by lemma 1), and then drives them all to one side of the target (possible by lemma 2). The lion drives the zebras far enough past the point so that it can again cross the group in fewer moves than it would take for any of the zebras to cross back past the target point before the lion finishes crossing the group (possible by lemmas 1, 2). The lion then begins to drive the zebras (all in a fairly tight bunch) towards the target. The lion then repeatedly applies the procedure outlined in Lemma 3 to place all the zebras (save the last one) on the point, and then uses the lemma 4 procedure to place the last one.

Slightly more general solution:

Solution 2: All target points must be distinct. The lion nominates a set of points anywhere on the line. The lion then applies solution 1 to place all of the zebras on the leftmost point, having driven them in from the left (or the rightmost, having driven them in from the right). The lion then repeats the process for all zebras except the one that was targeted for the leftmost point, moving them to the second leftmost. And so forth. When the 99 leftmost points are all occupied by the appropriate zebras, the lion targets the last zebra and pushes it past the rightmost target, then retreats so that the zebra must move exactly onto that point.

Does it make any difference if the targeting distance was slightly modified so that the lion cannot tag zebras exactly 100m or 200m away (that is, change it from a closed interval to an open interval)?

As far as I can see, this does not make a difference for these solutions. Considering the lemmas separately, I fail to see where any of them is compromised by this slight modification.

Edited to add (in response to Trenin below--I don't have enough reputation to comment on her/his answer): 1) I don't see any constraint in the puzzle that requires the zebras positions to not overlap. 2) If the lion is at 0, and a zebra is required to minimize its distance to a zebra at 10+pi, the zebra is forced to move exactly to 100, because this is the nearest position to 10+pi that satisfies the non-crossing constraint.

Answer 2

If you are talking about the real number line, then I believe the Zebras can win. All they need to do is make sure they stay at irrational numbered points on the line. Assuming the Lion picks rational numbers as his nominated positions (and if he picks irrational, then use a different class of irrational numbers for the zebras), then there are an infinite number of irrational numbers within any number range, providing an infinite number of possible moves to a zebra while avoiding the nominated position.

But then again, I don't understand how to satisfy this rule:

Zebra Move Constraint 2: Attractor The zebras are friendly. Within the positions allowed by the non-crossing constraint, the target will move to the position that minimises its distance to the last zebra it passed.

How do you minimize the difference between two real numbers? If the two zebras are not allowed to occupy the same spot, then there is no way to minimize the distance. Any attempt can be shown to not be minimal by halving the distance.

Perhaps I am misreading the question?

Answer 3

I might be missing something. Can't the lion simply push all the zebra far to one side, and then pull them one at a time. In each case (except the last) you push the zebra past the second one, and then pull it to it's position (the left most unfilled position). The last one will have already been crossed by the second last, so it can also be pulled into position.