5
$\begingroup$

There is a table with infinite cells. An ant starts from cell $(1,1)$ and each time it can move one cell up or right. Before starting to move, an infinite sequence of cell numbers like $<(x_{1},y_{1}) , (x_{2},y_{2}), ... , (x_{n}, y_{n}) , .... >$ is given to it. After step $k$, cell number $(x_{k},y_{k})$ will be poisoned and if ant goes there or already is there, it'll die. Prove with induction that the ant can live forever if it knows sequence elements from the beginning :)

$\endgroup$
  • $\begingroup$ What is the sum of $x$ and $y$ coordinates of ant at step $k$? How many cells are there that ant can reach at step $k$? How many of them can be poisoned before or at step $k$? $\endgroup$ – didgogns Feb 24 '17 at 15:15
  • $\begingroup$ @didgogns There is an infinite number of cells. After each step one cell is poisoned, therefore K-1 cells can be poisoned before step k. $\endgroup$ – T.Meyer Feb 24 '17 at 15:17
0
$\begingroup$

Hint: Consider for each level of the graph the number of possible cells at that level the ant can reach alive, minus the number of cells on later levels that are already poisoned at that time.

Show that this number cannot decrease.

Conclude that there are reachable cells on every level.

$\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.