An ant is at (0, 0) in the infinite integer grid. The ant and the exterminator take turns, with the ant going first.
- Each turn, the ant advances one square north or one square east.
- Each turn, the exterminator chooses one grid cell to spray with pesticide. The ant dies if it is currently in the square being sprayed, or if it ever steps onto a previously sprayed square.
The twist is that the ant is omniscient; the ant knows the infinite sequence of choices that the exterminator will make. That is, there is an infinite list
(x*_1_*, y*_1_*), (x*_2_*, y*_2_*), ...
of grid cells, such that the farmer will spray (x*_k_*, y*_k_*) on his kth turn, and the ant can decide where to move based on the entire list.
Puzzle
Show that the ant can survive for arbitrarily long. That is, for all natural numbers n, the ant has a strategy to survive for n turns.
Open problem
Show that the ant has a strategy to survive for infinitely long.
This may seem like a trivial consequence of the puzzle solution, but I think it isn't. There is a strategy to survive n steps for each n, but that doesn't mean these infinitely many strategies are consistent with each other. To solve the second problem, you need to show how the ant uses its foreknowledge to decide its first step, in a way that avoids traps all the way to infinity.