I think there are $3 \cdot 2^{m+n-1}$ good colorings. The proof is as follows, Let the number of rows be $n$ and columns be $m$ Label the boxes $(i,j)$ with the left bottom most box $(1,1)$ traditionally. Then we fill the block $(1,1);(2,1);(2,2);(1,2)$ initially. This can be done in $4!$ ways. Now the blocks $(3,1);(3,2)$ can be filled in $2$ ways, then $(4,1);(4,2)$ can be filled in $2$ ways and so on till $(m,1);(m,2)$ Thus the $2$ bottom most rows can be filled in $4! \times 2^{m-2}$ ways. Now consider the cell $(1,3)$ this can be filled in $2$ ways. Observe that the color of this cell determines the coloring of the whole row. Similarly (inductively or recursively if you want) the color of the first cell of each row can be done in $2$ ways each and the coloring of each such cell uniquely determines the coloring of the whole row. Thus the first cells of all the rows (except the bottom two rows) can be colored in $2$ ways each and thus there are $2^{n-2}$ such colorings. Multiplying this result with the initial result we get the total colorings as $4! \times 2^{m-2} \times 2^{n-2}$ which is $3 \times 2^{m+n-1}$ I hope my reasoning is correct and I have made no mistakes.

utkarshgupta wrote: I think there are $3 \cdot 2^{m+n-1}$ good colorings. Sorry to disappoint you but I think you are wrong. I was working on this problem and initially got this result but I figured out it is wrong. I am in lack of time but I will explain shortly. If you have $m=n=3$ you will get other result. If you watch upper rectangle without last row you will see it needs $2 \cdot 4!$ to fill this rectangle but watching cases how to fill total square you will get $72$ which is not by formula.

OK I understand the loophole in my proof. Thanx !

I'm not sure about the answer, but I'm sure that the idea is good.

2008 CGMO-P7 http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1236872&sid=728d1ceaeec980f50e9720001a2f3ab4#p1236872

Nice doing then, N. Beluhov!

Oh, come on, I do not want to defend anyone, of course, it's better all these problems to be original ones. But it was a competition at a national level, what would you say to IMO 2014, p5 which was a problem of Chinese TSTs 2006 with a cosmetic difference. (I mean both statements are almost the same).

Let colors be $1,2,3,4$. $WLOG$ suppose that numbers in $(1,1)$ and $(2,1)$ are $1$ and $3$ (not neccesarily respectively). It follows that numbers in $(1,2)$ and $(2,2)$ are $2$ and $4$. Note that if it happens that in second row we have three different consecutive numbers then all the other numbers will be predetermined. It is very easy to prove once one notices it. Now we have $2^n$ possible arrangements of the first to rows and $2^n-4$ of them predetermine the rest of the table ( only $(1,3)(2,4);(3,1)(2,4);(1,3)(4,2);(3,1)(4,2)$ don't). For these $4$ that don't predetermine the table we see that the first number in every row determines that row. Also, we can only choose number that doesn't appear in the previous row, or in other word we choose between $2$ numbers. Because in every of those $4$ cases we are left with $m-2$ rows for every of those $4$ first two rows configurations there are $2^{m-2}$ good colorings so the number of good colorings is $2^n-4+4 \cdot 2^{m-2}$ for pair $(1,3)$ in cells $(1,1)$ and $(2,1)$. Because there are $6$ pairs we can put in those cells the answer is: $6(2^n+2^m-4)$.

gobathegreat wrote: utkarshgupta wrote: I think there are $3 \cdot 2^{m+n-1}$ good colorings. Sorry to disappoint you but I think you are wrong. I was working on this problem and initially got this result but I figured out it is wrong. I am in lack of time but I will explain shortly. If you have $m=n=3$ you will get other result. If you watch upper rectangle without last row you will see it needs $2 \cdot 4!$ to fill this rectangle but watching cases how to fill total square you will get $72$ which is not by formula. Could anyone explain this please. Why @utkarshgupta's solution was wrong??

Solved with Alex Zhao, Elliott Liu, Eric Shen, Holden Mui, Luke Robitaille, and Ryan Yang The answer is $6\cdot 2^{n} + 6\cdot 2^{m} - 24$. Consider the coloring of the first row. Observe that if there exists $3$ consecutive squares of all different colors, wlog let them be red, green, blue, then the square above the green square is colored white, the square above the blue square is colored red, and the square above the red square is colored blue. Therefore, the square following the blue square must either be white or red. We can continue the coloring by going along each square following the blue square, which each has two choices. This gives a unique coloring that is also valid, since each time we add a color to a square, we will not violate any previous squares. Secondly, consider the case where no $3$ consecutive squares are all different colors. Then, WLOG, let the squares alternate as green, red, green, red, etc. The row above this is white, blue, white, etc., and so on. Each row can be colored in two different ways (either green red green red or red green red green). Now, we calculate the total number of colorings. For the second case, wlog let the first two squares be green, red. Then, doing casework on the first time we have the square not green nor red, then since we have $2$ choices for each of the rest of the squares in the row, we have a total of \[4\cdot 3\cdot 2^{m-2} + 4\cdot 3\cdot 2^{m-1} + \ldots + 4\cdot 3\cdot 2\]number of colorings. For the second case, there are $6$ ways to choose the colors for the first row, and then $2^{n}$ ways to alternate the rows. Adding this up gives a total of \[4\cdot 3\cdot(2^{m-1} - 2) + 6\cdot 2^{n} = 6\cdot 2^{n} + 6\cdot 2^{m} - 24\]number of colorings.