Египетские дроби

Египетские дроби

Одним из древнейших письменных документов человечества является папирус Райнда, датируемый ориентировочно 1600 г. до н.э. Замечательно, что это также древнейшее математическое сочинение. Древние египтяне записывали рациональные дроби как суммы чисел, обратных натуральным: 2/5 = 1/3 + 1/15, 6 / 7 = 1/2 + 1/3 + 1/42 и т. д. Папирус содержит математические задачи и таблицы, представляющие дроби 2/(2п+ 1), со знаменателями от 5 до 331 в виде суммы дробей с числителем 1.

Дроби с числителем единица мы будем называть египетскими дробями, а разложение рационального числа в сумму попарно различных египетских дробей — египетской суммой. Мы будем рассматривать только положительные рациональные числа.

1.1. а) Для каких натуральных N единицу можно представить в виде египетской суммы из N слагаемых?

б) Существуют ли египетские разложения единицы, в которых все знаменатели нечетны?

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

6} Докажите, что если т < п ² , то существует египетское разложение дроби т / п, в котором не более 2 ^m - 1 слагаемых.

в) Докажите, что всякую дробь т/п < 1 можно разложить в сумму не более min(m, log₂тп ) различных египетских дробей.

г) Докажите, что всякую дробь т/п < 1 можно разложить в сумму различных египетских дробей со знаменателями, не превосходящими п ².

1.3. Докажите, что при каждом sуравнение

в натуральных числах имеет лишь конечное множество решений.

1.4. а) Докажите, что для любого натурального п на интервале (0,1) существует рациональное число, не представимое в виде египетской суммы с не более, чем п слагаемыми.

б) Пусть М _n— множество рациональных чисел из интервала (0,1), представимых в виде суммы не более чем nегипетских дробей (не обязательно различных). Докажите, что при любом n множество М _п нигде не плотно.

Другими словами, для любого n и любого промежутка (a,b)Ì (0,1) найдется такой интервал (с,d) Ì (а,b), в котором все рациональные числа не представимы в виде суммы не более nегипетских дробей.

1.5. а) Может ли сумма нескольких последовательных египетских дробей (знаменатели которых являются последовательными натуральными числами) быть целым числом?

б) Тот же вопрос, но знаменатели должны являться последовательными нечетными натуральными числами.

в) Тот же вопрос, но знаменатели должны образовывать произвольную арифметическую прогрессию.

г) Докажите, что равенство

возможно лишь при a = n + 1, m =1

1.6. Пусть f_n— числа Фибоначчи. Докажите, что при всех т, п

1.7. Верно ли, что для каждой правильной дроби вида

, 2 £n£18 существует египетское разложение со знаменателями не превосходящими 95?

Малые числители

1.8. Найдите египетское разложение

сумму наименьшего числа слагаемых.

1.9. Докажите, что представление числа

, где n не делится на 3, в виде суммы двух египетских дробей возможно в том и только том случае, когда n имеет делитель вида Зn + 2.

1.10. Пусть а _n - число элементов множества

Докажите, что для каждого e > 0 при достаточно больших na_n< n^e.

Открытая проблема (Erdos, Straus). Уравнение

(1)

при n > 3 разрешимо в натуральных числах. Вычислительный эксперимент для n < 10⁸ подтверждает эту гипотезу.

1.11. Докажите, что уравнение (1) разрешимо при всех n, кроме, быть может, n = 1,121,169,289, 361,529 (mod 840).

1.12. Докажите, что число 1 нельзя, а число 1/2 можно представить в виде египетской суммы со знаменателями, являющимися точными квадратами.

Способы разложения на египетские дроби

В этом разделе мы рассматриваем различные способы получить представление рационального числа

в виде египетской суммы.

Определение 1. Жадный алгоритм. Выберем наибольшую дробь вида

, которая не превосходит . Потом возьмем наибольшую дробь вида , n ₂ > n ₁ для которой . Потом возьмем наибольшую дробь вида , n ₃ > n ₂ , для которой

и т.д.

Если на каждом шаге мы выбираем нечетные n i , то полученный метод будем называть нечетным жадным алгоритмом.

Определение 2. Разрешение конфликтов. Пусть

< 1. Положим

Когда несколько слагаемых в разложении совпадают, будем исправлять эту "неправильную" ситуацию. Каждый шаг алгоритма состоит в замене каких-то слагаемых другими. Будем рассматривать следующие разновидности этого метода.

• Метод парных замен.

• Метод подразбиения. Если какое-либо слагаемое встречается больше одного раза, выполним одну замену,

Определение 3. Метод двоичного разложения. Пусть

< 1. Разложим число в бесконечную двоичную дробь. Она будет смешанной периодической. Пусть период имеет длину n. Можно считать, что начальная непериодическая часть имеет длину больше n. Каждой единице, предшествующей первому периоду, соответствует дробь вида . Каждой единице из периода соответствует египетская дробь .

Аналогичный метод работает и в системах с другими основаниями, например, в шестиричной. Проблемы

и решаются просто: , . В десятичной системе счисления этот метод непосредственно на работает, поскольку не удается представить числа 4, 7, 8, 9 в виде суммы различных делителей числа 10. Назовем число N практичным, если все натуральные числа, не превосходящие N (в случае нечетного N — все кроме 2), можно представить в виде суммы нескольких (быть может, одного) различных делителей числа N. Пример четного практичного числа — 6, пример нечетного практичного числа — 945. Благодаря разложению из задачи 1.8, мы можем с минимальными изменениями распространить метод двоичного разложения на случай, когда основание системы счисления — практичное число.

Определение 4 Метод двоичного остатка. Для разложения числа а / b, ( b¹ 2ⁿ) в египетскую сумму выберем число p = 2 ^k > b. Разделим аp на b с остатком: ар = sb + г. Разложим r/p, s/p в