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$

Answer: C

Concepts:graph theory inclusion-exclusion

Difficulty rating: 1820

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

2011 AMC 12A Problem 16

Answer: C

Difficulty rating: 1820

Solution:

Problem 16 in Other Years