THE 68th NMO SELECTION TESTS FOR THE JUNIOR BALKAN MATHEMATICAL OLYMPIAD

We label the rows from 1 to $m$ and the columns from 1 to $n$. If $m$ and $n$ are not congruent to 2 modulo 3, i.e. $m=3a+r_1$ and $n=3b+r_2$ with $r_1,r_2\in \{0,1\}$, we can tile the rectangle formed by the first $3a$ lines and $3b$ columns with $a\cdot b$ disjoint $3\times 3$ squares. Each of these squares needs to contain at least 2 red squares, therefore one needs to paint red at least $2ab=2\cdot \lfloor \frac{m}{3}\rfloor \cdot \lfloor \frac{n}{3}\rfloor$ squares. On the other hand, this number is sufficient: paint red those unit squares whose row number is a multiple of 3 (i.e. 3, 6, ..., $3a$) and whose column number belongs to the set $\{2,3,5,6,...,3b-1,3b\}$. It is easy to check that each $3\times 3$ square contains exactly two red squares.

The same answer (with the exact same arguments) remains valid if $m\equiv 2(\mathrm{mod}3)$ and $n\equiv 0,1(\mathrm{mod}3)$ (the answer remains the same in the case $n\equiv 2(\mathrm{mod}3)$ and $m\equiv 0,1(\mathrm{mod}3)$).

Let us now tackle the case $m=3a+2$, $n=3b+2$. We prove that in this case the answer is $2ab+\min \{a,b\}$.

Let us call a zone a $5\times 5$ square from which we have removed a $2\times 2$ square situated in one of its corners. We start by noticing that in any zone we need to have at least three red squares. Indeed, examining the two $3\times 3$ squares that contain the two remaining opposite corners of the $5\times 5$ square, they contain each at least two red squares and they only share one unit square (the one in the center), hence they contain together at least 3 red squares. With this remark, we move on to the promised induction:

For $a=1$: we can paint red the squares situated in column number 3, on the lines 1, 3 and 4. Any $3\times 3$ square contains exactly two of these red squares.

Assuming the assertion true for a $(3a-1)\times (3a-1)$ board, let us prove it for the $(3a+2)\times (3a+2)$ board. From the inductive hypothesis, in the $(3a-1)\times (3a-1)$ square situated in top-left corner we must have at least $2(a-1{)}^2+a-1$ red squares. We cover the remaining part of the $(3a+2)\times (3a+2)$ square with $3\times 3$ squares, plus one zone placed in the bottom-right corner. In this remaining part we have at least $2(a-1)+2(a-1)+3$ red squares, hence we have in total at least $2(a-1{)}^2+a-1+4(a-1)+3=2a^2+a$ red squares.

For $m<n$ (the case when $m>n$ is similar), it is sufficient to notice that the rectangle $(3a+2)\times (3b+2)$ can be obtained from the $(3a+2)\times (3a+2)$ square by gluing a $(3a+2)\times (3b-3a)$ rectangle next to it. In the square there are at least $2a^2+a$ red squares, while in the rectangle one can fit $a\cdot (b-a)$ disjoint $3\times 3$ squares, therefore it contains at least $2a(b-a)$ red squares. In total, the rectangle has at least $2a^2+a+2a(b-a)=2ab+a$ red squares. We have already seen that this number can actually be achieved, therefore the statement is proven.