MathNet 2008-part-04 — 165 problems (EN–VI) Question 156

How many ways can you color the squares of a $2 \times 2008$ grid in 3 colors such that no two squares of the same color share an edge?