IMO 1998 SL 28

Origin: IRN

Problem

A solitaire game is played on an m \times n rectangular 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 can 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

Let A be the number of markers with white side up, and B the number of pairs of markers whose squares share a side. We claim that A + B does not change its parity as the game progresses. Suppose that in some move we remove a marker that has exactly k neigh- bors, among them r with white side up (0 \leqr \leqk \leq4). Of course, this marker has its black side up. When it is removed, the r white markers get black side up, while the k −r black ones become white. Thus A changes by k −2r. As for B, it decreases by k. It follows that A decreases by 2r and preserves its parity, as claimed. Initially, A = mn −1 and B = m(n −1) + n(m −1); hence A + B equals 3mn −m −n −1. If we succeed in removing all the markers, we end up with A + B = 0. Hence 3mn −m −n −1 = (m −1)(n −1) + 2(mn −1) must be even, or equivalently at least one of m and n is odd. On the other hand, the game can be finished successfully if m or n is odd. Assume that m is odd. As shown in the picture, we can arrive at the position (1) in m moves; with m+1 moves we reduce it to the position (1 1 2), and with the next m−1 moves to the position (2). We continue until we empty all the columns. • ◦◦◦ ◦◦◦ ◦◦◦ ◦◦◦ ◦◦◦ ◦◦◦ ◦◦ −\to ••• •••• ◦◦◦ ◦◦◦◦ −\to • • • • • • • ◦ ◦ ◦ −\to ••• •••• (0) (1) (1 1 2) (2) m ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩