67th NMO Selection Tests for JBMO

We label the lines from top to bottom and the columns from left to right. The leftmost side of the unit square in the upper-left corner can be colored in $3$ ways. Subsequently, there are $3$ ways of choosing the side of this unit square that is to receive the same color as the first side. The remaining two sides of the square have to be colored with the same color. This color can be chosen in $2$ ways. In conclusion, the unit square in the upper-left corner can be colored in $3\cdot 3\cdot 2=18$ ways.

Next, we successively color the unit squares in the first line, from left to right. Every time, the leftmost side of the square has already been colored. Thus, there are $6$ ways of coloring each of these squares. We proceed similarly on the first column. We color the unit squares from top to bottom and for each of these squares there are $6$ ways of coloring.

Now we move on to color the squares situated on rows $2,3,\dots ,m$ and columns $2,3,\dots ,n$. We color them from top to bottom, from left to right. Thus, when in turn to be colored, each unit square has already two sides colored: the upper side and the leftmost side. If these sides have received different colors, then the colors of this square have already been decided; there are $2$ ways of coloring the remaining sides with these two colors. If the two sides that are already colored have the same color, then the remaining sides will receive the same color. This color can be chosen in $2$ ways. Therefore, for each of these squares, there are $2$ ways of coloring.

In conclusion, there are $18\cdot 6^{m-1}\cdot 6^{n-1}\cdot 2^{(m-1)(n-1)}=3^{m+n}\cdot 2^{mn}$ ways of coloring.