AMC 10 · 2011 · #22
Grade 7 countingEach 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?
Pick an answer.
AMC 10 2011 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: A convex pentagon $ABCDE$ has each of its $5$ corners painted with one of $6$ available colors. The only rule: the two endpoints of every diagonal must be different colors. The five sides carry no rule at all. Count how many colorings obey the rule.
Givens: Pentagon $ABCDE$ has $5$ vertices; $6$ colors are available; a color may be reused on many vertices; The two ends of each diagonal must be different colors; The five diagonals are $AC$, $CE$, $EB$, $BD$, $DA$; Sides ($AB, BC, CD, DE, EA$) have no color restriction; Answer choices: (A) $2520$, (B) $2880$, (C) $3120$, (D) $3250$, (E) $3750$
Unknowns: The number of valid colorings of the five vertices
Understand
Restated: A convex pentagon $ABCDE$ has each of its $5$ corners painted with one of $6$ available colors. The only rule: the two endpoints of every diagonal must be different colors. The five sides carry no rule at all. Count how many colorings obey the rule.
Givens: Pentagon $ABCDE$ has $5$ vertices; $6$ colors are available; a color may be reused on many vertices; The two ends of each diagonal must be different colors; The five diagonals are $AC$, $CE$, $EB$, $BD$, $DA$; Sides ($AB, BC, CD, DE, EA$) have no color restriction; Answer choices: (A) $2520$, (B) $2880$, (C) $3120$, (D) $3250$, (E) $3750$
Plan
Primary tool: #1 Draw a Diagram
Secondary: #7 Identify Subproblems, #2 Make a Systematic List, #16 Change Focus / Count the Complement
The words "ends of each diagonal differ" hide a clean shape, so Tool #1 (Draw a Diagram) is the first move: draw only the diagonals and follow them. They form a five-pointed star, and walking the star visits all five vertices and returns to the start — it is one closed loop (a ring) of $5$. That turns the problem into "color a ring of $5$ so neighbors differ, using $6$ colors." Tool #2 (Make a Systematic List) counts the easy open-chain version with the multiplication counting principle. Tool #7 (Identify Subproblems) and Tool #16 (Count the Complement) then repair the one link the chain ignored by subtracting the bad cases, which shrinks the ring by one and gives a short recursion.
Execute — Answer: C
7.SP.C.8 Step 1 Turn the diagonals into a ring
- Draw only the diagonals: $AC$, $CE$, $EB$, $BD$, $DA$.
- Follow them in order $A \to C \to E \to B \to D \to A$.
- This single walk uses all five diagonals, touches each vertex exactly once, and comes back to $A$ — the five-pointed star is one closed loop of $5$ vertices.
- Sides have no rule, so the whole problem becomes: color a ring of $5$ vertices (in the order $A, C, E, B, D$) with $6$ colors so that any two neighbors in the ring get different colors.
💡 Every diagonal is one link of the star, and the star closes up into a single loop, so "diagonal ends differ" just means "ring neighbors differ."
7.SP.C.8 Step 2 Count the open chain first
- Temporarily cut the loop at the last link $D - A$, leaving an open chain $A - C - E - B - D$.
- Color it left to right.
- The first vertex $A$ can be any of $6$ colors.
- Every later vertex only has to avoid the one color just before it, so it has $5$ choices.
- By the multiplication counting principle the chain has $6 \cdot 5 \cdot 5 \cdot 5 \cdot 5$ colorings.
💡 Down a chain each new vertex dodges only its single left neighbor, so it always has $5$ safe colors.
7.SP.C.8 Step 3 Spot the one broken rule
- The chain count of $3750$ ignored exactly one diagonal: the closing link $D - A$.
- Some of those $3750$ colorings are illegal because they gave $A$ and $D$ the same color.
- So the true ring count is $3750$ minus the number of chain colorings where the first vertex $A$ and the last vertex $D$ match.
💡 The open chain over-counts by allowing the two ends to clash, so subtract just the clashing ones.
7.SP.C.8 Step 4 Glue the ends: a smaller ring
- Count the bad chains where $A$ and $D$ share a color.
- If those two ends must be equal, treat them as one merged vertex.
- The chain's links $A-C$, $C-E$, $E-B$, $B-D$ then close into a ring of $4$ vertices $A - C - E - B - (A)$, and each link still demands different colors.
- So the bad count equals the number of valid colorings of a $4$-vertex ring.
- This is the very same puzzle, one size smaller, giving the rule $R_n = 6 \cdot 5^{\,n-1} - R_{n-1}$.
💡 Forcing the two loose ends to match fuses them into one vertex, shrinking the ring by exactly one.
6.EE.A.1 Step 5 Work down to the 4-ring
- Use the rule with a base case.
- A $3$-ring is a triangle where all three vertices are pairwise neighbors, so $R_3 = 6 \cdot 5 \cdot 4 = 120$.
- Then the $4$-ring is $R_4 = 6 \cdot 5^3 - R_3 = 750 - 120 = 630$.
- That $630$ is the number of bad chains from the previous step.
💡 The same subtract-the-smaller-ring rule bottoms out at the triangle, whose count is a plain product.
7.SP.C.8 Step 6 Finish the 5-ring
- Put it together: the $5$-ring count is the chain count minus the bad (equal-ends) count, $R_5 = 3750 - 630 = 3120$.
- That is the number of valid colorings of pentagon $ABCDE$, so the answer is $(C)$.
💡 One subtraction closes the loop: start from the free chain, remove the colorings the last diagonal forbids.
7.SP.C.8 Draw only the diagonals: $AC$, $CE$, $EB$, $BD$, $DA$. Follow them in order $A \ 7.SP.C.8 Temporarily cut the loop at the last link $D - A$, leaving an open chain $A - C 7.SP.C.8 The chain count of $3750$ ignored exactly one diagonal: the closing link $D - A$ 7.SP.C.8 Count the bad chains where $A$ and $D$ share a color. If those two ends must be 6.EE.A.1 Use the rule with a base case. A $3$-ring is a triangle where all three vertices 7.SP.C.8 Put it together: the $5$-ring count is the chain count minus the bad (equal-ends Review
Reasonableness: The open-chain count $3750$ (choice E) is a clean upper bound, because it obeys four of the five diagonal rules and ignores only the closing one; the real answer must be a little smaller, and $3120 < 3750$ by a sensible $630$. Choice E is exactly the trap for anyone who forgets the last diagonal. Independent check with the cycle-coloring formula $(k-1)^n + (-1)^n (k-1)$ for $n = 5$, $k = 6$: $5^5 - 5 = 3125 - 5 = 3120$. Both routes agree, confirming $(C)$.
Alternative: Tool #7 (Identify Subproblems) by direct casework on the closing diagonal $DA$: over the chain $A-C-E-B-D$, split on whether $D$ equals $A$ or not, using that among the $5$ ways to color $D$ (avoiding $B$) exactly one might coincide with $A$. Tracking that pair through the chain reproduces $3120$. A slicker route recognizes the diagonal graph is the $5$-cycle $C_5$ and quotes its chromatic polynomial $(k-1)^5 + (k-1)(-1)^5 = 5^5 - 5 = 3120$ at $k = 6$.
CCSS standards used (min grade 7)
7.SP.C.8Find probabilities of compound events using organized lists, tables, and simulation (Structuring the diagonals as a ring, applying the multiplication counting principle to the chain ($6 \cdot 5^4$), and subtracting the complement (equal-ends colorings) to fix the closing diagonal.)6.EE.A.1Write and evaluate numerical expressions involving whole-number exponents (Evaluating the powers of $5$ in the counts $6 \cdot 5^4 = 3750$ and $6 \cdot 5^3 = 750$ inside the recursion.)
⭐ Hidden inside the pentagon, the diagonals form one five-point ring, so the puzzle is just "color a loop of 5 with 6 colors so neighbors differ": count the easy open chain ($6 \cdot 5^4 = 3750$), then subtract the $630$ that break the last link to land on $3120$.
⭐ Hidden inside the pentagon, the diagonals form one five-point ring, so the puzzle is just "color a loop of 5 with 6 colors so neighbors differ": count the easy open chain ($6 \cdot 5^4 = 3750$), then subtract the $630$ that break the last link to land on $3120$.
More like this
Same archetype — closest grade level first.