Выборочные суммы гармонического ряда.

[bot]

Да нет - всё просто. Искомое разложение единицы со знаменателями, большими N:
$1 = \frac{1}{N+1} + \frac{1}{N+2} + ... +\frac{1}{K} +R$, где $R<\frac{1}{K-1}$ и следовательно $R=\frac{1}{K}r$ с правильной дробью r, которую мы раскладывать умеем.
А теперь достаточно записать p/q в виде p одинаковых дробей и "развести" знаменатели.

Первоначально так и было - вместе с коллегой проверили, после чего и запостил. А потом увидал совсем простенькое "решение", доступное 5-класснику, в котором спустя пару часов косячок обнаружил. Ох не сразу вернулся в прежнее русло, да и не без посторонней помощи.

Однако всё же потянет на олимпиадную?

[Егор]

На олимпиадную, конечно, потянет (правда, хорошо известна в узких кругах).

Гашков и Чубариков в книге "Арифметика..." отвели на эту задачу весь второй параграф. Помимо прочего, там два алгоритма разложения правильной дроби, жутковатый алгоритм разложения произвольной дроби и замечание, что в книге Тригга "Задачи с изюминкой" было приведено некорректное доказательство.

[bot]

Хм, а зачем целый параграф? К сожалению в инете книжку не нашёл - там только заказать можно. Неужто у них сложнее?
Представление правильной дроби $\frac{p}{q}=\frac{p_0}{q_0} легко получить, например, через линейные представления единицы $1 = p_i q_{i+1} - q_i p_{i+1} \ (p_{i+1}<p_i, q_{i+1}<q_i$):

$\frac{p_0}{q_0}=\frac{p_0q_1}{q_0q_1}=\frac{1+q_0p_1}{q_0q_1}=\frac{1}{q_0q_1}+\frac{p_1}{q_1} = \frac{1}{q_0q_1} + \frac{1}{q_1q_2} + ... $,

а представление целого числа через сумму "далёких" членов ряда описано выше. Мой "коронный" ход через сумму одинаковых дробей $1/q$, понятно смысла не имеет, так как сам содержит разложение правильной дроби. Это просто отголоски тех глюков, которые у меня возникли после того, как я соблазнился лёгким 5-классным решением, основанном на равенстве $1 = \frac{1}{2}+\frac{1}{3}+\frac{1}{6}$, а потом обнаружил, что оно несостоятельно. С чего то я взял, что та же самая ошибка у меня была и в первоначальном. Освободился от этого глюка не без постороннего вмешательства.

[Егор]

Доказательство из книги Гашкова и Чубарикова построено на формуле

$$1=\sum_{k=1}^n\sum_{a_1,\ldots,a_k=0,1}\frac{1}{P_{a_k}(\ldots P_{a_1}(n)\ldots)}.$$

Все слагаемые различны. Здесь $P_0(x)=x+1$, $P_1(x)=x(x+1)$.

Полагая большие n, можно "раздвинуть" слагаемые.

См. также личное сообщение.