XXVII Olimpiada Matemática Rioplatense

We will first show that in a valid coloring of the board there cannot be a $3\times 3$ sub-board with all its cells painted in blue.

Consider an $n\times n$ sub-board $T$ with all cells painted in blue, for the maximum $n$, and assume $n\ge 3$. Since the board has unpainted cells, we may find an $(n+1)\times (n+1)$ sub-board $Q$ containing $T$. Without loss of generality, we may assume $T$ is in the upper-left corner of $Q$, as in the following picture:



We look at the $n$ cells to the left of $T$; we call them $c_1,c_2,\dots ,c_n$, from top to bottom. Note that, given two adjacent cells $c_i$ and $c_{i+1}$, there cannot be one painted and the other unpainted, since in this case, the $2\times 2$ sub-board of $Q$ containing them would have exactly three painted cells (two cells in $T$ and one in the last column). We deduce that the cells $c_1,\dots ,c_n$ are either all painted or all unpainted. If $n\ge 3$, the former is not possible, since at least one of the cells $c_1,c_2,c_3$ must be painted so that the $3\times 3$ sub-board in the right-upper corner of $Q$ has an odd number of blue cells. We conclude that all the cells $c_i$ must be painted. Similarly, the same holds for all the cells of $Q$ that are below $T$. Now, by looking at the $2\times 2$ sub-board in the bottom right corner of $Q$, we deduce that the corner cell is also painted since, otherwise, this sub-board would contain exactly 3 blue cells. Summarizing, we have proved that all the cells of $Q$ are painted in blue, contradicting the maximality of $T$. The contradiction arises from the assumption $n\ge 3$. It follows that the board cannot contain any $3\times 3$ board completely painted in blue.

Now consider any $3\times 3$ sub-board $T$. By assumption, it contains an odd number of blue cells, and we have proved that this number cannot be 9. Let us show that there cannot be 7 blue cells either. If this is not the case, the two unpainted cells $A$ and $B$ belong to the same $2\times 2$ sub-board of $T$ (otherwise, a $2\times 2$ sub-board of $T$ containing $A$ would have 3 blue cells). Assume, with no loss of generality, that $A$ and $B$ are in the $2\times 2$ sub-board in the upper-left corner of $T$. Then, the 5 cells of $T$ around this sub-board are painted:



But then, the cell marked with $\star$ has to be painted so that the $2\times 2$ board in the bottom-right corner has an even number of blue cells. From this fact, with a similar argument, it follows that the cells marked with $\Delta$ are also painted. This contradicts the fact that $T$ has 2 unpainted cells.

We conclude that every $3\times 3$ sub-board has at most 5 blue cells. As the $27\times 27$ board can be subdivided into 81 of those sub-boards, we have that Carla can paint at most $5\times 81=405$ cells in blue. In the next example, in which the pattern is repeated every 3 rows and every 3 columns, every $3\times 3$ board has exactly 5 blue cells.



Therefore, the maximum number of cells that Carla can paint is 405.