Did you solve it? Getting coins out of the bank

Earlier today I set you the following problem. It was a tricky one, and judging from the BTL comments the solution is eagerly awaited. Let me restate the problem before we get there. It concerns a game on a grid with an infinite number of rows and columns, and starts with three coins in the top left corner of the grid, as illustrated here.

The game has one move. At any moment you can remove any coin, and replace it with two coins, one in the cell immediately below the removed coin, and one in the cell immediately to the right of the removed coin. For example, just say we remove the coin two along on the top row, the grid will now look like this:

There’s one more thing. You are only allowed to remove a coin, in the way described above, if the cell below that coin and the cell to the right of that coin are empty. In other words, if a coin has an empty cell below it and an empty cell to its right, then you can remove that coin and replace it with two coins, one immediately below and one immediately to the right of the cell of the removed coin. That’s it. There are no more rules. Let’s redraw the initial grid with a red line separating the four cells in the upper left corner. These four cells are called the ‘bank’.

The challenge: design a strategy that gets all the coins out the bank. If you can’t, prove that it is impossible.

Solution

If you tried playing around with coins on your desk, or on this interactive version, you will have begun to suspect that moving all the coins from the bank is not possible. The coins quickly get gridlocked.

In fact, these suspicions are correct: it is impossible to get all the coins out of the grid. How do we prove it? In other words, how to we show that whatever strategy we use to get the coins out the bank we are doomed to failure.

Here’s one way. (There may be others – and if you find one please describe it below the line). The proof I’m going to describe here is beautiful and ingenious. It relies on the concept of an ‘invariant’, a property that stays the same when certain other things change.

Bear with me while we mark up the grid, as below. You will find out why we are doing this very shortly. Put the number 1 in the top left cell, as illustrated below. Let’s call the number in any cell the weight of the cell. Let the cells below and to the right of the top left cell have a weight of 1/2. Fill in the rest of the grid by halving the weight each cell you go down, and halving the weight each cell you go across.

Now we are ready for the great reveal! Our invariant is simply the weight of the cells with coins.

I’ll explain. Imagine a grid with a single coin in it, positioned in the top left cell. This cell has a weight of 1. When we remove it and replace it with a coin immediately below and immediately to the right, the grid now contains two coins, each on a (1/2)-cell. In other words, the weight of the cells with coins is 1/2 + 1/2 = 1. So, by removing the coin and replacing it with two coins, as per the rules, the total weight of the occupied cells remains the same.

In fact, whichever position a coin is in, replacing it with a coin below and a coin to the right makes no difference to the weight, because the labelling of the grid was deliberately done to make that the case. Take any cell, the weight of the cell below it, and of the cell to its right, is exactly half the weight of the original cell. So the sum of the weights of these two cells is equal to the weight of the original cell.

We’re almost there. Just a few things more to sort out. Let’s calculate the weight of the entire grid. The first row is the infinite sum:

1 + 1/2 + 1/4 + 1/8 + … = 2

The second row is

1/2 + 1/4 + 1/8 + 1/16 + … = 1

The third row is

1/4 + 1/8 + 1/16 + 1/32 + … = 1/2

Carrying on like this we see that when we count up the rows, the weight of the whole grid is:

2 + 1 + 1/2 + 1/4 + 1/8 + … = 4

Even though the grid has an infinite number of cells, the total weight is finite.

(I am assuming here that you know that the sum of 1/2 plus 1/4 plus 1/8… adds up to 1. An intuitive way to see this is to consider a whole cake. Eat half, and then half of what’s left, and then half of what’s left…you will be eating 1/2, then 1/4, then 1/8, and so on, and in the limit you will have eaten the whole cake.)

Now let’s consider the weight of the bank: it is 1 + 1/2 + 1/2 + 1/4 = 9/4.

This means that the weight of the grid outside the bank is 4 – 9/4 = 7/4.

Back to the question. We start with coins on three cells. These cells have a combined weight of 1 + 1/2 + 1/2 = 2.

If there was a strategy to get all the coins out of the bank, this would mean it would be possible for there to be a placement of coins on cells outside the bank whose combined weight is 2. But this is is impossible, because the highest possible weight outside the bank is 7/4, which is less than 2, and you only get this high when every single cell outside the bank is occupied.

In other words, there is no strategy to get all the coins out the bank. It does not exist!

I hope you enjoyed today’s puzzle. I’ll be back in two weeks.

Thanks to Carlos Sarraute for the problem.

I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.