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

[bot]

Неплохая олимпиадная задача - сегодня встретил. Авторскую формулировку исправляю, убрав несущественное ограничение (у него дробь правильная):

Доказать, что любую дробь $\frac{p}{q}$ (p и q - натуральные числа) можно представить в виде конечной суммы различных членов гармонического ряда.

[Capella]

Вопрос: можно ли считать такое равенство$ \frac {p} {q} = \frac {np} {nq} $ одним числом, для нахождения которого необходимо получить лишь правую или левую часть?

Подправила формулу

[bot]

Снимаю свою непонятку в связи с исправлением предыдущего поста.

[Capella]

Имелось ввиду, можно ли, например $ \frac {2} {50} $ приравнять вот этому члену гармонического ряда $ \frac {1} {25} $?

[bot]

Ну разумеется.

[RIP]

Недорешение в 1 строчку:
у числа p/q-1/n, где n=[q/p], числитель меньше p(считаем p<q).

[незваный гость]

В одну строчку, боюсь, не получиться, если дробь неправильная (id est, $p > q$).

Кроме того, Вы, вероятно имели в виду либо $[\frac{p}{q}]+1$, ($\lceil\frac{p}{q}\rceil$).

[Genrih]

незванный гость писал(а):

В одну строчку, боюсь, не получиться, если дробь неправильная (id est, $p > q$).

Так ведь если неправильная ($p > q$) так ... $\frac{p}{q}=\frac{q+(p-q)}{q} = 1+ \frac{p-q}{q}$ и ищем члены гармонического ряда для второго слагаемого как показано выше

[Dan_Te]

А если $\frac{p-q}{q}$ тоже неправильная? Тогда у нас еще единицы повылезут, что с ними делать?

[незваный гость]

Genrih писал(а):

Так ведь если неправильная ($p > q$) так ... $\frac{p}{q}=\frac{q+(p-q)}{q} = 1+ \frac{p-q}{q}$ и ищем члены гармонического ряда для второго слагаемого как показано выше

Интересное наблюдение (простите иронию). Как, например, насчет 8/3?

Я полагаю, что мы можем всегда загнать $\frac{p}{q}$ в переделы от нуля до единицы за конечное число первых членов гармонического ряда. Но тонкость здесь в том, что потом в предложенном процессе могут возникнуть проблемы, а именно, хочется взять член, а он уже использован.

Похоже, правильной стратегией будет вычитать из дроби члены ряда, пока разность будет положительной. Если она стала равной нулю - то все в порядке. А если нет - применяем к последней неотрицательной разности построение RIP.

Чуть более формально, пусть $f(k)=\frac{p}{q}-\sum\limits_{j=1}^{k}\frac{1}{j}$. Тогда $K=\max\{k: f(k)>0\}$. Далее либо $f(K+1) = 0$, либо $\lceil \frac{1}{f(K)} \rceil > K+1$, что дает возможность следовать идее RIP. Недосказанная хитрость RIP состоит не только в том, что числитель уменьшается, но и в том, что выбираемые члены убывают (а это весьма существенно, чтобы не повториться).

[Genrih]

незванный гость писал(а):

Интересное наблюдение (простите иронию). Как, например, насчет 8/3?

Да! Вы правы Dan_Te , незванный гость.
Не сообразил добавить, что к примеру (ироническому)):от 8/3 можно отделить целую часть (2) и "приблизиться" к ней суммой $\sum\limits_{j=1}^{N}\frac{1}{j}$ (до какого-то N), а остаток получить с помощью идеи RIP...
хотя ничего нового я так и не сказал...
Но спасибо !

[незваный гость]

Genrih писал(а):

незванный гость писал(а):

Интересное наблюдение (простите иронию). Как, например, насчет 8/3?

Да! Вы правы Dan_Te , незванный гость.
Не сообразил добавить, что к примеру (ироническому)):от 8/3 можно отделить целую часть (2) и "приблизиться" к ней суммой $\sum\limits_{j=1}^{N}\frac{1}{j}$ (до какого-то N), а остаток получить с помощью идеи RIP...

Тут не так просто - 2 не есть член гармонического ряда. А если Вы за просто так разделили дробь на две части, то надо доказывать, что члены использованные в их представлении будут разными.

[evgeny]

Это вопрос врядли можно считать олимпиадным. Судя по данным с
http://mathworld.wolfram.com/EgyptianFraction.html
одно из решений было опубликовано в 1202 году
там же есть ссылки на несколько алгоритмов разложения
(предложенный здесь алгоритм называется greedy algorithm)

[Genrih]

незванный гость писал(а):

Тут не так просто - 2 не есть член гармонического ряда. А если Вы за просто так разделили дробь на две части, то надо доказывать, что члены использованные в их представлении будут разными.

2 не есть.


$K=\max\{k:f(k)>0\}$ , a значит $\frac{p}{q}-\sum\limits_{j=1}^{k}\frac{1}{j}<\frac{1}{k+1}$ и получаем что остаток(для которого будем искать представление)меньше даже k+1 первых (использовали уже первые k членов ряда) и все члены будут разные. Если же конечно $f(K+1)$ не нуль

еvgeny, спасибо за ссылки!

[bot]

Прошу прощения, что ввёл в заблуждение. Я ещё вчера обнаружил косячок в моём "олимпиадном" решении. Оно, конечно, было гораздо проще, чем первоначальное для правильных дробей, но,увы, ...
Собственно считал совсем простым фактом и вроде получилось, что для любого N существует разложение единицы в сумму египетских дробей со знаменателями, большими N. Повозился вчера, думая что легко и просто залатаю, ан не так это просто.