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. Insert figure of a smaller circle, a bigger circle, and 6 sections dividing the region between the concentric circles.
Solution
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