Bulgarian National Mathematical Olympiad

Number the columns of the table by $1,2,\dots ,m$ and its rows by $1,2,\dots ,n$ and denote the cell in the $i$-th column and $j$-th row by $(i,j)$.

Consider an interesting coloring $S$. We show first that either any row in $S$ contains only two colors or any column in $S$ contains only two colors.

Suppose $S$ does not contain a rectangle $1\times 3$ (with longer horizontal side) containing three distinct colors. It follows that in any row of $S$ we have two alternating colors, as needed.

Let the cells $(u,v)$, $(u+1,v)$ and $(u+2,v)$ be covered in three distinct colors $a,b$ and $c$. We obtain that $(u+1,v+1)$ is colored in the fourth color $d$, $(u,v+1)$ in $c$, $(u+2,v+1)$ in $a$, $(u+1,v+2)$ in $b$, $(u,v+2)$ in $a$, $(u+2,v+1)$ in $c$, and so on. By analogy we obtain that $(u+1,v-1)$ is in color $d$, $(u,v-1)$ in $c$, $(u+2,v-1)$ in $a$ and so on. We conclude that column $u$ contains only colors $a$ and $c$, column $u+1$ contains only colors $b$ and $d$, and column $u+2$ contains only colors $a$ and $c$. It follows now that any column having the same parity as $u$ contains only colors $a$ and $c$, and any column having the parity of $u+1$ contains only colors $b$ and $d$.

Hence, either any row in $S$ contains only two colors or any column in $S$ contains only two colors.

The number of interesting colorings such that in any column of odd number two of the colors alternate and in any column of even parity the other two colors alternate is equal to $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\times 2^m$. The corresponding colorings when the rows are colored in two colors equal $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\times 2^n$. The colorings in which the color of the cell $(i,j)$ depends only on the parity of $i$ and $j$ are counted in both cases. Therefore, the number of interesting colorings equals $6\times (2^m+2^n)-24$.