Даны натуральные числа $n$ и $r$, $1\le r\le n$. Рассмотрим всевозможные подмножества множества $\{1,2,\ldots,n\}$, состоящие из $r$ чисел, и в каждом выберем наименьшее число. Докажите, что среднее арифметическое всех выбранных чисел равно $\dfrac{n+1}{r+1}$. (Например, при $n=3$, $r=2$ получаем три подмножества $\{1,2\}$, $\{1,3\}$, $\{2,3\}$ и среднее арифметическое равно $\dfrac{1+1+2}3=\dfrac43\Big)$.
Международная математическая олимпиада школьников (XXII, 1981 год)
Прежде всего заметим, что у множества $\{1,2,\ldots,n\}$ имеется $C_n^r=\dfrac{n!}{r!\,(n-r)!}$ подмножеств, состоящих из $r$ чисел. Мы приведём два свойства чисел $C_n^k$, которые понадобятся нам для решения нашей задачи:
$$\begin{array}{rc}
1^\circ.\quad&C_n^k+C_n^{k+1}=C_{n+1}^{k+1};\\[3pt]
2^\circ.\quad&C_n^k+C_{n-1}^k+\ldots+C_k^k=C_{n+1}^{k+1}.
\end{array}$$
Будем называть подмножества множества $\{1,2,\ldots,n\}$, состоящие из $r$ чисел, $r$-подмножествами. Легко сообразить, что наименьшими элементами $r$-подмножеств множества $\{1,2,\ldots,n\}$ могут быть только числа 1, 2, $\ldots$, $n-r+1$. При этом число $k$ является наименьшим сразу для $C_{n-k}^{r-1}$ таких подмножеств (в самом деле, каждое $r$-подмножество, для которого число $k$ является наименьшим элементом, содержит наряду с $k$ ещё $r-1$ элементов из множества $\{k+1,k+2,\ldots,n\}$, состоящего из $n-k$ элементов). Поэтому сумма всех выбранных чисел равна
$$
S=1\cdot C_{n-1}^{r-1}+2\cdot C_{n-2}^{r-1}+\ldots+(n-r+1)C_{r-1}^{r-1},\tag{*}
$$
и нужно показать, что среднее арифметическое $\dfrac S{C_n^r}$ (всего имеется $C_n^r$ $r$-подмножеств) равно $\dfrac{n+1}{r+1}$, или что $S=C_n^r\cdot\dfrac{n+1}{r+1}=C_{n+1}^{r+1}$.
Воспользовавшись тем, что $C_{n-1}^{k-1}=C_n^k-C_{n-1}^k$ (см. $1^\circ$), преобразуем сумму $S$ следующим образом:
$$\begin{gather*}
S=1\cdot C_{n-1}^{r-1}+2\cdot C_{n-2}^{r-1}+\ldots+(n-r+1)C_{r-1}^{r-1}=\\
=1\cdot(C_n^r-C_{n-1}^r)+2\cdot(C_{n-1}^r-C_{n-2}^r)+\ldots+(n-r)(C_{r+1}^r-C_r^r)+(n-r+1)C_r^r=\\
=C_n^r+C_{n-1}^r+\ldots+C_r^r.
\end{gather*}$$
Учитывая свойство $2^\circ$, получаем $S=C_{n+1}^{r+1}$, что и требовалось.
Рис. 2. $S(n+1,r=S(n,r)+S(n,r-1)$, поскольку число $n+1$ либо не входит в $r$-подмножество множества $\lbrace1,2,\ldots,n+1\rbrace$ (этому соответствует слагаемое $S(n,r)$), либо входит в него (тогда получается слагаемое $S(n,r-1)$).
Эту задачу можно решить и по индукции, рассмотрев множество $\{1,2,\ldots,n+1\}$ и заметив, что $$
S(n+1,r)=S(n,r)+S(n,r-1)\tag{**}
$$
(см. рис. 2); здесь через $S(m,k)$ обозначена сумма наименьших чисел $k$-подмножеств множества $\{1,2,\ldots,m\}$. Предположив доказанными равенства
$$
S(n,r)=C_{n+1}^{r+1},\quad S(n,r-1)=C_{n+1}^r
$$
для $r$- и $(r-1)$-подмножеств множества $\{1,2,\ldots,n\}$ (базис индукции содержится в условии задачи), получим, учитывая (**) и свойство $1^\circ$,
$$
S(n+1,r)=C_{n+1}^{r+1}+C_{n+1}^r=C_{n+2}^{r+1},
$$
что и требуется.
Интересно, что сумма наибольших чисел в $r$-подмножествах множества $\{1,2,\ldots,n\}$ равна
$$
n\cdot C_{n-1}^{r-1}+(n-1)C_{n-2}^{r-1}+\ldots+r\cdot C_{r-1}^{r-1},\tag{***}
$$
так что сумма средних арифметических наибольших и наименьших чисел этих подмножеств равна (см. (*), (***) и $2^\circ$) $n+1$. Отсюда получаем, что среднее арифметическое наибольших чисел в выбранных подмножествах равно $r\cdot\dfrac{n+1}{r+1}$. Оказывается, вообще для любого $j$, $j\le r\le n$, верно следующее утверждение: среднее арифметическое $j$-x по величине чисел $r$-подмножеств множества $\{1,2,\ldots,n\}$ равно $j\cdot\dfrac{n+1}{r+1}$. Докажите его самостоятельно.
