Three coins are placed at the origin of a Cartesian coordinate system. On one move one removes a coin placed at some position $(x, y)$ and places three new coins at $(x+1, y)$, $(x, y+1)$ and $(x+1, y+1)$. Prove that after finitely many moves, there will exist two coins placed at the same point.
Let $r = \sqrt{2} - 1$. Consider the sum $S$ of $r^{x_i+y_i}$ over all coins $(x_i, y_i)$ at any point. Note that $r$ has been chosen so that $S$ stays invariant because $1 = 2r + r^2$. In the beginning, $S=3$, and if we assume that at some point after the start there is no point with more than one coin, then we get:
This problem is very well-known in the form $(x,y) \to (x, y+1), (x+1, y)$.