clearing coins from a grid

There is two-dimensional grid with integer coordinates. We can do some moves by coins. If the coin is in point $(x,y)$ and point $(x+1,y)$ and $(x,y+1)$ are free from coins, we can remove coin from $(x,y)$ and put two coins at $(x,y+1)$ and $(x+1,y)$. In the beginning we have only one coin at the origin. The question is "Can we make free from coins square with coordinates of the lower left corner $(0,0)$ and upper right corner $(2,2)$?"

-

2 Answers

Assign point $(x,y)$ the weight $2^{-(x+y)}$. Then the weight of $(x,y)$ equals the weight of $(x+1,y)$ plus the weight of $(x,y+1)$, so the total weight of the occupied points never changes. At the beginning, with a single coin at the origin, the total weight is just $1$. The points outside that square have total weight $15/16$, which is less than $1$, so it's impossible.

-

This is a cute little problem.

The insight here is to look for an invariant that is preserved by the allowed moves. In this case, the right way to approach it is to think of the original coin at the origin as having a fixed mass of 1. The rule for replacing the coin with two others can be thought of as breaking the coin in half, to be replaced by two coins of half the mass. Since we are starting with one coin of mass one at the origin, our rules tell us that a coin on a given square will have a certain prescribed mass, regardless of the sequence of moves that got it there. In particular, a square that is $n$ steps away from the origin will support a mass of $2^{-n}$.

The way to proceed should now be clear - we determine the (finite) mass of the entire grid. Then, we can check and see if a region can be cleared by computing the mass of the complement - if this is less than our original mass of one, a region can't be cleared.

-