Єгипетські дроби
Багатьом, напевно, відомо, що в Стародавньому Єгипті дробові числа записували досить своєрідним способом. Єгиптяни використовували лише дроби з числівником( 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{1}{n} = frac{1}{n+1} + frac{1}{n(n+1)}.)
Застосовуючи це тотожність, ми будемо розкладати цей аліквотний дріб у суму інших аліквотних дробів, але вже з великими знаменниками. Тим самим ми будемо уникати повторюваних дробів у розкладанні. Наприклад, згадане раніше завдання з папірусу Рінда в загальному вигляді вирішується так:
( frac{2}{n} = frac{1}{n} + frac{1}{n} = frac{1}{n} + frac{1}{n+1} + frac{1}{n(n+1)}.)
Подібно ви можете вчинити і з довільним дробом(frac {k} {n}): спочатку представити її у вигляді суми k однакових дробів(frac {1} {n}), а потім, залишивши першу з них у спокої, почати «розганяти» інші — замінити другу на(frac {1} {n + 1} +frac {1} {n (n + 1)}), до третьої застосовувати цю ж рівність до тих пір, поки всі компоненти не стануть більше( n\frac
Таким методом дійсно можна розкласти довільне число в суму різних аліквотних дробів, проте їх кількість і їх знаменники виявляться, в загальному випадку, астрономічно великі. Фібоначчі запропонував інший метод побудови єгипетського дробу (суми різних аліквотних дробів) для цього звичайного дробу(frac {k} {n}), де k . За допомогою n/k — це найменша ціла кількість, не менша за(frac {n} {k}). (Оскільки(frac {n} {k} > 1), це число не менше 2.) Далі,
( frac{k}{n} = frac{1}{⌈n / k⌉} + frac{k⌈n / k⌉-n}{n⌈n / k⌉}.)
Перший дріб у цьому розкладанні вже аліквотний, а до другого дробу, якщо він виявиться не аліквотним, ми знову застосуємо ту ж процедуру.
Оскільки n/k ^ n/k + 1, новий числник k. n/k — n виявиться меншим за старий числитель k. Таким чином, наш процес не може тривати нескінченно і зупиниться не більше ніж через k кроків. З іншого боку, нескладна викладка показує, що знаменники одержуваних аліквотних дробів весь час ростуть, а значить, всі ці дроби різні.
Алгоритм Фібоначчі ефективніший за показаний раніше метод, однак і він у деяких випадках дає неоптимальні розкладання. Наприклад,
( frac{5}{121} = frac{1}{33} + frac{1}{121} + frac{1}{363}, )
тоді як метод Фібоначчі дасть розкладання
( frac{5}{121} = frac{1}{25} + frac{1}{757} + frac{1}{763309} + frac{1}{873960180193}+ frac{1}{1527612795642093418846225}. )
Тут ефективності алгоритму заважає його жадібність: він завжди намагається вичленувати з(frac {k} {n}) найбільший можливий аліквотний дріб ,(frac {1} {^ n/k ^}) — у нашому випадку це(frac {1} {25}), тоді як більш скромний початок з(frac {1} {33}) дає кращий результат.
Сучасні методи дозволяють розкладати дріб у суму різних аліквотних досить ефективно. Наприклад, М. Воуз в 1985 році побудував алгоритм, який розкладає дріб(frac {k} {n}) в суму не більше ніж( Csqrt {log _ 2n}) аліквотних (тут C — константа, не залежна від k і n).
З єгипетськими дробами пов’язані кілька відкритих питань теорії чисел. Так, гіпотеза Ердешу — Штрауса стверджує, що будь-який дріб з числівником 4 може бути розкладено в суму трьох (!) аліквотних, незалежно від значення знаменника n. Цю гіпотезу перевірили на комп’ютері для значень n до 1014, проте докази для всіх n поки не знайдено.
Насамкінець розповімо ще про одне застосування розкладання дробу в суму аліквотних — щоправда, не обов’язково різних. Почнемо з відомого завдання: дані два бікфордових шнури, кожен з яких горить рівно 1 хвилину, але, можливо, нерівномірно. Як за допомогою цих шнурів відміряти півтори хвилини? Оскільки(text {1,5} = 1 +frac {1} {2}), ми можемо спочатку відміряти хвилину за допомогою одного шнура, а потім підпалити другий шнур з двох сторін — тоді він згорить за півхвилини.
Цю конструкцію можна узагальнити на довільний аліквотний дріб: якщо ми будемо підтримувати на шнурі одночасно n точок горіння, то шнур згорить за(frac {1} {n}) хвилин. Наприклад, підпалимо шнур з краю і в середині. Середній вогник піде в обидва боки, тобто роздвоїться. Таким чином, один шнур горітиме з двох боків, а інший — з одного. Якщо перший шнурок наздожене раніше, то підпалимо другий, знову ж таки, зсередини. Інакше — погасимо один з кінців першого шнурка і підпалимо його зсередини. Будемо так діяти до тих пір, поки всі шнурки не догорять, підтримуючи в будь-який момент часу рівно 3 точки горіння. Тоді шнур згорить за(frac {1} {3}) хвилини.
Довільний же дріб можна розкласти в суму аліквотних — таким чином, ми навчилися відміряти довільний час, виражений в хвилинах раціональним числом. При цьому чим менше аліквотних дробів в сумі, тим менше шнурів нам буде потрібно.
- Попередня
- Наступна