The unit squares of an 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 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 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 .
Note that for it is possible to achieve that black unit squares become white, and vice versa, by choosing each of the four squares exactly twice.
Moreover, for a 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 squares once.
If is divisible by , we can divide the board into disjoint boards. As previously shown, we can conclude that for such all black unit squares can be coloured white, and vice versa. Let , for and .
We claim that, if does not divide , 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 when divided by . 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 when divided by .
Moreover, note that any square needs not be chosen more than twice, since the colours of the unit squares which we obtain after steps are the same as the colours obtained after steps, for and .
Observe only the first two rows of the board and assume that the first unit square in the first row is black. The square in the first two columns must be chosen twice. After that, the second unit square in the first row is grey, so the 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 square in the third and fourth row. Analogously, we conclude that the 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 square in the top part of the board, i.e. the squares must be chosen, in order,
times, where this sequence is periodical with the period .
Regardless of whether or , it is unambiguously determined how many times we need to choose the 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 square in order to change the colour of the last unit square from black to white or vice versa. This completes the proof.