21
$\begingroup$

You're surrounded by infinitely many zombies. You're at the origin, and zombies occupy the points $(100i,100j)$ for all integer $i, j$ except the origin, as shown below:

enter image description here

You and the zombies move alternatively. You all move in steps. Each step is of distance 1, and can only be taken in one of the four cardinal directions. In your move, you can move at most 100 steps. In a zombies move, the simple-minded zombies move according to the following simple rules:

  • if $0\lt \vert Z_x - Y_x\vert \leq \vert Z_y- Y_y \vert$, the zombie moves 1 step horizontally towards you;
  • if $0\lt \vert Z_y - Y_y\vert \lt \vert Z_x- Y_x \vert$, they move 1 step vertically towards you;
  • if $Z_x=Y_x$ or $Z_y=Y_y$, they simply move 1 step closer to you.

where $Z_x$ and $Z_y$ are the zombie's x and y coordinates, and $Y_x$ and $Y_y$ your coordinates.

Question: Can you survive indefinitely? If so, how? If not, how many turns can you survive and how far (in steps) can you move away from the origin before being caught?


Edit: fixed the bug mentioned by @iBug.

$\endgroup$
7
  • 1
    $\begingroup$ At first I thought this could involve some irrational number stuff, but then realized all steps are integers. Hmm, need more ideas. $\endgroup$ – justhalf Apr 28 at 4:26
  • 8
    $\begingroup$ The question doesn't say that a zombie would kill you. On the other hand there is no reason to believe you can survive indefinitely even without the zombies. So I would say eventually you will die like all of us. $\endgroup$ – Florian F Apr 28 at 9:29
  • $\begingroup$ bug found by iBug :D $\endgroup$ – Dmitry Kamenetsky Apr 28 at 11:51
  • 5
    $\begingroup$ Because an isotropic infinite field of zombies exerts zero net gravity everywhere. $\endgroup$ – obscurans Apr 29 at 5:22
  • 2
    $\begingroup$ @fall: At the start everything is 100 squares apart, so there's room for movement $\endgroup$ – Mooing Duck Apr 29 at 16:23
15
$\begingroup$

Answer:

Yes, we can survive forever.

Strategy:

Use your first move to go to 50,50. Afterwards alternate between +(99,0) and +(0,99).

Visualisation:

enter image description here Numbers are smaller (10 steps instead of 100). Time is indicated for zombies (grey dots) from lighter to darker. Origin is bottom left.

Proof:

Once a zombie has smaller by two x or y coordinate than you they can never catch up with you along that coordinate, so we can ignore those.

Those diagonally ahead of you will move in lockstep and alternate -(1,0) and -(0,1) so your distance to them will not change mod 100 until you pass them. EDIT: Actually this depends on which of the alternating steps we take first:
less interesting ...

The others in front of you will move away from the diagonal and are therefore harmless, too.

$\endgroup$
9
  • 7
    $\begingroup$ According to OP I can take up to 100 steps per move. $\endgroup$ – loopy walt Apr 28 at 11:44
  • $\begingroup$ After you made your first move to (50,50), aren't all diagonal zombies in front of you going to move one step left? There will be no zombie on the diagonal henceforth? $\endgroup$ – Eric Apr 28 at 12:13
  • $\begingroup$ If you move up first they will move down the next move and after your next move to the right they will be back on the diagonal. If you move right first you are completely right. That is the difference between the two plots. $\endgroup$ – loopy walt Apr 28 at 12:20
  • 1
    $\begingroup$ No, because of the modulo 100 argument. Each time they are back on the diagonal their offset from you will be (50,50) mod 100. $\endgroup$ – loopy walt Apr 28 at 12:33
  • 2
    $\begingroup$ @iBug I don't think it makes a difference for this strategy. $\endgroup$ – loopy walt Apr 28 at 12:35
10
$\begingroup$

The answer is Yes.

The current version of the game has a bug to exploit: If a zombie is horizontally aligned with you (Zy = Yy), according to the rule, it'll "move vertically towards you", but since it has the same "vertical level" with you, it cannot move "towards" you and it'll be stuck at its place.

This means every zombie that falls onto the same horizonal line as you will remain forever, so we can just move between (0, 0) and (1, 0) alternatively, and zombies will move between (1, 1) and (0, 1) or between (1, -1) and (0, -1) following your pattern. Since all zombies have the same parity of their Manhattan distance to the origin, there will not be two zombies simultaneously at (0, 1) and (1, 1), so you will not die and the zombies will "dance with you".

Now it's time for you to challenge yourself with existential crisis :)

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for catching the bug! That was definitely not meant to be though : ( Let me fix the bug. $\endgroup$ – Eric Apr 28 at 7:38
3
$\begingroup$

A stronger solution.

The answer is yes even if you can run only 2 steps per round.

On the first round move 2 steps up (0,+2).
On the subsequent rounds move 2 steps right (+2,0).

This works even if there is a zombie on each cell of the grid except for y = 1,2,3 and your starting cell.

As you run right, as long as the zombies in front of you are further right than up or down from you, they move left. They stay away from y = 1,2,3. They move up or down only when you are about to overtake them. But since they need 2 move to reach y = 2, by that time you already overtook them. They miss you. They won't even reach y = 2 because after one vertical move you already move right of them and they start walking horizontally again.

Here is an illustration of the process.

enter image description here

$\endgroup$

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.