Log In

How to hunt a zombie

Posted on: May 25th, 2013 by

A zombie moves along a 1 dimensional line. It starts at position x, and at each time step, it moves y steps to the right. x and y are integers unknown to you. (If y is negative, it means the zombie moves -y steps to the left.) After each time step, you are allowed to examine any integer position and ask if the zombie is in that position. If correct, you get to shoot the zombie on the head and the zombie will be eliminated. Devise an algorithm that is guaranteed to kill the zombie.

via Microsoft research

One Response to How to hunt a zombie

  1. Dinesh had this to say about that:

    At time n, the zombie is in location x+ny. If we can find a bijection from the integers Z to Z^2, we are done. But Z^2 is the same as Q and we can use Cantor's enumeration of rational numbers as this bijection.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}