2016 AIME II Problems/Problem 12
The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and you will paint each of the six sections a solid color. Find the number of ways you can choose to paint the sections if no two adjacent sections can be painted with the same color.
Assume, WLOG, the left ring is color . Now, let be the number of ways to satisfy the conditions where there are sections ending on color . We make a table on .
Note that because then adjacent sections are both color . We also have to multiply by by symmetry for other colors in the left ring, so the desired answer is .
Solution by Shaddoll