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.

Are the target positions single points? (And if not, what's stopping the zebras from moving $\epsilon$ away from a target position whenever it would otherwise move onto that position?) — Lopsy, Mar 14 '15 at 14:40
@Lopsy Yes, the target positions are single points. The primary tool provided for the lion here is the non-coincide restriction. One consequence is that it requires the tagged zebra to remain 100m away from the lion. Together with the 100m limit of motion per turn, this allows the lion to fine-tune the position of zebras. — Lawrence, Mar 14 '15 at 21:13
I'm being stupid today. Suppose the tagged zebra is at Z and the lion is at L on the number line. Then, as I understand the rules, the set of legal moves for the tagged zebra is the interval [Z-100,Z+100], minus the set [L-100,L+100]. This set is either empty (which I think can never happen) or infinite. So how can the lion ever set up a situation where a zebra is forced to make one particular move? — Lopsy, Mar 14 '15 at 22:59
@Lopsy Thanks. I had a solution in mind when posting the puzzle, but something must have gotten lost in the process. I've added a new constraint that should help the lion with its task. — Lawrence, Mar 15 '15 at 10:44
i didnt understand tbh , what s the purpose , to be not at respective prespecified target or to be always a safe distance from lion's claws ? and can a lion be harmless when zebra passes thru or hav i not contained this part well enugh: "spots can pass through each other with no consequence." — Abr001am, Mar 16 '15 at 14:52
@Agawa001 This is a lion-centric puzzle. The lion's goal in this version is to position the zebras at predetermined locations, given the 2 restrictions on zebra movements. There is no capture goal in this puzzle. This puzzle only has a superficial resemblance to the original L&Z puzzle. I retained the reference to L&Z because it is an abstracted form of a portion of one attempt to solve Lopsy's L&Z variant. — Lawrence, Mar 16 '15 at 15:14
in this case zebras can win eventually , there s noway a lion can force a zebra to be at a level of a spesific spot when a zebra is free to go wherever it wants both directions. when a zebra feels close to a coming target , it changes drection immediatly , or is there other constraint iwasnt aware of ? — Abr001am, Mar 16 '15 at 16:25
@Agawa001 The zebra is not completely free to choose - it can only move if tagged, but must stop if a different zebra is tagged. It must avoid the lion across its own and the lion's next move, but within that range of motions must select the one that moves it near the zebra it last saw. These give the lion quite a lot of control. But is it enough? — Lawrence, Mar 16 '15 at 23:34
I have made a second change to the rules and added an example of how the lion can position one zebra. Both rule changes are highlighted at the bottom of the puzzle description. — Lawrence, Mar 17 '15 at 02:04
At this rate, we'll need a lion-and-zebra tag. This is the 4th question I'm seeing. — ghosts_in_the_code, Apr 16 '15 at 12:33
@ghosts_in_the_code It's an interesting field :P . But more seriously, perhaps an "infinite plane" tag would be useful. — Lawrence, Apr 16 '15 at 12:42
@Hackiisan In answer to your questions: 1) Yes, all positions are public knowledge. 2) Tagging happens at any time. I should really have used a different word - it means the zebra selected as the target, not the zebra that is caught. One zebra is selected at the start, and the lion can change the target (and hence the movable zebra) at any time. 3) Zebras always have at least one legal move - it can always move away from the lion (up to 100m at a time). The intention of the zebra-attractor constraint is to allow the lion a mechanism to 'pull' zebras, not just push them. — Lawrence, Sep 26 '15 at 09:47

jsocolar · Accepted Answer · 2015-11-16T18:43:06.760

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.

Welcome to Puzzling.SE! It's generally better to edit your post instead of making a new one. This is not a discussion board; it's designed to get answers to questions. If you can improve your answer, then do it! If you try to make new posts instead, I bet it's flagged as spam because you're a new user posting huge amounts of text in multiple posts. — Engineer Toast, Nov 16 '15 at 15:31
Thanks Engineer Toast . As it happens, this is my only post--my very first one. Not sure why it flagged as spam instead of letting the post through. I tried changing around the format, removing the words "give away" (as in "this might give away the answer") etc. Anyway, if anybody else encounters this problem, a viable workaround seems to be to post something very short, then edit that post with whatever text was originally denied. — jsocolar, Nov 16 '15 at 15:34

score 1 · Answer 2 · answered Nov 16 '15 at 18:04

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?

The attractor constraint allows the lion to 'pull' a zebra by moving away from the zebra. The non-crossing constraint requires the zebra to stay at least 100m away from the lion. Together, they allow the lion to precisely position that zebra. Consider a scenario with the lion and two zebras (A and B) arranged in the order L < A < B < 0. The lion comes near A, targets A, then drives A past B, and then past any target position (say 100). So far, A can still choose irrational numbers to go to. Then the lion retreats to 0 using as many turns as necessary. Then A must follow but stop at 100. — Lawrence, Nov 16 '15 at 22:46

score 0 · Answer 3 · answered Nov 17 '15 at 00:05

0

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.

answered Nov 17 '15 at 00:05

Dr Xorile

23,406
3
47
125

That's a valid approach, though the order of pulling them is important (cf jsocolar's accepted answer). – Lawrence Nov 17 '15 at 11:03

Precision Tag - can the lion win?

3 Answers3