В тетради написано несколько чисел. К этим числам разрешается приписать число, равное среднему арифметическому двух или нескольких из них, если оно отлично от всех уже написанных чисел. Докажите, что, начав с двух чисел 0 и 1, с помощью описанных операций можно получить:
число $\dfrac{1}{5}$;
любое рациональное число между 0 и 1.
М. Серов
Всесоюзная XIII олимпиада школьников, 9 и 10 классы
Начнём с представления числа $\dfrac15$ и вообще $\dfrac1q$. Числа $\dfrac12$, $\dfrac14$, $\dfrac34$ получить очень просто:
$$
\dfrac12=\dfrac{0+1}2,\quad\dfrac14=\dfrac{0+\dfrac12}2,\quad\dfrac34=\dfrac{\dfrac12+1}2.
$$
Так же можно, очевидно, получить любую правильную двоично-рациональную дробь, т. е. дробь вида $\dfrac p{2^m}$, $p\lt2^m$ (рис. 1).
Рис. 1
Чтобы получить дробь $\dfrac1q$, достаточно представить 1 в виде суммы $q$ различных правильных двоично-рациональных дробей: их среднее арифметическое будет равно как раз $\dfrac1q$. Докажем по индукции, что это возможно. В виде суммы двух таких дробей 1 представить можно $\Big($например, $1=\dfrac34+\dfrac14\Big)$. Из представления 1 в виде суммы $n-1$ различных двоично-рациональных дробей можно получить её представление в виде суммы $n$ таких дробей:
$$
1=a_1+a_2+\ldots+a_{n-1}=\dfrac12+\dfrac{a_1}2+\dfrac{a_2}2+\ldots+\dfrac{a_{n-1}}2.
$$
В частности, следуя этому построению, получим
$$
\begin{gather*}
1=\dfrac34+\dfrac14=\dfrac12+\dfrac38+\dfrac18=\\
=\dfrac12+\dfrac14+\dfrac3{16}=\dfrac12+\dfrac14+\dfrac18+\dfrac3{32}+\dfrac1{32},
\end{gather*}
$$
что даёт представление числа $\dfrac15$.
Теперь к доказательству второго утверждения задачи можно идти многими разными путями. Приведём два из них.
1. Докажем, что если натуральное число $p$ можно представить в виде суммы $n-1$ различных правильных двоично-рациональных дробей:
$$
p=a_1+a_2+\ldots+a_{n-1}\quad(0\lt a_{n-1}\lt\ldots\lt a_2\lt a_1\lt1),
$$
то его можно представить и в виде суммы $n$ таких дробей. Пусть $2^m$ — наибольший из знаменателей слагаемых $a_i$. Заменив $a_{n-1}$ на сумму $\left(a_{n-1}-\dfrac1{2^{m+2}}\right)+\dfrac1{2^{m+2}}$, получим нужное представление. Итак, если каждая из дробей $\dfrac1q$, $\dfrac2q$, $\ldots$, $\dfrac{q-1}q$ может быть представлена в виде среднего арифметического различных правильных двоично-рациональных дробей, то и дроби $\dfrac1{q+1}$, $\dfrac2{q+1}$, $\ldots$, $\dfrac{q-1}{q+1}$ могут быть представлены в аналогичном виде. Чтобы закончить доказательство по индукции (база индукции — представление числа $\dfrac12\Big)$, осталось представить в нужном виде дробь $\dfrac q{q+1}$ заменой всех дробей $a_i$ на $1-a_i$.
2. Рассмотрим три уже полученных числа: 0, $\dfrac1q$, 1. Одно из двух средних $\dfrac{0+1}2$, $\dfrac{\dfrac1q+1}2$ — дробь вида $\dfrac{p_0}q$, $1\lt p_0\lt q$ (если $q\gt2$). Одно из двух средних $\dfrac{0+\dfrac{p_0}q}2$, $\dfrac{\dfrac1q+\dfrac{p_0}q}2$ — дробь $\dfrac{p_1}q$, где $1\lt p_1\lt p_0$ (если $q\gt3$). Ясно, что, продолжив этот процесс, мы получим дробь $\dfrac2q$. Рассмотрев затем тройку чисел $\dfrac1q$, $\dfrac2q$, $\dfrac{p_0}{q}$, мы таким же спуском получим дробь $\dfrac3q$, затем (если $q\gt4$) $\dfrac4q$, $\ldots$, $\dfrac{q-1}{q}$ и т. д. (рис. 2).
Рис. 2
Заметим, что среднее арифметическое более чем двух чисел нам надо находить лишь один раз.
