Question

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 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.

Answer

Answer: 732

Concepts:graph theory recursive counting

Difficulty rating: 2400

Solution:

Let $P_n$ be the number of valid paintings of a ring of $n$ sections. Cutting a ring open between two adjacent sections shows that ring paintings correspond exactly to rows of $n$ sections with adjacent colors different and the two end colors different. A row of $n$ sections with adjacent colors different can be painted in $4 \cdot 3^{n-1}$ ways, and the rows whose end colors match correspond, by merging the two end sections into one, to ring paintings of $n - 1$ sections. Hence $P_n + P_{n-1} = 4 \cdot 3^{n-1}.$

Three mutually adjacent sections give $P_3 = 4 \cdot 3 \cdot 2 = 24,$ so $P_4 = 108 - 24 = 84,$ then $P_5 = 324 - 84 = 240,$ and finally $P_6 = 972 - 240 = 732.$

2016 AIME II Problem 12

Answer: 732

Difficulty rating: 2400

Solution:

Problem 12 in Other Years