Problem:
A set of n people participate in an online video basketball tournament. Each person may be a member of any number of 5-player teams, but no two teams may have exactly the same 5 members. The site statistics show a curious fact: The average, over all subsets of size 9 of the set of n participants, of the number of complete teams whose members are among those 9 people is equal to the reciprocal of the average, over all subsets of size 8 of the set of n participants, of the number of complete teams whose members are among those 8 people. How many values n,9≤n≤2017, can be the number of participants?
Answer Choices:
A. 477
B. 482
C. 487
D. 557
E. 562
Solution:
Let T be the number of teams participating in the tournament, and let P be the set of participants. For every A⊆P let f(A) be the number of teams whose 5 players are in A. According to the described property,
⎝⎜⎜⎜⎛(n9)1A⊆P∣A∣=9∑f(A)⎠⎟⎟⎟⎞⋅⎝⎜⎜⎜⎛(n8)1A⊆P∣A∣=8∑f(A)⎠⎟⎟⎟⎞=1
Note that each of the T teams is counted exactly (n−54) times in the sum ∑A⊆P∣A∣=9f(A). Indeed, once a particular team is fixed, there are exactly (n−54) ways of choosing the remaining 4 persons to determine a set A of size 9 . Thus the sum in the first factor is equal to (n−54)T; similarly, the sum in the second factor is equal to (n−53)T. The described property is now equivalent to
(n9)(n8)(n−54)(n−53)T2=1
Therefore
T2=((n−5)!)29!8!(n!)24!3!=9⋅82⋅72⋅62⋅52⋅4n2(n−1)2(n−2)2(n−3)2(n−4)2
so
T=8⋅7⋅6⋅5⋅3⋅2n(n−1)(n−2)(n−3)(n−4)=25⋅32⋅5⋅7n(n−1)(n−2)(n−3)(n−4).
Thus a number n has the required property if and only if T is an integer and n≥9. Let N=n(n−1)(n−2)(n−3)(n−4); because
N consists of the product of five consecutive integers, it is always a multiple of 5. Similarly, N≡0(mod7) if and only if n≡0,1,2,3,4 (mod7),N≡0(mod9) if and only if n≡0,1,2,3,4,6,7(mod9), and N≡0(mod32) if and only if n≡0,1,2,3,4,8,10,12(mod16). Therefore by the Chinese Reminder Theorem there are exactly 5⋅7. 8=280 residue-class solutions mod16⋅9⋅7=1008. Thus there are 2⋅280=560 values of n with the desired property in the interval 1≤n≤2⋅1008=2016. The numbers 1,2,3, and 4 are among them, and 5,6,7, and 8 are not. In addition, 2017≡1(mod1008); thus 2017 is also a valid value of n. Therefore there are 560−4+1=557 possible values of n in the required range.
The problems on this page are the property of the MAA's American Mathematics Competitions