Elementary Techniques used in the IMO (International Mathematical Olympiad) - Invariants

This post follows from Part 5.

Part 6

In this post, we shall explore another method of colouring, more often known as assigning weights. Commonly in such questions, we tend to involve $+1, -1$ a lot since the common technique of taking product and sum gives us lots of additional information. I would advise the reader to take special care as to the motivation behind finding a suitable invariance sum or product as it would help in the exercise in the next post.

(IMO shortlist 2005) There are $n$ markers, each with one side white and the other side black, aligned in a row with their white sides up. At each step, if possible, we choose a marker with the white side up (but not one of the outermost markers), remove it, and reverse the two neighbouring markers. Prove that one can reach a configuration with only two markers left if and only if $3 \nmid n-1$.

Solution: Just playing around with small examples can lead to one trivial observation: the parity of the number of black markers remains unchanged during the game. Hence if only two markers are left, they must have the same colour.

We can see that we can assign "weights". Well, here the best thing to encode would be the number of black markers. Remember that $(-1)^n$ for some $n$ provides lots of information by encoding the parity(when we consider sums), let us define assign to a white marker with $n$ black markers to its left the value $(-1)^n$. We only assign values to the white markers. Denote $\mathbb{S}$ as the sum of all numbers assigned to the white markers.

Consider an arbitrary white marker with both of its neighbours initially white and with $k$ black markers to its left. We perform an operation on that marker and see how it affects $(-1)^n$. Clearly, if we turn both of its neighbouring markers black and remove it, then $\mathbb{S}$ decreases by $-(-1)^k + (-1)^{k-1} + (-1)^{k-1} = 3 (-1)^{k-1}$. Therefore, we have just shown that $\mathbb{S} \pmod 3$ is invariant.

If the game ends with two black markers then $\mathbb{S} \equiv 0 \pmod 3$ and if it ends with two white markers then $\mathbb{S} \equiv 2 \pmod 3$. $\rightarrow 3 \nmid n-1$.

To show that if we start with $n ≥ 5$ markers and $n \equiv 0,2 \pmod 3$ satisfies the conditions. By removing the $3$ leftmost white markers (that do not violate the conditions), we obtain a row of $n-3$ markers. By working backwards, we can reach $2$ or $3$ white markers. We are done with the former and for the latter we can reach $2$ black markers. □

The next post will be tomorrow! :)