设 $1\leqslant r\leqslant n$，考虑集合 $\{1,2,\cdots,n\}$ 的所有含 $r$ 个元素的子集及每个这样子集中最小的元素，用 $F(n,r)$ 表示所有这样的最小数的算术平均值．求证：$F(n,r)=\dfrac{n+1}{r+1}$．（联邦德国）
【难度】
【出处】
1981年第22届IMO试题
【标注】
【答案】
略
【解析】
集合 $\{1,2,\cdots,n\}$ 共有 $C_n^r$ 个 $r$ 元子集，对于最小元素为 $k(1\leqslant i\leqslant n-r+1)$ 的 $r$ 元子集，有 $C_{n-r}^{r-1}$ 个（其余的 $r-1$ 个元素取自 $k+1,k+2,\cdots,n$），所以 $\displaystyle F(n,r)=\dfrac{1}{C_n^r}\sum\limits_{k=1}^{n-r+1}kC_{n-k}^{r-1}$．
因为 $C_{n-k}^r+C_{n-k}^{r-1}=C_{n-k+1}^r$，所以
$kC_{n-k}^{r-1}=kC_{n-k+1}^{r}-kC_{n-k}^{r}=(k-1)C_{n-(k-1)}^{r}-kC_{n-k}^{r}+C_{n-(k-1)}^{r}$
于是
$\begin{aligned}\sum_{k=1}^{n-r+1}kC_{n-k}^{r-1}=&\sum_{k=1}^{n-r+1}[(k-1)C_{n-(k-1)}^{r}-kC_{n-k}^r]+\sum_{k=1}^{n-r+1}C_{n-(k-1)}^{r}\\&=\sum_{k=1}^{n-r+1}C_{n-k+1}^{r}\\&=\sum_{k=1}^{n-r+1}(C_{n-k+2}^{r+1}-C_{n-k+1}^{r+1})\\&=C_{n+1}^{r+1}
\end{aligned}$
所以 $F(n,r)=\dfrac{1}{C_n^r}\cdot C_{n+1}^{r+1}=\dfrac{n+1}{r+1}$．
因为 $C_{n-k}^r+C_{n-k}^{r-1}=C_{n-k+1}^r$，所以
$kC_{n-k}^{r-1}=kC_{n-k+1}^{r}-kC_{n-k}^{r}=(k-1)C_{n-(k-1)}^{r}-kC_{n-k}^{r}+C_{n-(k-1)}^{r}$
于是
$\begin{aligned}\sum_{k=1}^{n-r+1}kC_{n-k}^{r-1}=&\sum_{k=1}^{n-r+1}[(k-1)C_{n-(k-1)}^{r}-kC_{n-k}^r]+\sum_{k=1}^{n-r+1}C_{n-(k-1)}^{r}\\&=\sum_{k=1}^{n-r+1}C_{n-k+1}^{r}\\&=\sum_{k=1}^{n-r+1}(C_{n-k+2}^{r+1}-C_{n-k+1}^{r+1})\\&=C_{n+1}^{r+1}
\end{aligned}$
所以 $F(n,r)=\dfrac{1}{C_n^r}\cdot C_{n+1}^{r+1}=\dfrac{n+1}{r+1}$．
答案
解析
备注
