2011 AMC 12A Problem 16

Problem 16 of 25IntermediateCounting & Probability

Each vertex of convex pentagon

ABCDE

is to be assigned a color. There are

6

colors to choose from, and the ends of each diagonal must have different colors. How many different colorings are possible?

Show solution

Solution

The diagonals connect the vertices in the order

A - C - E - B - D - A,

which is a

5

-cycle. The condition is exactly that this cycle is properly colored. The number of proper

k

-colorings of a cycle of length

n

(k-1)^n + (-1)^n (k-1).

With

n = 5

and

k = 6,

\begin{gathered} 5^5 + (-1)^5 \cdot 5 \\ = 3125 - 5 = 3120. \end{gathered}

Thus, the correct answer is C.