Advanced Combinatorics Problem

Question

We divide the upper right quadrant into squares like a chessboard. We play a game. We start with a penny in the corner square.

We have one rule: If a penny has empty squares above and right, you may remove the penny and then fill those two empty squares with a penny each.

I'm asked to determine the smallest number of moves required to completely remove all pennies from the shaded blue region (as seen below).

When I tried to do this on my own, I kept on getting that the blue area couldn't be completely rid of pennies. I was able to move the penny from the initial corner but ran into big problems when I had two pennies at the farthest blue box in the first row and the farthest blue box in the second row. This is where all the pennies on the grid start multiplying very fast to the point where you can't remove the penny from the first row.

Answer 1

Initial idea: at least $14$ moves are necessary.

Assign an uneven weight to each square of the board, according to the number of steps from the corner: the bottom-left square has weight $1$, then the two adjacent squares have weight $1/2$, the three squares in the next diagonal layer have weight $1/4$, and generally the squares at distance $k$ have weight $2^{-k}$. Now we make the following key observation:

After any valid move, the sum of all the weights of squares containing pennies is unchanged.

Since the initial sum is exactly $1$, it must remain $1$ no matter how many moves are made. As each move creates exactly one penny, we get a lower bound by asking: what is the fewest number of squares outside the blue region which can sum to $1$?

Each such square has weight at most $1/8$, and there are only $4$ of them. The next-heaviest squares are the $5$ of weight $1/16$, then $6$ of weight $1/32$. So even the $15$ heaviest available squares add up to only $$\frac{4}{8} + \frac{5}{16} + \frac{6}{32} = 1.$$

We will definitely need to end up with at least 15 pennies (possibly more if we can't pack them exactly into those slots via legal moves), which will take at least 14 moves.

Refinement: it cannot be done in any number of moves.

To prove this is impossible, we make another very easy, but critical, observation:

There is always exactly one penny in the first row (and exactly one penny in the first column).

I leave it to you to show that at any point in time the sum of all the squares containing pennies is strictly less than $$\frac{1}{4} + \sum_{n=0}^\infty (n+2)2^{-n-3} = 1.$$

But this means that we can never position enough pennies outside the blue region to achieve a total weight of $1$! No matter how many moves we make, there must remain some pennies inside the blue region.