
3. The fields of an $n \times n$ board, where $n \geqslant 3$, are coloured black and white as on the usual chessboard, with the field in the upper left-hand corner being black. We change the white fields into black ones, in the following manner: in each step we choose an arbitrary rectangle of size $2 \times 3$ or $3 \times 2$, which still contains three white fields, and we blacken these three fields. For which $n$ can we, after some number of steps, make the whole board black?


Solution. In each step we blacken exactly three fields, thus the total number of white fields has to be divisible by three. For even $n$, this number is equal to $\frac{1}{2} n^{2}$ (since there are as many black fields as white). For odd $n$, the number of white

![](https://cdn.mathpix.com/cropped/2024_04_17_dea7690a2ad723913678g-17.jpg?height=494&width=714&top_left_y=187&top_left_x=677)

Fig. 2

fields equals $\frac{1}{2}\left(n^{2}-1\right)$ (since there is one more black field than there are white fields). The numbers $\frac{1}{2} n^{2}$ or $\frac{1}{2}\left(n^{2}-1\right)$ are divisible by three if and only if $n=6 k$ or $n=6 k \pm 1$, respectively, for a suitable integer $k$.

We now show that for any $n$ of the above forms it is indeed possible to blacken all fields in the board. For $n=6 k$ this is immediate, since the whole board can be partitioned into disjoint rectangles of size $2 \times 3$ and we can apply the blackening procedure in each of them. Note that the same procedure can be applied, in fact, in any rectangle whose one dimension is divisible by 2 and the other by 3 .

For numbers of the form $n=6 k \pm 1$ we describe the blackening algorithm by induction. For the smallest possible values $n=5$ and $n=7$, Fig. 3 shows the $2 \times 3$
![](https://cdn.mathpix.com/cropped/2024_04_17_dea7690a2ad723913678g-17.jpg?height=562&width=1122&top_left_y=1352&top_left_x=458)

Fig. 3

and $3 \times 2$ rectangles in the respective boards in which we perform the blackening (for clarity, from the original chessboard colouring, only the field in the middle - not covered by the rectangles - is blackened in the picture ). In the induction step it is enough to show that if it is possible to make completely black any board of size $n \times n$ for an odd $n$, then the same is true for the board of size $(n+6) \times(n+6)$. From Fig. 4 it is clear how to proceed: we first blacken the "central" board $n \times n$ (which has black corner fields), and then we blacken each of the four marked rectangles of sizes $(n+3) \times 3$ or $3 \times(n+3)$. (This is possible in view of the observation at the end of the previous paragraph, since for $n$ odd the number $n+3$ is divisible by two.)

![](https://cdn.mathpix.com/cropped/2024_04_17_dea7690a2ad723913678g-18.jpg?height=586&width=714&top_left_y=184&top_left_x=677)

Fig. 4

Conclusion: The board can be made completely black if and only if $n$ is of the form $6 k, 6 k+1$ or $6 k-1$ for some integer $k$.
