Maths Olympiad Prep

Library / /32 of 32

Combinatorics Difficulty 7.9 National Olympiad, round 2 Prove it Estonia

In a 2n×2n2n \times 2n grid exactly half of the squares have been coloured black and the other half are white. In one step one can take some 2×22 \times 2 square in this grid and reflect its four squares w.r.t. the horizontal or vertical central axis. Which positive integers nn make it possible to get from any initial configuration to a state where the whole board has been coloured chessboard-style?

Solution

In case of n=1n = 1 it is not possible to get the chessboard-pattern if 2×22 \times 2 the initial configuration is like in fig. 19, because adjacent same-coloured squares are same-coloured also after reflecting.

Figure 1

Let us now show that for any n2n \ge 2 we can start from any initial configuration and reach the chessboard pattern. For that we can show that whenever we have some wrong-coloured squares, we can reduce their number by taking some finite number of steps. Note that a wrong-coloured square turns into a right-coloured square on the other side of the axis of reflection and the other way round. Let us define a double reflection to be reflecting the same 2×22 \times 2 area first horizontally and then vertically. A double reflection is equivalent to a reflection with respect to the centre of the 2×22 \times 2 square, whereas the wrong-coloured squares will remain wrong-coloured and the right-coloured squares right-coloured after the reflection.

First suppose that there exist two adjacent same-coloured squares. W.l.o.g., let those two wrong-coloured squares be in the same row. As n2n \ge 2, we can also assume that this row is at least third from the top and that there is at least one column to the right of the squares under consideration. Let us mark the wrong-coloured square with W and the right-coloured square with R on the figure; xx means one or the other and xx' means the opposite of xx (if xx is right then xx' is wrong and the other way round).

* If out of the two adjacent wrong-coloured squares at least one has a wrong-coloured upper neighbour, then by reflecting w.r.t. the vertical axis the number of wrong-coloured squares decreases by at least 2 (fig. 20).

Figure 2

* If both upper neighbours of the two adjacent wrong-coloured squares are right-coloured, but at least one of them in turn has wrong-coloured upper neighbour, then by reflecting w.r.t. the vertical axis we can take the two adjacent wrong-coloured squares up by one row, so that the number of wrong-coloured squares does not change (see fig. 21). Afterwards we can do as described previously.

Figure 3

* If the 2×22 \times 2 square above the two wrong-coloured squares is entirely right-coloured, but at least one adjacent square to the right of this 2×22 \times 2 area is wrong-coloured, then we can use double reflection to swap this wrong-coloured square with one of the right-coloured squares in the 2×22 \times 2 area (on fig. 22 the wrong-coloured square is the bottom right square; in the other case the same transition helps). After that we can proceed as before.

Figure 4

* In the rest of the cases we can reduce the number of wrong-coloured squares by 2 using the steps on fig. 23.

Figure 5

Let us finally look at the situation where there are no two wrong-coloured adjacent squares. With double reflections a wrong-coloured square can be moved along the diagonals without changing the number of wrong- or right-coloured squares. Since the numbers of black and white squares are initially equal and do not change with reflecting, the existence of a wrong-coloured black square implies that there must also exist a wrong-coloured white square and the other way round. Therefore by taking steps along the diagonals we can take one wrong-coloured square next to another one and proceed as described above.

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.