1
$\begingroup$

Background

See the puzzle Variant of lion and 100 zebras from @ghosts-in-the-code which remains unsolved years after it was posted. Several times in the last couple of years I've started to write up an answer, only to get caught up in some finicky details that are needed to prove whether the lions can actually catch a zebra, or merely keep it trapped forever, and stupidly failed to keep copies of the partly-written solutions. Given the age of that other puzzle, it doesn't seem fair to post a partial answer at this stage... instead, I'm breaking down my intended solution into a series of other sufficiently-interesting puzzles, so that if I ever try to attempt a full answer again, I'll at least have the other elements available to link to or copy from (and if someone else gets the full answer to that puzzle first, so be it!)

Basic rules

This is a turn-based game/simulation. On each turn, a single lion may move in any direction on the infinite plane by up to 100m. After this a single zebra may move in any direction by up to 100m. Where there are multiple lions or multiple zebras, each "team" can choose which of their members to move each time their "team" has a turn. Turns repeat indefinitely. Lions win if any lion may, on its move, reach the position of any zebra. Zebras win if they can evade capture forever.

Puzzle 1: Is a zebra trapped in a fixed enclosure?

For this puzzle, we have just one lion, but the zebra is in an enclosure. The goal of the lion for this puzzle is not to catch the zebra (a task already demonstrated to be impossible for a single lion), but to keep it trapped in the enclosure forever. The lion will, nevertheless take any opportunity given to it to catch the zebra, should the zebra be foolish enough to end its turn within 100m of the lion, so the zebra must avoid this at all costs.

The enclosure has a single opening from which the zebra can escape unless the lion can effectively block it. This opening may be of any size from a few metres (allowing the lion to keep the zebra trapped forever if it can merely reach the middle of the opening before the zebra can get there) to many kilometres.

The shape of the enclosure is not intended as important, but comments highlighted some edge cases where it may be make a difference. You may thus assume whatever convex shape is convenient for your calculations, or as a bonus answer you may prefer highlight any regions where it really does make a difference. To avoid creating unintended restrictions, when passing the end of the enclosure boundary, either animal may make change direction as needed during its movement of up to 100m.

For the purposes of this puzzle, a single zebra starts at a random position within the enclosure, and the lion starts somewhere outside the enclosure.

Example of a possible starting position

Sub-problem A: when can the zebra escape?

For what starting positions of lion and zebra relative to the opening of the enclosure can the zebra guarantee to escape? How?

Sub-problem B: how can the lion keep the zebra trapped?

For any starting positions not meeting the condition for sub-problem A, what strategy can the lion use to ensure the zebra never escapes.

Sub-problem C: can the lion force the zebra into the enclosure?

Suppose instead the zebra starts very slightly outside the enclosure, but the lion can pick its starting point anywhere more than 100m from the zebra before the lion's first move (which can thus end anywhere except at the zebra's starting point). Can the lion force the zebra into the enclosure? If so, how? If not, how does the zebra secure its escape? Is there a maximum or minimum size of opening that the lion can force the zebra into?

Starting position with zebra just outside the enclosure

$\endgroup$
8
  • $\begingroup$ How many sub-problems, at least, should be solved for an acceptable answer? $\endgroup$
    – bobble
    May 21 at 16:35
  • $\begingroup$ @bobble A and B complement each other, and should both form part of an acceptable answer - if the answer to A is that the zebra can always escape with a clear strategy for how, then B is kind-of redundant, whereas if the answer to A is that the zebra can never escape, there'd be a lot more to do for B. C was added more as an afterthought - by extending A to consider zebra locations just outside the enclosure, it may help solvers think carefully about any boundary condition(s) found - perhaps it's a hint in disguise? $\endgroup$
    – Steve
    May 21 at 16:46
  • $\begingroup$ Can they change direction within their moves? $\endgroup$
    – loopy walt
    May 21 at 17:23
  • 1
    $\begingroup$ I hate to be that guy but I'm pretty sure the shape of the enclosure also can make a difference. Example: opening 60m wide, zebra 40m inside midpoint, lion 60m outside. If zebra can turn at end of opening and the nearest outside corner of the enclosure and this corner is less than 50m away zebra escapes, otherwise it is trapped. $\endgroup$
    – loopy walt
    May 21 at 19:41
  • 1
    $\begingroup$ I'm glad it's not just me that can't get this damn puzzle out of my head. $\endgroup$
    – Veedrac
    May 21 at 23:07
6
$\begingroup$

Let's focus on the

bisector of the two animals' positions just before the next move.

A few observations:

The zebra can never cross it without immediately being caught.

Conversely:

As long as the zebra moves a straight 100m without touching the bisector the lion cannot catch it in the next move.

This already resolves C as

once the zebra is outside the confinement there will always be an obstruction free direction away from the bisector.

To avoid tedious edge cases I'll assume that the enclosure is a rectangle with one side completely open.

B

The lion wins precisely when the opening falls entirely on the lions side of the bisector. Indeed, by mirroring the zebra's moves the lion can fix the bisector exactly where it is and there is no way for the zebra to make any progress.

A

If the bisector is outside the confinement or crosses the opening at least one of the two corners flanking the opening will be on the zebra's side. The zebra can move straight there being careful to use up whatever is left of the last 100m step moving as far away from the lion as possible.

$\endgroup$
1
  • $\begingroup$ Thanks, that was indeed the intended answer, and described far more succinctly than I'd expected! (This one was intended to be relatively easy so the ground rules are established for later puzzles). $\endgroup$
    – Steve
    May 22 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.