Mathematica competitions in Croatia

We will prove the following claim by mathematical induction on the number of coins: We can remove all the coins from some starting arrangement if and only if there is an odd number of coins with black side up.

If there is only one coin on the board, we can remove it if and only if it is turned black side up.

For positive integer $N>1$, assume that the claim holds for all arrangements consisting of less than $N$ coins and consider an arbitrary starting arrangement of $N$ coins. Let $K$ be the number of coins with black side up in that arrangement.

Observe that, by removing some coin, board is divided in two parts and that the moves performed on one of these sides do not affect the coins on the other part.

If $K$ is odd, we will prove that it is possible to remove all coins. Let $Y$ be the first coin on the board that is turned with black side up. Assume that $Y$ is neither on the first, nor on the last square of the board, and denote by $X$ the coin on a square left to $Y$, and by $Z$ the coin on a square right of $Y$. In the first move, remove both $Y$ and its square (and turn $X$ and $Z$). This way, we obtain two smaller boards. We will show that we can remove all coins from both of them. On the first board there are coins being left of $Y$, and on the second one there are those who are right of $Y$.

On the first board all coins are turned with white side up, except $X$ which was just turned so that it is black side up. Hence, on the first board there is exactly one coin with black side up, so, by induction hypothesis, there is a sequence of moves removing all the coins from that board.

If $Z$ is white side up, then, after the move, the number of coins on the other board with black side up will be equal to $K$. If $Z$ is black side up, then, after the move, the number of coins on the other board with black side up will be equal to $K-2$. In both cases the number is odd. By induction hypothesis, we can remove all the coins from the second board as well.

If $Y$ is on the first square, then consider just the second board and coin $Z$, and if $Y$ is on the last square, consider just the first board and coin $X$.

Assume that $K$ is even and that, for a considered starting arrangement, there is a sequence of moves removing all the coins.

Let $Y$ be the coin that is removed first. Beside $Y$, there was an odd number of coins on the board with black side up. The total number of coins turned with black side up on both parts of the board will still, after the move, be an odd number. Hence there is an even number of coins turned with black side up on one part of the board. By induction hypothesis, coins on that part cannot be removed, contradiction. We have shown that if it is possible to remove all the coins, then the number of those with black side up cannot be an even number.