Олимпиадная задача о натуральных числах Н и a для Глеба

Рассмотрим число $N$ и последовательность, которую Глеб мог выписать на доску. Исходное число $a$ обозначим через $a_{1}$, а все последующие через $a_{2}$, $a_{3}, \ldots, a_{n}$. Из условия имеем $N = a_{k} q_{k} + a_{k+1}$ при $1 \leq k \leq n - 1$, а также $N = a_{n} q_{n}$, где через $q_{k}$ обозначены неполные частные от делений.

Мы хотим добиться выполнения неравенства $$\frac{a_{1}}{N} + \frac{a_{2}}{N} + \ldots + \frac{a_{n}}{N} > 100.$$

Как нетрудно видеть, $N < a_{k} (q_{k} + 1)$, откуда $a_{k} / N > 1 / (q_{k} + 1)$; кроме того, $a_{n} / N = 1 / q_{n}$. Следовательно, достаточно добиться выполнения неравенства $$ \frac{1}{q_{1} + 1} + \frac{1}{q_{2} + 1}

• \ldots + \frac{1}{q_{n-1} + 1} + \frac{1}{q_{n}}

100.$$

Покажем, что существуют такие изначальные числа $N$ и $a$, что при всех $k < n$ выполнено $q_{k} = k$ и $q_{n} = n + 1$. Если это удастся, то задача будет решена, так как неравенство $$ \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} + \frac{1}{n + 1}

100, как известно, верно при достаточно больших $n$ (см. комментарий 1 в конце решения). Итак, мы выбрали неполные частные, осталось найти подходящие $N$ и $a_{k}$. Заметим, что равенство (реккурентная формула) a_{k} = \frac{N - a_{k+1}}{k}, $$ дополненное неравенством $a_{k} > a_{k+1}$, эквивалентно тому, что $a_{k+1}$ является остатком от деления $N$ на $a_{k}$ с неполным частным $k$.

Сначала выберем $a_{n} = 1$ и $N = n + 1$. Далее определим все $a_{k}$ по указанной выше реккурентной формуле, начиная с конца. Часть из полученных чисел, возможно, окажутся рациональными; однако, как легко видеть, если $N$ и все $a_{k}$ домножить на произвольное число, реккурентные равенства сохранятся, как и условие последнего деления $N = (n + 1) a_{n}$. Просто домножим $N$ и все $a_{k}$ на их общий знаменатель, и они станут целыми. Осталось убедиться, что все $a_{k}$ положительны и что $a_{k} > a_{k+1}$.

Для этого сначала докажем индукцией по $k$, что $0 < a_{k} < N / k$. База $k = n$ очевидна, так как $a_{n} = N / (n + 1)$. Пусть мы доказали для $k + 1$, докажем для $k$. Так как $0 < a_{k+1} < N / k$, то $0 < N - a_{k+1} < N$, а заменяя $N - a_{k+1}$ на $k a_{k}$ согласно реккурентной формуле, получаем искомое $0 < a_{k} < N / k$.

Осталось заметить, что при $k < n$ $$a_{k} = \frac{N - a_{k+1}}{k} > \frac{N - \dfrac{N}{k+1\vphantom)}}{k} = \frac{N}{k+1} > a_{k+1}.$$

Это завершает доказательство того, что полученная последовательность $a_{k}$ искомая.

Комментарии.

Докажем, что для любого натурального $d$ можно выбрать несколько первых членов последовательности $\frac{1}{2} + \frac{1}{3} + \ldots$, чтобы их сумма была больше $d$. Например, можно взять первые $2^{2d} - 1$ чисел. Действительно, их можно разбить на $2d$ частей: в первой части число $\frac{1}{2}$, во второй — числа $\frac{1}{3}$ и $\frac{1}{4}$, в третьей — от $\frac{1}{5}$ до $\frac{1}{8}$ и т.д., то есть в $m$-й части числа от $\frac{1}{2^{m-1}+1}$ до $\frac{1}{2^m}$. Тогда для каждого $m$ от $1$ до $2 d$ в $m$-ю часть попадут $2^{m-1}$ чисел, и их сумма будет не менее $\frac{1}{2^m} \cdot 2^{m-1} = \frac{1}{2}$, поэтому сумма всех чисел окажется не менее $d$.

Нетрудно видеть, что неполные частные $q_{k}$ возрастают с ростом $k$, так как соотношение $a_{k} q_{k} + a_{k+1} = N = a_{k+1} q_{k+1} + a_{k+2}$ не может выполняться при $a_{k} > a_{k+1} > a_{k+2}$ и $q_{k} \geq q_{k+1}$. Аналогично можно показать, что самое последнее частное хотя бы на $2$ больше предпоследнего. Отсюда ясно, что используемая выше последовательность $q_{k}$ в некотором смысле «минимальна».

Можно показать, что в качестве общего знаменателя, на который мы домножали полученные в решении числа $a_{k}$, чтобы они стали целыми, можно было взять $n!$. Тогда нетрудно вычислить $N = (n + 1)!$ и $$a_{k} = (n + 1)! (k - 1)! \Bigl( \frac{1}{k!} - \frac{1}{(k+1)!} + \frac{1}{(k+2)!} - \ldots +\frac{(-1)^{n-k+1}}{(n+1)!} \Bigr) .$$