Maths Olympiad Prep

Library / /24 of 24

Combinatorics Difficulty 7.9 National Olympiad, round 2 Prove it Croatia

The unit squares of an N×NN \times N board are coloured black and white so that squares that share a side have different colours, and so that at least one corner square is coloured black. In each step we choose a 2×22 \times 2 square and change the colour of all four unit squares inside that square, so that white unit squares become black, black become grey and grey become white.
Determine all positive integers N>1N > 1 for which it is possible, using a finite number of steps, to achieve that all unit squares that were originally black become white, and all unit squares that were originally white become black.
(Russia 2012)

Solution

We claim that the sought numbers are all multiples of 33.
Note that for N=3N = 3 it is possible to achieve that black unit squares become white, and vice versa, by choosing each of the four 2×22 \times 2 squares exactly twice.
Figure 1

Moreover, for a 3×33 \times 3 board whose corner and central squares are white, and the remaining four squares are black, we can change the colour of black squares to white and vice versa by choosing each of the four 2×22 \times 2 squares once.
Figure 2

If NN is divisible by 33, we can divide the board into disjoint 3×33 \times 3 boards. As previously shown, we can conclude that for such NN all black unit squares can be coloured white, and vice versa. Let N=3K+LN = 3K + L, for L{1,2}L \in \{1, 2\} and KNK \in \mathbb{N}.

We claim that, if 33 does not divide NN, it is not possible to change the colour of all black squares to white, and vice versa.
Note that a black unit square will become white if and only if the number of steps in which we change the colour of that square gives remainder 22 when divided by 33. Analogously, a white unit square will become black if and only if the number of steps in which we change the colour of that square gives remainder 11 when divided by 33.
Moreover, note that any 2×22 \times 2 square needs not be chosen more than twice, since the colours of the unit squares which we obtain after 3q+r3q + r steps are the same as the colours obtained after rr steps, for r{0,1,2}r \in \{0, 1, 2\} and qNq \in \mathbb{N}.

Observe only the first two rows of the N×NN \times N board and assume that the first unit square in the first row is black. The 2×22 \times 2 square in the first two columns must be chosen twice. After that, the second unit square in the first row is grey, so the 2×22 \times 2 square in the second and third column must be chosen twice. By doing this, we achieve that the second unit square is black, and the third one is white. It follows that we must not choose the 2×22 \times 2 square in the third and fourth row. Analogously, we conclude that the 2×22 \times 2 square in the fourth and fifth column must be chosen once, the one in the fifth and sixth row must be chosen once, and the one in the sixth and seventh column must not be chosen. In this way we can conclude exactly what must be done

with each 2×22 \times 2 square in the top 2×3K2 \times 3K part of the board, i.e. the 2×22 \times 2 squares must be chosen, in order,
2,2,0,1,1,0,2,2,0,2, 2, 0, 1, 1, 0, 2, 2, 0, \dots
times, where this sequence is periodical with the period 66.

Regardless of whether L=1L = 1 or L=2L = 2, it is unambiguously determined how many times we need to choose the 2×22 \times 2 square in the last two columns in order to achieve that the next to last unit square in the first row changes its colour from black to white or vice versa. However, that number is different from the number of times we would need to choose that same 2×22 \times 2 square in order to change the colour of the last unit square from black to white or vice versa. This completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.