How Many Ways to Color a 2x2016 Grid Using 3 Colors with Adjacency Restrictions?

[anemone]

Here is this week's POTW:

-----

You're required to color the squares of a $2\times 2016$ grid in 3 colors, namely yellow, purple and green. How many ways can you color the squares such that no two squares of the same color share an edge?

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to kaliprasad for his correct solution.:)

You can find the proposed solution below:

Spoiler

The left-most column can be colored in $^3P_2=6$ ways. For each subsequent column, if the nth column is colored with Yellow-Purple, then the (n+1)th column can only be colored with one of Purple-Yellow, Purple-Green, Green-Yellow. That is, if we colored the first nth columns, then there are 3 ways to color the (n+1)th column. It follows that the number of ways of coloring the board is $6\times 3^{2015}$.