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

Степан Кузнецов
«Квант» №12, 2019

Многим, наверное, известно, что в Древнем Египте дробные числа записывали довольно своеобразным способом. Египтяне использовали только дроби с числителем \( 1 : \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, ... , \) такие дроби называются аликвотными, а также дроби \( \frac{2}{3} \) и \( \frac{3}{4} \). Остальные дроби представлялись в виде сумм упомянутых выше дробей; при этом египтяне следили, чтобы все дроби в сумме были различны.

Для чего же может быть полезно такое странное представление дробей? Рассмотрим следующую задачу: нужно разделить 5 лепешек поровну между 8 людьми. Ясно, что каждый должен получить \( \frac{5}{8} \) лепешки — можно разделить каждую лепешку на 8 равных частей и дать каждому по 5 таких частей. Египетская дробь, однако, дает более экономный способ разделения: поскольку \( \frac{5}{8} = \frac{1}{2} + \frac{1}{8} \), достаточно разделить 4 лепешки пополам (и каждому дать по половине), и только последнюю, 5-ю, лепешку делить на 8 частей.

Возникает естественный вопрос — а всякое ли рациональное число от 0 до 1, т.е. правильную дробь, можно представить таким образом. Этот вопрос нетривиален из-за требования различности дробей: нельзя просто разложить дробь \( \frac{k}{n} \) в сумму \( \underbrace{\frac{1}{n}+... + \frac{1}{n}}_{k\:\text{раз}}\).

Уже в древнеегипетском источнике — папирусе Ринда — мы находим таблицу разложений в суммы различных аликвотных дробей для чисел вида \( \frac{2}{n} \).

К счастью, в современных обозначениях не составляет труда решить задачу и в общем виде. Для этого воспользуемся следующим тождеством:

Применяя это тождество, мы будем раскладывать данную аликвотную дробь в сумму других аликвотных дробей, но уже с большими знаменателями. Тем самым мы будем избегать повторяющихся дробей в разложении. Например, упомянутая ранее задача из папируса Ринда в общем виде решается так:

Аналогично можно поступить и с произвольной дробью \( \frac{k}{n} \): сначала представить ее в виде суммы k одинаковых дробей \( \frac{1}{n} \), а потом, оставив первую из них в покое, начать «разгонять» остальные — заменить вторую на \( \frac{1}{n+1} + \frac{1}{n(n+1)} \), к третьей применять это же равенство до тех пор, пока все компоненты не станут больше \( \frac{1}{n(n+1)} \), и так далее.

Таким методом действительно можно разложить произвольное число в сумму различных аликвотных дробей, однако их количество и их знаменатели окажутся, в общем случае, астрономически велики. Фибоначчи предложил другой метод построения египетской дроби (суммы различных аликвотных дробей) для данной обыкновенной дроби \( \frac{k}{n} \), где k < n. Через ⌈n/k⌉ обозначается наименьшее целое число, не меньшее \( \frac{n}{k} \). (Поскольку \( \frac{n}{k}>1 \), это число не меньше 2.) Далее,

Первая дробь в этом разложении уже аликвотная, а ко второй дроби, если она окажется не аликвотной, мы опять применим ту же процедуру.

Поскольку ⌈n / k⌉ < n / k + 1, новый числитель k⌈n / k⌉ − n окажется меньше старого числителя k. Таким образом, наш процесс не может продолжаться бесконечно и остановится не более чем через k шагов. С другой стороны, несложная выкладка показывает, что знаменатели получаемых аликвотных дробей все время растут, а значит, все эти дроби различны.

Алгоритм Фибоначчи эффективнее показанного ранее метода, однако и он в некоторых случаях дает неоптимальные разложения. Например,

в то время как метод Фибоначчи даст разложение

Здесь эффективности алгоритма мешает его жадность: он всегда пытается вычленить из \( \frac{k}{n} \) наибольшую возможную аликвотную дробь, \(\frac{1}{⌈n / k⌉} \) — в нашем случае это \(\frac{1}{25} \), в то время как более скромное начало с \(\frac{1}{33} \) дает лучший результат.

Современные методы позволяют раскладывать дробь в сумму различных аликвотных довольно эффективно. Например, М. Воуз в 1985 году построил алгоритм, раскладывающий дробь \(\frac{k}{n} \) в сумму не более чем \( C \sqrt{log_2n} \) аликвотных (здесь C — константа, не зависящая от k и n).

С египетскими дробями связаны несколько открытых вопросов теории чисел. Так, гипотеза Эрдёша — Штрауса утверждает, что любая дробь с числителем 4 может быть разложена в сумму трех (!) аликвотных, независимо от значения знаменателя n. Эту гипотезу проверили на компьютере для значений n до 10¹⁴, однако доказательства для всех n пока не найдено.

В заключение расскажем еще об одном применении разложения дроби в сумму аликвотных — правда, не обязательно различных. Начнем с известной задачи: даны два бикфордовых шнура, каждый из которых горит ровно 1 минуту, но, возможно, неравномерно. Как с помощью этих шнуров отмерить полторы минуты? Поскольку \( \text{1,5} = 1 + \frac{1}{2}\), мы можем сначала отмерить минуту с помощью одного шнура, а затем поджечь второй шнур с двух сторон — тогда он сгорит за полминуты.

Эту конструкцию можно обобщить на произвольную аликвотную дробь: если мы будем поддерживать на шнуре одновременно n точек горения, то шнур сгорит за \( \frac{1}{n} \) минут. Например, подожжем шнур с краю и в середине. Средний огонек пойдет в обе стороны, т.е. раздвоится. Таким образом, один кусок шнура будет гореть с двух сторон, а другой — с одной. Если первый шнурок догорит раньше, то подожжем второй, опять же, изнутри. Иначе — погасим один из концов первого шнурка и подожжем его изнутри. Будем так действовать до тех пор, пока все шнурки не догорят, поддерживая в любой момент времени ровно 3 точки горения. Тогда шнур сгорит за \( \frac{1}{3} \) минуты.

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