4
$\begingroup$

There is an 8x8 array of sleeping humans with ten feet between adjacent humans, with sides in the four cardinal directions. A hero and a villain start ten feet west of the northwest human. The hero goes first. On each turn, a player moves ten feet in one of the cardinal directions. If the hero stops right next to a live human on his turn, the hero wakes him up and the human runs away. If the villain stops right next to a sleeping human on his turn, he kills the human. If either player breaks the rules, they die. How many people can the hero guarantee to save without dying?

(The earth is flat in this puzzle.)

Rules:

  • No skipping turns
  • You MUST move exactly ten feet on each turn
  • Each of your moves must be in a cardinal direction
  • No shouting to wake everyone up
Improve this question
$\endgroup$
7
  • $\begingroup$ Do you know the optimal solution? $\endgroup$
    – xnor
    Sep 21 at 1:54
  • $\begingroup$ Not really, although I have some bounds. $\endgroup$
    – mathlander
    Sep 21 at 1:56
  • $\begingroup$ Ok, so far I have that it's between 15 and 36. $\endgroup$
    – xnor
    Sep 21 at 1:58
  • $\begingroup$ I have that it's between 15 and 57. $\endgroup$
    – mathlander
    Sep 21 at 2:00
  • 2
    $\begingroup$ Are we supposed to assume the sleepers take up no room? $\endgroup$
    – msh210
    Sep 21 at 3:10

1 Answer 1

Reset to default
5
$\begingroup$

Two weak bounds which can surely be improved.

The hero can save at most

36 people

Here's the villain's strategy to kill the rest:

After the first move, mirror the hero across the main diagonal, that is, swapping North ⇿ West and South ⇿ East. So, if the hero moves to $(x,y)$, you move to $(y,x)$, taking $(1,1)$ to represent the northwest square you first move to. That way, you always kill one of $(x,y)$ or $(y,x)$ whenever $x \neq y$, since whichever one the hero moves to first, you get the other. The hero saves the 8 people on the main diagonal $x=y$, and the other 56 get split.

On the other hand, the hero can save at least

15 people

by

running south and east in any combination to the opposite corner, saving 15 people, since the villain will always be at least one step behind.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This was the same solution for 15 that I got. $\endgroup$
    – mathlander
    Sep 21 at 2:14
  • $\begingroup$ The hero can get 28 using a similar pairing strategy. $\endgroup$
    – mathlander
    Sep 21 at 2:52
  • $\begingroup$ @mathlander I was thinking about that but not getting it to work out. We can match a 7-by-8 hero region to a 7-by-8 villain region, but it seems to me like that won't guarantee getting one of each pair unless the matching is self-inverse. $\endgroup$
    – xnor
    Sep 21 at 5:15
  • 1
    $\begingroup$ I think the general answer for this question is n*(n+1)/2. $\endgroup$
    – Oray
    Sep 21 at 7:16
  • $\begingroup$ For the mapping, you can use a piecewise function to fix it. $\endgroup$
    – mathlander
    Sep 21 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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