BxMO/EGMO Team Selection Test

Answer: this can be done exactly if $n$ is divisible by $2$ or $3$, except for $3$ itself.

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

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

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

Now suppose $n$ is not divisible by $2$ or $3$. Then we colour the columns cyclically with the colours $0$, $1$, $2$ mod $3$. Each pentomino always has $3$ squares of the same colour, and $1$ 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 $n$ is not divisible by $3$, there is a colour that has $n$ more squares than any other colour. So the difference between the number of squares of these two colours is $n$, which is odd since $n$ is also not divisible by $2$. We conclude that these two colours can never both have only black squares. $\square$