2025 AIME II Problem 11

Attempt Problem 11 of the 2025 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2025 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

11.

Let SS be the set of vertices of a regular 2424-gon. Find the number of ways to draw 1212 segments of equal lengths so that each vertex in SS is an endpoint of exactly one of the 1212 segments.

Answer: 113
Concepts:regular polygongraph theorygreatest common divisorcasework
Difficulty rating: 3060
Solution:

Two chords of a circle through equally spaced points have equal length exactly when they skip the same number of vertices, so all 1212 segments join pairs of vertices exactly kk apart for one common k{1,,12}.k \in \{1, \ldots, 12\}. For fixed k,k, form the graph on the 2424 vertices joining each ii to i±k(mod24):i \pm k \pmod{24}: we need a perfect matching in this graph. For k<12k \lt 12 the graph is a disjoint union of gcd(24,k)\gcd(24, k) cycles of length 24/gcd(24,k),24/\gcd(24, k), while for k=12k = 12 it is 1212 disjoint diameters.

A cycle of even length has exactly 22 perfect matchings (alternate edges), and a cycle of odd length has none. So each k<12k \lt 12 with even cycle length contributes 2gcd(24,k):2^{\gcd(24, k)}: k=1,5,7,11k = 1, 5, 7, 11 give 22 each; k=2,10k = 2, 10 give 44 each; k=3,9k = 3, 9 give 88 each; k=4k = 4 gives 16;16; k=6k = 6 gives 64.64. For k=8k = 8 the cycles have odd length 3,3, giving 0.0. For k=12k = 12 the matching is forced: 11 way.

The total is 42+24+284 \cdot 2 + 2 \cdot 4 + 2 \cdot 8 +16+64+0+1+ 16 + 64 + 0 + 1 =113.= 113.

← Problem 10#10
Full Exam

Problem 11 in Other Years