2011 AIME I Problem 5

Question

The vertices of a regular nonagon (

9

-sided polygon) are to be labeled with the digits

1

through

9

in such a way that the sum of the numbers on every three consecutive vertices is a multiple of

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

Answer: 144

Concepts:modular arithmetic circular arrangements multiplication principle

Difficulty rating: 2420

Small hint:

Compare two overlapping triples of consecutive vertices: their sums differ by the labels three apart, so labels three apart are congruent mod

3

Big hint:

Each of the residue classes

\{3,6,9\},

\{1,4,7\},

\{2,5,8\}

occupies one of the three position classes; count assignments and orderings, then divide by

9

rotations

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,

labels three apart are congruent mod

3.

Thus the position classes

\{1, 4, 7\},

\{2, 5, 8\},

\{3, 6, 9\}

each carry a single residue class of digits, and the digits

1

through

9

consist of exactly three digits from each residue class mod

3.

Every triple of consecutive positions then contains one digit from each residue class, with sum

\equiv 0 + 1 + 2 \equiv 0 \pmod 3,

so all

3!

assignments of residue classes to position classes are acceptable, and within each position class the three digits can be arranged in

3!

ways. That gives

3! \cdot (3!)^3 = 6^4 = 1296

acceptable labelings.

Because the digits are distinct, no nontrivial rotation fixes a labeling, so the

1296

labelings split into rotation classes of size

9,

giving

\frac{1296}{9} = 144

distinguishable arrangements.