2011 AIME I Problem 5

Below is the professionally curated solution for Problem 5 of the 2011 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticcircular arrangementsmultiplication principle

Difficulty rating: 2420

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.

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 4Full ExamProblem 6

Problem 5 in Other Years