2011 AMC 12A Problem 16

Question

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?

2520

2880

3120

3250

3750

The five diagonals

AC, CE, EB, BD, DA

form a single

5

-cycle among the vertices

The number of proper colorings of a cycle of length

n

with

k

colors is

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

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

is

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

Problem 16 in other years