Египетские дроби
Египетская дробь - в математике сумма нескольких попарно различных дробей вида 1/n (так называемых аликвотных дробей). Другими словами, каждая дробь суммы имеет числитель, равный единице, и знаменатель, представляющий собой натуральное число.
Египетская дробь представляет собой положительное рациональное число вида a/b. Можно показать, что каждое положительное рациональное число может быть представлено в виде египетской дроби (что мы ниже и сделаем).
История
Египетские дроби были изобретены и впервые использованы в Древнем Египте. У египтян не было дробей с числителем и знаменателем, как у нас. Были только часто используемые дроби, которые называют «натуральными». В Древнем Египте это дроби
для которых имелись специальные термины. Для дробей
есть специальные обозначения.
По мере того, как техника счета совершенствовалась, область дробей распространилась на основные (или аликвотные). Египтяне ставили иероглиф
над числом для обозначения такой дроби. (На картинке ниже -- дробь
)
Никаких других дробей, кроме этих, египтянин написать не мог.
Замечательно словесное выражение для
, которое буквально значит «две части». Дополнение «двух частей» до полной единицы называлось «третьей частью». Аналогично можно объяснить другие наши дроби (
).
В таком понимании пятая часть, например, представляет последнюю часть, которая вместе с четырьмя другими образует полную единицу. Говоря буквально, бессмысленно говорить о «двух пятых», так как имеется только одна пятая часть, а именно последняя.
Кроме того, дробную черту египтяне не воспринимали как деление. Да у них и слова «делить» не было.
То есть возникновение египетских дробей было обусловлено отсутствие соответствующего математического аппарата.
Одним из первых известных упоминаний о египетских дробях является Математический папирус Ринда.
А вот задача из этого знаменитого папируса: «Разделить 7 хлебов между 8 людьми». Решена задача у Ахмеса так: поскольку
, то каждому надо дать по половинке, четвертинке и восьмушке хлеба.
Египетские дроби продолжали использоваться в Древней Греции и впоследствии математиками всего мира до средних веков, несмотря на имеющиеся к ним замечания древних математиков. Важную работу по исследованию египетских дробей провёл математик XIII века Фибоначчи.
Способы разложения на египетские дроби
Жадный алгоритм, он же алгоритм Фибоначчи.
Алгоритм Фибоначчи осуществляет разложение
путём последовательного проведения замены:
Иначе говоря, на каждом шаге мы выбираем максимальную дробь вида
, не превосходящую
. А на следующем шаге переходим к дроби
.
Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. (И тем самым мы показали, что любую обыкновенную дробь можно разложить в египетскую). Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями.
Например, для
жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе аж 500 знаков!, тогда как существует гораздо более простое представление:
Другой метод представления обыкновенной дроби в виде египетской называется
Разрешение конфликтов
Пусть
. Положим
Когда несколько слагаемых в разложении совпадают, будем исправлять эту «неправильную» ситуацию. Каждый шаг алгоритма состоит в замене каких-то слагаемых другими. Будем рассматривать следующие разновидности этого метода.
Метод парных замен.
Например:
Метод подразбиения.
Если какое-либо слагаемое встречается больше одного раза, выполним одну замену,
Например:
Плюсы и минусы египетских дробей
В английской вики есть такой чудный пример: «Египетские дроби иногда легче позволяют сравнить размер дробей. Например, если некто хочет знать, больше ли
, чем
. Он может превратить их в египетские дроби:
;
»
Этот «легкий способ» напоминает шутку про Фейнмана, который ради какой-то задачи школьного курса просуммировал ряды в уме. Сравнивать в уме обычные дроби в их нормальной записи кажется гораздо проще, чем переводить их в египетский вид. Возможно, для египтян сравнения такого рода и были более удобны, так как наших дробей они не знали.
Вернемся к задаче про 7 хлебов и 8 человек. Если говорить как обычно, что всем надо выдать по
, нам придется каждую буханку хлеба разрезать на 8 частей и каждому дать по 7 частей из них. Если же мы представим
в виде
, то нужно 4 буханки разрезать пополам, 2 буханки разрезать на 4 части и только одну буханку разрезать на 8 частей. То есть каждому выдать не по 7 маленьких кусочков размером 1/7, а всего по три куска.
Как сказала Екатерина Георгиевна: «Меньше разрезов - это хорошо! Но еще и меньше кусков!»
Конечно, в современном мире мы не пользуемся египетскими дробями. Еще Фибоначчи показал, что по сравнению с обыкновенными дробями это неудобно.
Гипотезы
Ну, и напоследок об открытых, нерешенных проблемах. Вдруг, кто-нибудь докажет на досуге :)
Гипотеза Эрдёша - Штрауса утверждает, что для всякого целого числа n ≥ 2, существуют положительные целые x, y и z, при которых
Компьютерные эксперименты показывают, что гипотеза верна для всех n ≤ 1014, но доказательство пока не найдено.
Обобщение этой гипотезы, предложенное Анджеем Шинцелем, утверждает, что для всякого положительного k существует N, при котором для всех n ≥ N существует разложение
Иначе говоря, разложение в египетские дроби всегда можно придумать не слишком-то длинное!
Специально для жж матфака Евгения Федотова.
Египетская дробь представляет собой положительное рациональное число вида a/b. Можно показать, что каждое положительное рациональное число может быть представлено в виде египетской дроби (что мы ниже и сделаем).
История
Египетские дроби были изобретены и впервые использованы в Древнем Египте. У египтян не было дробей с числителем и знаменателем, как у нас. Были только часто используемые дроби, которые называют «натуральными». В Древнем Египте это дроби
для которых имелись специальные термины. Для дробей
есть специальные обозначения.
По мере того, как техника счета совершенствовалась, область дробей распространилась на основные (или аликвотные). Египтяне ставили иероглиф
над числом для обозначения такой дроби. (На картинке ниже -- дробь
)
Никаких других дробей, кроме этих, египтянин написать не мог.
Замечательно словесное выражение для
, которое буквально значит «две части». Дополнение «двух частей» до полной единицы называлось «третьей частью». Аналогично можно объяснить другие наши дроби (
).
В таком понимании пятая часть, например, представляет последнюю часть, которая вместе с четырьмя другими образует полную единицу. Говоря буквально, бессмысленно говорить о «двух пятых», так как имеется только одна пятая часть, а именно последняя.
Кроме того, дробную черту египтяне не воспринимали как деление. Да у них и слова «делить» не было.
То есть возникновение египетских дробей было обусловлено отсутствие соответствующего математического аппарата.
Одним из первых известных упоминаний о египетских дробях является Математический папирус Ринда.
А вот задача из этого знаменитого папируса: «Разделить 7 хлебов между 8 людьми». Решена задача у Ахмеса так: поскольку
, то каждому надо дать по половинке, четвертинке и восьмушке хлеба.
Египетские дроби продолжали использоваться в Древней Греции и впоследствии математиками всего мира до средних веков, несмотря на имеющиеся к ним замечания древних математиков. Важную работу по исследованию египетских дробей провёл математик XIII века Фибоначчи.
Способы разложения на египетские дроби
Жадный алгоритм, он же алгоритм Фибоначчи.
Алгоритм Фибоначчи осуществляет разложение
путём последовательного проведения замены:
Иначе говоря, на каждом шаге мы выбираем максимальную дробь вида
, не превосходящую
. А на следующем шаге переходим к дроби
.
Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. (И тем самым мы показали, что любую обыкновенную дробь можно разложить в египетскую). Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями.
Например, для
жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе аж 500 знаков!, тогда как существует гораздо более простое представление:
Другой метод представления обыкновенной дроби в виде египетской называется
Разрешение конфликтов
Пусть
. Положим
Когда несколько слагаемых в разложении совпадают, будем исправлять эту «неправильную» ситуацию. Каждый шаг алгоритма состоит в замене каких-то слагаемых другими. Будем рассматривать следующие разновидности этого метода.
Метод парных замен.
Например:
Метод подразбиения.
Если какое-либо слагаемое встречается больше одного раза, выполним одну замену,
Например:
Плюсы и минусы египетских дробей
В английской вики есть такой чудный пример: «Египетские дроби иногда легче позволяют сравнить размер дробей. Например, если некто хочет знать, больше ли
, чем
. Он может превратить их в египетские дроби:
;
»
Этот «легкий способ» напоминает шутку про Фейнмана, который ради какой-то задачи школьного курса просуммировал ряды в уме. Сравнивать в уме обычные дроби в их нормальной записи кажется гораздо проще, чем переводить их в египетский вид. Возможно, для египтян сравнения такого рода и были более удобны, так как наших дробей они не знали.
Вернемся к задаче про 7 хлебов и 8 человек. Если говорить как обычно, что всем надо выдать по
, нам придется каждую буханку хлеба разрезать на 8 частей и каждому дать по 7 частей из них. Если же мы представим
в виде
, то нужно 4 буханки разрезать пополам, 2 буханки разрезать на 4 части и только одну буханку разрезать на 8 частей. То есть каждому выдать не по 7 маленьких кусочков размером 1/7, а всего по три куска.
Как сказала Екатерина Георгиевна: «Меньше разрезов - это хорошо! Но еще и меньше кусков!»
Конечно, в современном мире мы не пользуемся египетскими дробями. Еще Фибоначчи показал, что по сравнению с обыкновенными дробями это неудобно.
Гипотезы
Ну, и напоследок об открытых, нерешенных проблемах. Вдруг, кто-нибудь докажет на досуге :)
Гипотеза Эрдёша - Штрауса утверждает, что для всякого целого числа n ≥ 2, существуют положительные целые x, y и z, при которых
Компьютерные эксперименты показывают, что гипотеза верна для всех n ≤ 1014, но доказательство пока не найдено.
Обобщение этой гипотезы, предложенное Анджеем Шинцелем, утверждает, что для всякого положительного k существует N, при котором для всех n ≥ N существует разложение
Иначе говоря, разложение в египетские дроби всегда можно придумать не слишком-то длинное!
Специально для жж матфака Евгения Федотова.