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

This post follows from Part 6. Note that this shall be the last tutorial segment for the series of posts. There will be a test in a few days for the interested reader. Questions for the test will be taken from recent IMO so I encourage my readers to go through the previous posts if they would feel like taking the test.

Please also bare with me. This is quite a long instalment.

Part 7

(IMO shortlist 1998) A solitaire game is played on an $m \times n$ regular board, using $mn$ markers that are white on one side and black on the other. Initially, each square of the board contains a marker with its white side up, except for one corner square, which contains a marker with its black side up. In each move, one may take away one marker with its black side up but must then turn over all markers that are in squares having an edge in common with the square of the removed marker. Determine all pairs $(m,n)$ of positive integers such that all markers can be removed from the board.

Solution: This is a particularly annoying problem. It is extremely long and difficult to understand. As such, let us employ the technique of trying small cases to perhaps find a pattern.

1. $m,n = 1$. This is boring. Just remove the "corner square" marker.

2. WLOG $m=2, n =1$. This is boring too. Remove any "corner square" marker. The other will be black. Remove both.

3. $m = 2, n=2$. Just do the operations and you will find that you end up with a sole white marker that cannot be removed.

4. $m = 2, n =3$. Just remove the first row one by one and leave the following scenario, it is clear that all markers can be removed.

5. $m = 2, n = 4$. Playing around shows that this case is impossible.

Diagram 1

These observations motivate us to conjecture that if either $m,n$ is odd then we can remove all markers (using the $4$th case as a hint). WLOG, let us write $m = 2k+1$. For easy reference, we assign the markers a position $(i,j)$ as the $i$th row and $j$th column. So now, again, WLOG, $(1,1)$ is that with the black side up. We remove $(1,1)$ and in sequential from top to bottom, remove all $(k,1)$ for $2≤ k ≤ m$. We have something as in the following diagram:

tagtext

So in our mathematical language, each marker $(k,2)$ now has its black side up (sounds like backside up). Anyways, the next thing is to sequentially (which means in the order of $q = 1, \ldots , \frac{m-1}{2}$ ) remove the markers $(2q+1,2)$. The cute thing here is that each with $(2q,2)$ is actually flipped twice, which means it turn from $\text{black} \rightarrow \text{white} \rightarrow \text{black}$, which is nice. So we have the following diagram:

tagtext

Now by removing the markers $(2q,2)$ sequentially, we end up with the following diagram. It is clear now that by using this procedure we can remove all markers given that $m$ is odd (so that the final row would be black).

tagtext

To show that if $(m,n)$ are both even then we cannot remove all the markers, we need to find an invariance. Here are $2$ approaches, as we will see, the first approach stems from the fact that empty squares without markers are useless, so the idea of removing empty squares. The second one is more well-known, as assigning weights of $-1,1$ allows one to consider sums and products (as in this case).

Consider the perimeter of the board. We consider removing a black marker as removing the edges that the cell it is in shares with the perimeter of the board. This is a bit ambiguous and requires the formal definition of perimeter. With that in mind, we will refer to removing a black marker as removing the cell it is in. Consider removing a cell that shares $k$ edges with the perimeter of the board, then $k$ is lost and $4 -k$ is gained for the perimeter. The presence of $4$ suggests taking $\pmod 4$ which is a considerably good strategy. So, we have a net gain of $4 - 2k$ for the perimeter, which is $2k \pmod 4$.

We want to eliminate the variable $k$, so let's give it a physical meaning first. Well, except for the first black marker and its cell, $k$ is actually $\text{\# of adjacent markers removed} + \text{\# of edges shared with the perimeter of the board}$. Notice that the former is always odd, since if we consider the cycle $\text{white} \rightarrow \text{black} \rightarrow \ldots \rightarrow \text{Black}$, we would always need an odd number of manipulations/arrows, as desired. This implies that the total sum is odd, and we see that no matter whether $k \equiv 1,3 \pmod 4$, $2k \equiv 2 \pmod 4$.

However, this means the perimeter changes $(n-2)(m-2)+3$ times from $2(m+n)$ which is the original perimeter. By assumption $2(m+n) \equiv 0 \pmod 4$, which means that the final perimeter is $2 \pmod 4$. It is clear that a contradiction arises since we need it to be $0 \pmod 4$. □

For the reader: Solve this example by assigning the weights as suggested as a second approach.