2011 AMC 10A Problem 22

The diagonals are $AC, CE, EB, BD, DA$. Reading them in that order, each one starts where the previous one ended, so the five diagonals form a single closed loop
$$A \to C \to E \to B \to D \to A.$$
The condition "ends of every diagonal differ" is exactly "consecutive vertices around this loop differ." So we are counting proper colorings of a $5$-cycle with $6$ colors.

Ignore the closing link $D$-$A$ for a moment and color along the path $A, C, E, B, D$, each vertex different from the one before: $6 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 3750$ colorings. The bad ones are those with $D$ the same color as $A$. Merging $D$ into $A$ in such a coloring produces a proper coloring of the $4$-cycle $A \to C \to E \to B \to A$, and vice versa.

The same trick counts the $4$-cycle: path colorings $6 \cdot 5^3 = 750$, minus those with $B$ matching $A$, which correspond to proper colorings of the triangle $A, C, E$: $6 \cdot 5 \cdot 4 = 120$. So the $4$-cycle has $750 - 120 = 630$ proper colorings.

Therefore the pentagon has $3750 - 630 = 3120$ valid colorings.

The answer is $\boxed{\textbf{(C)}\ 3120}$.

Draw the constraint graph, not the picture: vertices joined by a diagonal are exactly the "must differ" pairs, and for a pentagon those pairs form the pentagram, a single cycle. Cycles are counted by the recursion "path count minus the smaller cycle," which here gives $6\cdot5^4 - (6\cdot5^3 - 6\cdot5\cdot4)$. The general result $(k-1)^n + (-1)^n(k-1)$ for an $n$-cycle with $k$ colors is worth remembering.

Casework along the loop. Color $A$ ($6$), then $C \ne A$ ($5$), then $E \ne C$ ($5$). If $E = A$ (one of those $5$ ways), $B$ has $5$ choices and $D$ must avoid $A$ and $B$: $5 \cdot 4 = 20$. If $E \ne A$ ($4$ ways), then $B \ne E$: either $B = A$ (then $D$ has $5$) or $B$ is one of $4$ others (then $D$ has $4$), giving $5 + 16 = 21$. Total $30(20 + 4 \cdot 21) = 30 \cdot 104 = 3120$.

• Coloring the vertices in order with 6, 5, 5, 5, 5 choices (3750) and never closing the loop, or applying the restriction to sides instead of diagonals.
• Believing the answer must be $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 720$ or similar because "all five ends must differ"; only diagonal endpoints must differ, and adjacent vertices may share a color.