Египетские дроби
Одним из древнейших письменных документов человечества яв­ляется папирус Райнда, датируемый ориентировочно 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 при достаточно больших n  a _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 в