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.

• What have you tried? Surely you can at least find an upper bound for the smallest number of moves? This is a useful first step to proving optimality. Commented Nov 15, 2016 at 3:00
• This shaded region is small enough where you can just work out all the combinations by hand. Post what you come up with and maybe someone will help if you are wrong. Commented Nov 15, 2016 at 3:16
• @cBEiN I think "work out all the combinations by hand" is a slight exaggeration. If I didn't mess up my calculations, it should take at least 14 moves minimum, which seems like a lot of combinations. Commented Nov 15, 2016 at 4:36
• @Erick I guess I may be doing it wrong because I didn't get any. That was my initial confusion with this problem. I got that there was no way to clear the blue area. Commented Nov 15, 2016 at 4:40
• @ErickWong 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. Commented Nov 15, 2016 at 4:56

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.

• Thank you very much! Your help was very much appreciated Commented Nov 15, 2016 at 7:51