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×n m \times n regular board, using mn 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) (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 m,n = 1 . This is boring. Just remove the "corner square" marker.

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

  3. m=2,n=2m = 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=3m = 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 m = 2, n = 4 . Playing around shows that this case is impossible.

Diagram 1 Diagram 1

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

tagtext tagtext

So in our mathematical language, each marker (k,2) (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,,m12 q = 1, \ldots , \frac{m-1}{2} ) remove the markers (2q+1,2) (2q+1,2) . The cute thing here is that each with (2q,2) (2q,2) is actually flipped twice, which means it turn from blackwhiteblack \text{black} \rightarrow \text{white} \rightarrow \text{black} , which is nice. So we have the following diagram:

tagtext tagtext

Now by removing the markers (2q,2) (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 m is odd (so that the final row would be black).

tagtext tagtext

To show that if (m,n) (m,n) are both even then we cannot remove all the markers, we need to find an invariance. Here are 2 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 -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 k edges with the perimeter of the board, then k k is lost and 4k 4 -k is gained for the perimeter. The presence of 4 4 suggests taking (mod4) \pmod 4 which is a considerably good strategy. So, we have a net gain of 42k 4 - 2k for the perimeter, which is 2k(mod4) 2k \pmod 4 .

We want to eliminate the variable k k , so let's give it a physical meaning first. Well, except for the first black marker and its cell, k k is actually # of adjacent markers removed+# of edges shared with the perimeter of the board \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 whiteblackBlack \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 k1,3(mod4) k \equiv 1,3 \pmod 4 , 2k2(mod4) 2k \equiv 2 \pmod 4 .

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

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

Note by Anqi Li
7 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...