HMMT-Feb 2011 guts, Problem 18

In how many ways can each square of a $4 \times 2011$ grid be colored red, blue, or yellow such that no two squares that are diagonally adjacent are the same color?

Solution: If we first color the board in a checkerboard pattern, it is clear that the white squares are independent of the black squares in diagonal coloring, so we calculate the number of ways to color the white squares of a $4 \times n$ board and then square it. Let $a_{n}$ be the number of ways to color the white squares of a $4 \times n$ board in this manner such that the two squares in the last column are the same color, and $b_{n}$ the number of ways to color it such that they are different. We want to find their sum $x_{n}$. We have $a_{1}=3, b_{1}=6$. Given any filled $4 \times n-1$ grid with the two white squares in the last column different, there is only 1 choice for the middle square in the $n$th row, and two choices for the outside square, 1 choice makes them the same color, 1 makes them different. If the two white squares are the same, there are 2 choices for the middle square and the outer square, so 4 choices. Of these, in 2 choices, the two new squares are the same color, and in the other 2, the two squares are different. It follows that $a_{n}=2 a_{n-1}+b_{n-1}$ and $b_{n}=2 a_{n-1}+b_{n-1}$, so $a_{n}=b_{n}$ for $n \geq 2$. We have $x_{n}=8 \cdot 3^{n-1}$ and $x_{2011}=8 \cdot 3^{2010}$. So the answer is $64 \cdot 3^{4020}$. $\fbox{64 \cdot 3^{4020}}$.

Answer: 64 \cdot 3^{4020}