Представление рациональных чисел в виде суммы простых дробей

[skobar]

Навеяно вызвавшей бурную реакцию темой о дробях :), в частности постом мат-ламер-а:

мат-ламер в сообщении #1671438 писал(а):

В учебнике Винберга приведён содержательный пример теории дробей - разложение на простейшие дроби. Обычно в учебниках анализа этот вопрос рассмотрен упрощённо. Винберг доказывает, что это разложение существует и единственно.

К разложению из Винберга следующая задачка никакого отношения не имеет, и единственности никакой не будет. Но тем не менее хорошая развлекательная задачка продвинутого школьного уровня. Предлагалась на американском Putnam Mathematical Competition в 1954 году:

$\textit{Доказать, что любое положительное рациональное число} \ \ r \ \textit{можно представить в виде суммы}$

$$r=\sum_{i=1}^{k} \frac{1}{n_i} \ \ \textit{, где} \ \ n_1, n_2, \dots, n_k - \textit{различные натуральные числа}$$

[Edward_Tur]

Жадный алгоритм для египетских дробей

[skobar]

Edward_Tur в сообщении #1671478 писал(а):

Жадный алгоритм для египетских дробей

Да, именно решение основанное на жадном алгоритме и предполагалось (индукцией по числителю дроби). При этом не предполагалось, что школьники/студенты знакомы с темой и жадным алгоритмом заранее.

[juna]

skobar в сообщении #1671473 писал(а):

$\textit{Доказать, что любое положительное рациональное число} \ \ r \ \textit{можно представить в виде суммы}$

$$r=\sum_{i=1}^{k} \frac{1}{n_i} \ \ \textit{, где} \ \ n_1, n_2, \dots, n_k - \textit{различные натуральные числа}$$

Только нужно заметить, что $0<r<1$.

Интересно, кстати, существует ли что-то типа жадного алгоритма для представления

$$r=\sum_{i=0}^k\frac{(-1)^i}{n_i}, 0<r<1, \forall i: n_i\in \mathbb{N}$$

Например, абы какой способ дает:

$$\frac{4}{13}=\frac{1}{4}-\frac{1}{18}+\frac{1}{9}-\frac{1}{468}+\frac{1}{234}$$

но хотелось бы, чтобы знаменатели последовательно нарастали, например, как вот здесь

$$\sqrt{10}-3=\frac{1}{6}-\frac{1}{222}+\frac{1}{8436}-\frac{1}{320340}+\ldots$$

[waxtep]

juna в сообщении #1672704 писал(а):

Только нужно заметить, что $0<r<1$.

Почему? Можно же сначала взять достаточно большой кусок гармонического ряда, чтоб покрыть целую часть

[juna]

waxtep в сообщении #1672715 писал(а):

juna в сообщении #1672704 писал(а):

Только нужно заметить, что $0<r<1$.

Почему? Можно же сначала взять достаточно большой кусок гармонического ряда, чтоб покрыть целую часть

Да, Вы правы. Я имел ввиду условие применения жадного алгоритма.

[skobar]

Утверждение верно для всех положительных рациональных чисел. Конечно, предполагалось, что при помощи жадного алгоритма утверждение сначала будет доказано для $r<1$ (содержательная часть), и затем отсюда будет распространено на все положительные рациональные числа (легкая, почти очевидная часть).

[juna]

Не совсем очевидно, в условии есть требование различных $n_i$, гармонический ряд поэтому не подойдёт, а что если вы эти члены уже использовали, а они требуются жадному алгоритму для разложения остатка.

[waxtep]

juna в сообщении #1672740 писал(а):

Не совсем очевидно, в условии есть требование различных $n_i$, гармонический ряд поэтому не подойдёт, а что если вы эти члены уже использовали, а они требуются жадному алгоритму для разложения остатка.

По-моему, гармонический ряд подойдет всегда, можно с самого начала идти жадно. И всегда же можно применить трюк типа $\dfrac1{k}=\dfrac1{k+1}+\dfrac1{k(k+1)}$, например

$$\frac43=\frac12+\frac13+\frac14+\frac14=\frac12+\frac13+\frac14+\frac15+\frac1{20}$$

[skobar]

juna в сообщении #1672740 писал(а):

Не совсем очевидно, в условии есть требование различных $n_i$, гармонический ряд поэтому не подойдёт, а что если вы эти члены уже использовали, а они требуются жадному алгоритму для разложения остатка.

Ну это совсем просто. Пусть утверждение уже доказано для $0<r<1$. Возьмем любое рациональное $r \geq 1$. Обозначим через $S_n \ n$-ую частичную сумму гармонического ряда:

$$ S_n= \sum_{k=1}^{n} 1/k$$

Найдется $l \in \mathbb{N}$ такое, что

$$ S_l \leq r <S_{l+1}$$

Тогда $r-S_l$ - рациональное число, меньшее $\frac{1}{l+1}$, и, значит, может быть записано в виде египетской дроби. Т.к. $r-S_l <\frac{1}{l+1}$, все знаменатели в разложении будут строго больше, чем $l$, и одинаковых знаменателей в разложении $r=S_l + (r-S_l)$ не будет.

[juna]

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