2011 AMC 10A Problem 22

1. Draw the diagonals. A pentagon has $5$ diagonals: $AC$, $CE$, $EB$, $BD$, $DA$. Written in this order, each one starts where the last one ended, so they form one closed loop (the five-pointed star):
$$A \to C \to E \to B \to D \to A.$$
2. Restate the rule. "The ends of each diagonal have different colors" now just means: any two vertices next to each other on this loop must have different colors. The sides of the pentagon don't matter at all.
3. Color around the loop. Go in the order $A, C, E, B, D$. The tricky part is at the end: $D$ must differ from both $B$ and $A$. How many choices $D$ has depends on whether $B$ and $A$ have the same color, so we keep track of that.
- $A$: $6$ choices.
- $C$: must differ from $A$, so $5$ choices.
- $E$: must differ from $C$, so $5$ choices. Split into two cases, depending on whether $E$ has the same color as $A$.
4. Case 1: $E$ is the same color as $A$ ($1$ of the $5$ choices for $E$).
- $B$ must differ from $E$, which is $A$'s color: $5$ choices, and $B$ is automatically different from $A$.
- $D$ must differ from $B$ and from $A$, which are two different colors: $4$ choices.
- That gives $5 \times 4 = 20$ ways to finish.
5. Case 2: $E$ is a different color from $A$ ($4$ of the $5$ choices for $E$). Now $B$ must differ from $E$, which leaves $5$ colors. One of those is $A$'s color.
- If $B$ has $A$'s color ($1$ way), then $D$ only has to avoid that one color: $5$ choices.
- If $B$ has another color ($4$ ways), then $D$ must avoid two different colors: $4$ choices.
- That gives $1 \times 5 + 4 \times 4 = 21$ ways to finish, for each of the $4$ choices of $E$.
6. Add it up. After $A$ and $C$ ($6 \times 5 = 30$ ways), the number of ways to finish is $1 \times 20 + 4 \times 21 = 104$. So the total is
$$30 \times 104 = 3120.$$

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

Look at which pairs must differ, not at the shape of the pentagon. Here those pairs form a single loop of five. Coloring around a loop is easy until the last vertex, which has two neighbours already colored. Its number of choices depends on whether those two neighbours match, so split into cases on exactly that.

Count first, then remove the bad colorings.

1. Color $A, C, E, B, D$ in order, each different from the one before, and ignore the rule between $D$ and $A$: $6 \times 5 \times 5 \times 5 \times 5 = 3750$ ways.
2. The bad ones are those where $D$ has the same color as $A$. In those, we can think of $D$ and $A$ as one vertex, and we are just coloring a loop of four, $A, C, E, B$, with neighbours different.
3. Count the loop of four the same way: $6 \times 5 \times 5 \times 5 = 750$ colorings along the path, minus those where $B$ matches $A$. Those are colorings of the triangle $A, C, E$ with all three colors different: $6 \times 5 \times 4 = 120$. So the loop of four has $750 - 120 = 630$ colorings.
4. The answer is $3750 - 630 = 3120$.