75th Romanian Mathematical Olympiad

Indeed, if $n$ is even, then we can divide the board into squares $2\times 2$. Now we pick a different color for each such square and use it for the cells of that square. This coloring clearly satisfies the requirement.

To prove that $n$ must be even, start from any cell $S$ of the board and move from each cell $C$ to its neighbour having the same color as $C$ and which has not been previously visited. Since the board is finite, this procedure must stop at some point, meaning that the next step takes us to an already visited cell $V$. Since each cell has exactly two neighbours with the same color as $C$, the cell $V$ must be $S$. So, for each cell $S$ of the board we have a path $P_S$, constructed as above. Notice that if two such paths have a common cell, then they must coincide, because these paths have the same pairs of 'consecutive cells' (they may have different starting points and the order in which the consecutive cells are covered can be reversed). Therefore, the number of the board's cells is the sum of the numbers of the cells of the different paths $P_S$.

Color now the board chess-wise. Each pair of consecutive cells of a path is made of a black and a white cell, therefore each path must have an even number of cells. This shows that the number $n^2$ of the board's cells is the sum of some even numbers, so $n$ is even.