Maths Olympiad Prep

Library / /4 of 5

Combinatorics Difficulty 6.8 National Olympiad Prove it Greece

For each positive integer nn, we consider a 3n×3n3n \times 3n chessboard, and its squares are colored black and white as follows: Starting from the left up corner square every third diagonal is black and all other squares are white, as in the figure.
Figure 1
At each move we select a 2×22 \times 2 square and we change the color of its squares as follows: The white squares become orange, the oranges (if there exist) become black and the blacks become white. Our target is, after a finite number of moves, to obtain a chessboard with all black squares at the initial placement changed to whites and all white squares at the initial placement changed to black. Prove that:

a) The target is not feasible for n=3n = 3.
b) The target is feasible for n=2n = 2.

Solution

a) Firstly, observe that if we change the colour of one square 3 times, it goes back to its original colour. As the final configuration does not depend on the order of moves and placing a move on a square 3 times does not change the configuration, we can suppose that a move is placed on any square exactly 0, 1 or 2 times. This further implies that a white square must change its colour 2 (modulo 3) times and that a black square must be changed 1 (modulo 3) times.
Let us associate each 2×22 \times 2 square with its top left unit square. Let's take a look at the first column. Its top square is white and is included in only one 2×22 \times 2 square, so that square has to be placed 2 times. The second square in this column is also white and is included in its 2×22 \times 2 square as well as in the one associated with the first unit square in the column. This square has already been turned black by taking the 2×22 \times 2 square of the first unit square in this column twice, so its own 2×22 \times 2 square has to be taken 0 times.
We use similar arguments to show that next four 2×22 \times 2 squares have to be called 1,1,1 and 0 times. After that we have the white square included only in its own 2×22 \times 2 square and in the one above it, which has been taken 0 times, so we have the same situation we had in the beginning. Therefore, the next one should be used 2 times and the next is white, so 0 times. However, this is the only 2×22 \times 2 that contains the last black square, therefore, this cannot change color, a contradiction.

b) Working as in a), we can fill the board with the numbers 0, 1, 2 in each square, showing how many times we should use the corresponding 2×22 \times 2 square.
Figure 2

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.