2017 AMC 12B Problem 25

Attempt Problem 25 of the 2017 AMC 12B 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 2017 AMC 12B solutions, or check the answer key.

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

25.

A set of nn people participate in an online video basketball tournament. Each person may be a member of any number of 55-player teams, but no two teams may have exactly the same 55 members. The site statistics show a curious fact: The average, over all subsets of size 99 of the set of nn participants, of the number of complete teams whose members are among those 99 people is equal to the reciprocal of the average, over all subsets of size 88 of the set of nn participants, of the number of complete teams whose members are among those 88 people. How many values n,n, 9n2017,9 \le n \le 2017, can be the number of participants?

477477

482482

487487

557557

562562

Answer: D
Concepts:double countingdivisibilityChinese Remainder Theorem
Difficulty rating: 2650
Solution:

Let TT be the number of teams. Summing over size-99 subsets counts each team (n54)\binom{n-5}{4} times and over size-88 subsets (n53)\binom{n-5}{3} times. The averages are (n54)T(n9)\dfrac{\binom{n-5}{4}T}{\binom n9} and (n53)T(n8);\dfrac{\binom{n-5}{3}T}{\binom n8}; setting the first equal to the reciprocal of the second and simplifying gives T=n(n1)(n2)(n3)(n4)253257. \begin{aligned} &T \\ &\quad {}= \scriptsize \frac{n(n-1)(n-2)(n-3)(n-4)}{2^5 \cdot 3^2 \cdot 5 \cdot 7}. \end{aligned} We need this to be a positive integer with n9.n \ge 9. Let N=N = n(n1)(n2)(n3)(n4);n(n-1)(n-2)(n-3)(n-4); as a product of five consecutive integers, NN is always divisible by 5.5. The condition 7N7\mid N holds for 55 residues modulo 7;7; 9N9\mid N holds for 77 residues modulo 9;9; and 32N32\mid N holds for 88 residues modulo 16.16. The Chinese Remainder Theorem therefore gives 578=2805\cdot7\cdot8=280 solutions modulo lcm(7,9,16)=1008.\operatorname{lcm}(7,9,16)=1008. So there are 560560 values in 1n2016;1 \le n \le 2016; removing n=1,2,3,4n = 1, 2, 3, 4 (which are below 99) and adding n=2017n = 2017 (since 20171(mod1008)2017 \equiv 1 \pmod{1008}) gives 5604+1=557560 - 4 + 1 = 557 valid values.

Thus, the correct answer is D.

← Problem 24#24
Full Exam

Problem 25 in Other Years