2011 AIME I Problem 5

Attempt Problem 5 of the 2011 AIME I 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 2011 AIME I solutions, or check the answer key.

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

5.

The vertices of a regular nonagon (99-sided polygon) are to be labeled with the digits 11 through 99 in such a way that the sum of the numbers on every three consecutive vertices is a multiple of 3.3. Two acceptable arrangements are considered to be indistinguishable if one can be obtained from the other by rotating the nonagon in the plane. Find the number of distinguishable acceptable arrangements.

Answer: 144
Concepts:modular arithmeticcircular arrangementsmultiplication principle
Difficulty rating: 2420
Solution:

Two overlapping triples of consecutive vertices share two labels, so their sums differ by labels three positions apart. Since all triple sums are multiples of 3,3, labels three apart are congruent mod 3.3. Thus the position classes {1,4,7},\{1, 4, 7\}, {2,5,8},\{2, 5, 8\}, {3,6,9}\{3, 6, 9\} each carry a single residue class of digits, and the digits 11 through 99 consist of exactly three digits from each residue class mod 3.3.

Every triple of consecutive positions then contains one digit from each residue class, with sum 0+1+20(mod3),\equiv 0 + 1 + 2 \equiv 0 \pmod 3, so all 3!3! assignments of residue classes to position classes are acceptable, and within each position class the three digits can be arranged in 3!3! ways. That gives 3!(3!)3=64=12963! \cdot (3!)^3 = 6^4 = 1296 acceptable labelings.

Because the digits are distinct, no nontrivial rotation fixes a labeling, so the 12961296 labelings split into rotation classes of size 9,9, giving 12969=144\frac{1296}{9} = 144 distinguishable arrangements.

← Problem 4#4
Full Exam

Problem 5 in Other Years