Maths Olympiad Prep

Library / /3 of 4

Combinatorics Difficulty 8.6 Shortlist Prove it Netherlands

We have an n×nn \times n-board with n3n \ge 3 of which each square can be coloured white or black separately. Each move we change the colour of five chosen squares in the possibly rotated version of the following pentomino pattern.
Figure 1
At the beginning, all the squares are white. Determine for which nn it is possible to make all squares black after a finite number of moves.

Solution

Answer: this can be done exactly if nn is divisible by 22 or 33, except for 33 itself.

We first show that for n=3n = 3, recolouration is not possible. We consider the boxes AA, BB and MM in the following figure.
Figure 2
Then each pentomino box contains MM and each pentomino contains AA or BB. Since AA and BB have to be chosen an odd number of times to make them black, in such a case MM is chosen an even ++ even == even number of times. So MM is then white and we conclude that we can never make all the squares black at the same time.

Now suppose n4n \ge 4. If nn is divisible by 22 then we repeatedly use the following procedure:
Figure 3
To do this, we divide the board into (12n)2\left(\frac{1}{2}n\right)^2 blocks of 2×22 \times 2. Since n4n \ge 4 we can find a 4×44 \times 4 block around each 2×22 \times 2 block so we can apply the procedure.

If nn is divisible by 33 and unequal to 33 itself, then nn is at least 66. Using our work above, we have the following procedure for a 3×33 \times 3-block with sufficient space:
Figure 4
To apply this repeatedly, we divide the board into (13n)2\left(\frac{1}{3}n\right)^2 blocks of 3×33 \times 3. Since n6n \ge 6 we can find around each 3×33 \times 3 block the required 4×54 \times 5 block so we can apply the procedure.

Now suppose nn is not divisible by 22 or 33. Then we colour the columns cyclically with the colours 00, 11, 22 mod 33. Each pentomino always has 33 squares of the same colour, and 11 square of both other colours. This means that each move switches an odd number of squares of each colour between white/black. So the parity of the number of black squares is always the same for all three colours. In contrast, since nn is not divisible by 33, there is a colour that has nn more squares than any other colour. So the difference between the number of squares of these two colours is nn, which is odd since nn is also not divisible by 22. We conclude that these two colours can never both have only black squares. \Box

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 and solution reproduced as published; topic and difficulty added by this site.