# Prove that the ant can survive

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 :)

• 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$? – didgogns Feb 24 '17 at 15:15
• @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. – T.Meyer Feb 24 '17 at 15:17