AMC 10 · 2021 · #25

Grade 11 countingnumber-theory

Archetype Modular Cycle Frequency Count └ Sub-archetype Floor Count Across Residue Bins

permutations-basicmodular-arithmeticsymmetry-argumentvieta-formulas symmetry-argumentidentify-subproblems ↑ Prerequisites: permutations-basicmodular-arithmetic

📏 Long solution 💡 4 insights

Problem

For each odd integer at least five, count the ordered quadruples of pairwise different integers from one up to that number whose sum is a multiple of it. One fixed cubic polynomial equals that count for every such odd number. Find the coefficient of the linear term.

Pick an answer.

(A)

${-}6$

(B)

${-}1$

(C)

(D)

(E)

How to solve

Strategy Organize Information in More Ways

Counting the good quadruples one at a time is hopeless because the divisibility condition tangles all four entries together. Tool #15 (Organize Information in More Ways) is the move: instead of examining quadruples individually, bundle them into families and count families. Tool #4 (Introduce a Variable) supplies the bundling rule — a shift amount k that is added to all four entries at once, wrapping around modulo m. Tool #2 (Make a Systematic List) does the plain permutation count of all quadruples and then divides it among the families. Tool #9 (Solve an Easier Related Problem) checks the resulting formula against m=5, which is small enough to count by hand. Tool #13 (Convert to Algebra) finishes by expanding the product form of the count into standard c₃x³+c₂x²+c₁x+c₀ shape so the requested coefficient can be read off.

1STEP 1

Count every quadruple first

Count every quadruple first.

T=m(m-1)(m-2)(m-3)

2STEP 2

Shift all four entries together

Shift all four entries together.

σ_k(a₁,a₂,a₃,a₄)=(a₁+k, a₂+k, a₃+k, a₄+k) mod m, k=0,1,…,m-1

3STEP 3

Track what the shift does to the sum

The shift changes the sum predictably.

S ↦ S+4k (mod m); 4k≡ -S (mod m) ⇔ k≡ -4⁻¹S (mod m) (exactly one k)

4STEP 4

Divide the pool by the family size

In each family exactly one works.

D(m)=(m(m-1)(m-2)(m-3))/m=(m-1)(m-2)(m-3)

5STEP 5

Test the formula at m=5

Test the formula on a small value.

D(5)=4!=24=(5-1)(5-2)(5-3)

6STEP 6

Expand and read off c₁

Expanding gives a linear coefficient of 11.

q(x)=(x-1)(x-2)(x-3)=x³-6x²+11x-6 → c₁=11 → (E)

Answer

Check a second value. The formula gives D(7)=6 · 5 · 4=120, and evaluating the expanded cubic gives q(7)=343-294+77-6=120, so the expansion is arithmetically sound. The count is also plausible on its own terms: D(m) must be a multiple of 4!=24 because every valid set of four entries can be ordered in 24 ways, and (m-1)(m-2)(m-3) is a product of three consecutive integers times nothing else — for m=5 that is 24, for m=7 it is 120=5 · 24, both multiples of 24 as required. The oddness of m is doing real work and is not decoration: if m were even, gcd(4,m) ≠ 1 and the congruence 4k≡ -S would have either no solution or several, so the one-per-family argument would collapse. Finally, the distractor list is a warning worth noticing — the expanded cubic has c₂=-6 and c₀=-6, and choices (A) -6 and (D) 6 are exactly those numbers and their negatives, so reading the wrong coefficient is the intended trap. The requested coefficient is the one on x, giving 11 and choice (E).

💡Key takeaway

Adding the same number to all four entries and wrapping around m keeps them distinct and pushes the sum by 4k, so in each family of m shifted quadruples exactly one sum is a multiple of m — that makes D(m)=(m-1)(m-2)(m-3), whose x-coefficient is 11.

Count every quadruple first
Shift all four entries together
Track what the shift does to the sum
Divide the pool by the family size
Test the formula at m=5
Expand and read off c₁