Selection tests for the Balkan Mathematical Olympiad 2013

Let us associate a $1$ to each cell with a black color and a $0$ to each cell with a white color. The condition is equivalent to the sum of numbers in each $2\times 3$ rectangle and in each $3\times 2$ rectangle being even. Let $a_{i,j}$ be this number at the cell in the $i^{\text{th}}$ row and $j^{\text{th}}$ column, for $1\le i,j\le 50$.

Consider, for a fixed pair $i,j$, with $1\le i\le 48$ and $1\le j\le 47$, the $3\times 4$ rectangle:

$a_{i,j}$	$a_{i,j+1}$	$a_{i,j+2}$	$a_{i,j+3}$
$a_{i+1,j}$	$a_{i+1,j+1}$	$a_{i+1,j+2}$	$a_{i+1,j+3}$
$a_{i+2,j}$	$a_{i+2,j+1}$	$a_{i+2,j+2}$	$a_{i+2,j+3}$

By applying the condition to the two $2\times 3$ rectangles which contain cells from the second and the third rows, we get $$a_{i+1,j}+a_{i+1,j+1}+a_{i+1,j+2}+a_{i+2,j}+a_{i+2,j+1}+a_{i+2,j+2}\equiv 0(\mathrm{mod}2),$$ and $$a_{i+1,j+1}+a_{i+1,j+2}+a_{i+1,j+3}+a_{i+2,j+1}+a_{i+2,j+2}+a_{i+2,j+3}\equiv 0(\mathrm{mod}2)$$ By applying the condition to all the $3\times 2$ rectangles, we get $$\begin{array}{c}{a}_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}+a_{i+2,j}+a_{i+2,j+1}\equiv 0(\mathrm{mod}2),\\ a_{i,j+1}+a_{i,j+2}+a_{i+1,j+1}+a_{i+1,j+2}+a_{i+2,j+1}+a_{i+2,j+2}\equiv 0(\mathrm{mod}2),\end{array}$$ and $$a_{i,j+2}+a_{i,j+3}+a_{i+1,j+2}+a_{i+1,j+3}+a_{i+2,j+2}+a_{i+2,j+3}\equiv 0(\mathrm{mod}2).$$ By adding these 5 relations and cancelling all even numbers we get $$a_{i,j}+a_{i,j+3}\equiv 0(\mathrm{mod}2).$$ This proves that $$a_{i,j+3}=a_{i,j}$$ We prove in a similar way that $$a_{i+3,j}=a_{i,j}$$ Therefore, it is enough to know the numbers in the $3\times 3$ rectangle

$a_{1,1}$	$a_{1,2}$	$a_{1,3}$
$a_{2,1}$	$a_{2,2}$	$a_{2,3}$
$a_{3,1}$	$a_{3,2}$	$a_{3,3}$

to deduce, by periodicity, the numbers in all the other cells.

Applying the condition to the first $2\times 3$ rectangle, we will get $$a_{2,3}\equiv a_{1,1}+a_{1,2}+a_{1,3}+a_{2,1}+a_{2,2}(\mathrm{mod}2)$$ Applying the condition to the second $2\times 3$ rectangle and to the second $3\times 2$ rectangle and adding the two relations, we will get $$a_{3,1}\equiv a_{2,1}+a_{1,2}+a_{1,3}(\mathrm{mod}2)$$ We obtain in a similar way $$a_{3,2}\equiv a_{2,2}+a_{1,3}+a_{1,1}(\mathrm{mod}2)$$ $$a_{3,3}\equiv a_{2,3}+a_{1,1}+a_{1,2}(\mathrm{mod}2)$$ Therefore, it is enough to know the 5 numbers $$a_{1,1},a_{1,2},a_{1,3},a_{2,1},a_{2,2}$$ to deduce all the numbers in the cells of the $50\times 50$ chessboard.

Conversely, choose a value in $\{0,1\}$ for each number $a_{1,1},a_{1,2},a_{1,3},a_{2,1},a_{2,2}$, and deduce the values in all the other cells of the chessboard. It is easy to check that the condition on the two $2\times 3$ rectangles and the two $3\times 2$ rectangles in the $3\times 3$ rectangle above is satisfied. We deduce, by periodicity, that it is satisfied in all the chessboard. Hence there are $2^5$ ways to color the chessboard.