AMC12 2017 B

AMC12 2017 B · Q25

AMC12 2017 B · Q25. It mainly tests Combinations, Counting & probability misc.

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 \leq n \leq 2017$, can be the number of participants?

有n个人参加在线视频篮球锦标赛。每人可加入任意多个5人团队，但无两个团队有完全相同的5名成员。网站统计显示一个奇特事实：对n名参与者所有大小为9的子集，完整团队（成员都在这9人中）的数量的平均值，等于对所有大小为8的子集的相同平均值的倒数。有多少个n（$9 \leq n \leq 2017$）可以是参与者人数？

(A) 477 477

(B) 482 482

(D) 557 557

(E) 562 562

Answer

Correct choice: (D)

正确答案：（D）

Solution

Answer (D): Let $T$ be the number of teams participating in the tournament, and let $P$ be the set of participants. For every $A\subseteq P$ let $f(A)$ be the number of teams whose 5 players are in $A$. According to the described property, $\left(\frac{1}{\binom{n}{9}}\sum_{\substack{A\subseteq P\\ |A|=9}} f(A)\right)\cdot\left(\frac{1}{\binom{n}{8}}\sum_{\substack{A\subseteq P\\ |A|=8}} f(A)\right)=1.$ Note that each of the $T$ teams is counted exactly $\binom{n-5}{4}$ times in the sum $\sum_{\substack{A\subseteq P\\ |A|=9}} f(A)$. Indeed, once a particular team is fixed, there are exactly $\binom{n-5}{4}$ 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 $\binom{n-5}{4}T$; similarly, the sum in the second factor is equal to $\binom{n-5}{3}T$. The described property is now equivalent to $\frac{\binom{n-5}{4}\binom{n-5}{3}T^2}{\binom{n}{9}\binom{n}{8}}=1.$ Therefore $T^2=\frac{(n!)^2\,4!\,3!}{((n-5)!)^2\,9!\,8!}=\frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{9\cdot 8^2\cdot 7^2\cdot 6^2\cdot 5^2\cdot 4},$ so $T=\frac{n(n-1)(n-2)(n-3)(n-4)}{8\cdot 7\cdot 6\cdot 5\cdot 3\cdot 2}=\frac{n(n-1)(n-2)(n-3)(n-4)}{2^5\cdot 3^2\cdot 5\cdot 7}.$ Thus a number $n$ has the required property if and only if $T$ is an integer and $n\ge 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\equiv 0\pmod 7$ if and only if $n\equiv 0,1,2,3,4\pmod 7$, $N\equiv 0\pmod 9$ if and only if $n\equiv 0,1,2,3,4,6,7\pmod 9$, and $N\equiv 0\pmod{32}$ if and only if $n\equiv 0,1,2,3,4,8,10,12\pmod{16}$. Therefore by the Chinese Remainder Theorem there are exactly $5\cdot 7\cdot 8=280$ residue-class solutions mod $16\cdot 9\cdot 7=1008$. Thus there are $2\cdot 280=560$ values of $n$ with the desired property in the interval $1\le n\le 2\cdot 1008=2016$. The numbers 1, 2, 3, and 4 are among them, but 5, 6, 7, and 8 are not. In addition, $2017\equiv 1\pmod{1008}$; thus 2017 is also a valid value of $n$. Therefore there are $560-4+1=557$ possible values of $n$ in the required range.

答案（D）：设 $T$ 为参加锦标赛的队伍数，设 $P$ 为参赛者集合。对每个 $A\subseteq P$，令 $f(A)$ 表示其 5 名队员都在 $A$ 中的队伍数量。根据题述性质， $\left(\frac{1}{\binom{n}{9}}\sum_{\substack{A\subseteq P\\ |A|=9}} f(A)\right)\cdot\left(\frac{1}{\binom{n}{8}}\sum_{\substack{A\subseteq P\\ |A|=8}} f(A)\right)=1.$ 注意，在和式 $\sum_{\substack{A\subseteq P\\ |A|=9}} f(A)$ 中，每支队伍恰好被计数 $\binom{n-5}{4}$ 次。确实，固定一支队伍后，为了确定一个大小为 9 的集合 $A$，只需从其余人中选择剩下的 4 人，而这样的选法正好有 $\binom{n-5}{4}$ 种。因此第一个括号中的和等于 $\binom{n-5}{4}T$；同理，第二个括号中的和等于 $\binom{n-5}{3}T$。于是题述性质等价于 $\frac{\binom{n-5}{4}\binom{n-5}{3}T^2}{\binom{n}{9}\binom{n}{8}}=1.$ 因此 $T^2=\frac{(n!)^2\,4!\,3!}{((n-5)!)^2\,9!\,8!}=\frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{9\cdot 8^2\cdot 7^2\cdot 6^2\cdot 5^2\cdot 4},$ 从而 $T=\frac{n(n-1)(n-2)(n-3)(n-4)}{8\cdot 7\cdot 6\cdot 5\cdot 3\cdot 2}=\frac{n(n-1)(n-2)(n-3)(n-4)}{2^5\cdot 3^2\cdot 5\cdot 7}.$ 因此，一个数 $n$ 具有所需性质当且仅当 $T$ 为整数且 $n\ge 9$。令 $N=n(n-1)(n-2)(n-3)(n-4)$；由于 $N$ 是五个连续整数的乘积，它总是 5 的倍数。类似地，当且仅当 $n\equiv 0,1,2,3,4\pmod 7$ 时有 $N\equiv 0\pmod 7$；当且仅当 $n\equiv 0,1,2,3,4,6,7\pmod 9$ 时有 $N\equiv 0\pmod 9$；当且仅当 $n\equiv 0,1,2,3,4,8,10,12\pmod{16}$ 时有 $N\equiv 0\pmod{32}$。因此由中国剩余定理，模 $16\cdot 9\cdot 7=1008$ 恰有 $5\cdot 7\cdot 8=280$ 个剩余类解。于是区间 $1\le n\le 2\cdot 1008=2016$ 内满足所需性质的 $n$ 的取值共有 $2\cdot 280=560$ 个。其中 1、2、3、4 在内，但 5、6、7、8 不在内。另外，$2017\equiv 1\pmod{1008}$，因此 2017 也是一个可行的 $n$。所以在所要求范围内可能的 $n$ 值共有 $560-4+1=557$ 个。

Topics