AMC 10 · 2017 · #25

Grade 11 counting

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

combinations-basicdivisibility-ruleschinese-remainder-theoremfactorial double-countingcasework ↑ Prerequisites: combinations-basicdivisibility-rules

📏 Long solution 💡 4 insights

Problem

There are n people. A team is a set of exactly 5 of them, and no two teams have the same five members, so the teams form a collection of distinct 5-element subsets. Look at every subset of 9 people and average the number of teams sitting entirely inside; then do the same over every subset of 8 people. These two averages are reciprocals of each other. Count how many n with 9 up to 2017 allow such a collection of teams to exist.

Pick an answer.

(A)

477

(B)

482

(C)

487

(D)

557

(E)

562

How to solve

Strategy Convert to Algebra

The statement is a sentence about averages, so Tool #13 (Convert to Algebra) carries the problem: rewrite "one average is the reciprocal of the other" as an equation and see what it forces. Tool #4 (Introduce a Variable) names the one quantity the averages can depend on, the number of teams T. Tool #15 (Organize Information in More Ways) does the real work of evaluating each average: counting team-and-group pairs from the team's side instead of the group's side turns a sum over C(n, 9) subsets into a single product, and the same double-count collapses the messy ratio into (C(9, 5))/(C(n, 5)). Once the condition becomes a divisibility statement, Tool #7 (Identify Subproblems) splits it into one independent question per prime power 2⁵, 3², 5, 7. Tool #5 (Look for a Pattern) finishes the count: the surviving condition reads only remainders, so it repeats with period 7 · 9 · 32=2016, and one full period plus a small correction at the ends gives the total.

1STEP 1

Name the number of teams

Let one letter be the number of teams.

1 ≤ T ≤ C(n, 5), TinZ

2STEP 2

Average as total over groups

An average is the total over the group count.

A₉=(TC(n-5, 4))/(C(n, 9)), A₈=(TC(n-5, 3))/(C(n, 8))

3STEP 3

Collapse both averages

Both averages collapse onto the same factor.

A₉=126 T/(C(n, 5)), A₈=56 T/(C(n, 5))

4STEP 4

Read the reciprocal as an equation

The reciprocal condition makes the product a perfect square.

126 · 56 T²=C(n, 5)² ⟹ (84T)²=C(n, 5)² ⟹ 84T=C(n, 5)

5STEP 5

Turn it into a divisibility test

The whole-number team count turns it into a divisibility test.

84 | C(n, 5)⇔ 2⁵ · 3² · 5 · 7 | n(n-1)(n-2)(n-3)(n-4)

6STEP 6

Handle each prime power

Each prime power is handled on its own.

mod 7: n≡ 0,1,2,3,4; mod 9: n≢ 5,8; mod 32: n≡ 0,2,4 ( mod 8) or n≡ 1,3 ( mod 16)

7STEP 7

Count one full period

Counting one full period gives 557.

560-3=557 → (D)

Answer

557

Three checks agree. First, a concrete case: n=10 gives C(10, 5)=252=84 · 3, so T=3 teams should work, and indeed A₉=(126 · 3)/252=3/2 and A₈=(56 · 3)/252=2/3, whose product is 1. Second, a density estimate: the three conditions pass a fraction 5/7·7/9·1/2=5/18 of all integers, and the range holds 2017-9+1=2009 values, so roughly 2009·5/18≈ 558 should qualify — right where 557 sits, while 477, 482, and 487 would need a density near 1/4 and 562 overshoots the whole period count adjusted for the ends. Third, recount with a different window: 1 ≤ n ≤ 2016 is also one full period and contributes 560. Shifting to 9 ≤ n ≤ 2017 drops n=1,2,3,4, all four of which satisfy the congruences, and adds n=2017, which is 1 more than 2016 and so has the same remainders as n=1 and does qualify. That gives 560-4+1=557, matching the first count through completely different bookkeeping.

💡Key takeaway

Both averages are the same fraction T/(C(n, 5)) scaled by a constant, so "one is the reciprocal of the other" collapses to C(n, 5)=84T, and the whole contest problem becomes counting which n make C(n, 5) a multiple of 84.

Name the number of teams
Average as total over groups
Collapse both averages
Read the reciprocal as an equation
Turn it into a divisibility test
Handle each prime power
Count one full period