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 $1$ . Now, let $f(a,b)$ be the number of ways to satisfy the conditions where there are $a$ sections ending on color $b$ . We make a table on $f(a,b)$ . $\begin{tabular}{c|c|c|c|c }&1 & 2 & 3& 4 \\ \hline 1& 1 & 0 & 0 & 0\\ 2 & 0 & 1 & 1 & 1 \\ 3& 3 & 2 & 2 & 2 \\ 4 & 6 & 7 & 7 & 7 \\ 5 & 21 & 20 & 20 & 20\\ 6& 0& 61 & 61 & 61\\ \end{tabular}$ Note that $f(6, 1)=0$ because then $2$ adjacent sections are both color $1$ . We also have to multiply by $4$ by symmetry for other colors in the left ring, so the desired answer is $(61+61+61) \cdot 4 = \boxed{732}$ .

Solution by Shaddoll

Page

Toolbox

Search

2016 AIME II Problems/Problem 12

Solution