Wersja z 2015-09-12
Ułamkami egipskimi nazywamy odwrotności liczb naturalnych większych od 1. Zapisujemy je w postaci potęgowej: `2^(-1)`, `3^(-1)`, `4^(-1)`, `5^(-1)`, `6^(-1)`, …, albo też w postaci tradycyjnej: `1/2`, `1/3`, `1/4`, `1/5`, `1/6`, …, czyli jako ułamki zwykłe o liczniku równym 1 (i taki zapis dominuje w opracowaniach poświęconym tym ciekawym liczbom).
Niekiedy ułamki egipskie nazywa się ułamkami prostymi, ale nazwa ta jest myląca, ponieważ zwykle odnosi się ona do pewnego typu algebraicznych wyrażeń wymiernych, które z ułamkami egipskimi nie mają wiele wspólnego. Dlatego też tej wieloznacznej nazwy nie będziemy tu używać.
Warto nadmienić, że niektóre źródła, w tym Wikipedia, za ułamek egipski uważa… sumę ułamków o liczniku 1! O wyjątkowej absurdalności pomysłu na definicję, w której sumę nazywa się ułamkiem, nie trzeba chyba nikogo przekonywać. Ten idiotyzm definicyjny powstał w wyniku pomylenia pojęć „ułamek egipski” i „rozkład na ułamki egipskie”. W tym artykule nie będziemy jednak zajmować się dyskusją z idiotyzmami, bo byłoby to stratą czasu.
Odwrotności liczb naturalnych (większych od 1) były głównym typem ułamków znanych starożytnym Egipcjanom. W rzeczywistości w swoich obliczeniach dopuszczali także ułamki `2/3` i `3/4`, jednak tych ułamków umownie nie będziemy nazywać egipskimi.
Nie oznacza to oczywiście, że nie znali innych ułamków. Uważali je jednak za niewygodne, nieeleganckie, albo po prostu za będące zapisami działań, a nie ich wynikami. Na analogicznej zasadzie my dziś uważamy `5 : 8` za zapis działania, a `5/8` za wynik. Dla Egipcjan ułamki inne niż te zwane dziś przez nas egipskimi były zapisem zadania do wykonania, a spodziewanym wynikiem była suma ułamków egipskich. Zatem wynikiem działania `5 : 8` było dla Egipcjanina „pół i ósma część”, a zapis tego wyrażenia w piśmie hieroglificznym przypominał raczej nasze `2^(-1) + 8^(-1)` niż ułamki, którymi się zwykle posługujemy.
Takie działanie matematyczne nazywamy dziś rozkładem ułamków zwykłych na egipskie. Rozkład ten ma istotne ograniczenia.
Egipcjanie mocno podkreślali warunek ujęty tu w punkcie 2. Egipscy matematycy sporządzili nawet tabelę rozkładu ułamków o liczniku `2` na (różne) ułamki o liczniku `1` – można ją znaleźć w słynnym papirusie Ahmesa.
Liczby całkowite także można przedstawić jako sumy różnych ułamków egipskich, np. `1 = 1/2 + 1/3 + 1/6`. Mało to, ułamki egipskie także możemy rozłożyć na sumy mniejszych ułamków egipskich, np. `1/2 = 1/3 + 1/6` (co zresztą wynika wprost z rozkładu jedności). Tego typu działania mają jednak niewiele wspólnego z matematyką egipską. Wspominamy tu jednak o nich z całkiem innych powodów. Przypominamy też przy okazji, że z dwóch dodatnich ułamków o takim samym liczniku mniejszy jest ten, którego mianownik jest większy, np. `1/3 < 1/2`.
Dowolny ułamek można rozłożyć na ułamki egipskie na nieskończenie wiele sposobów. Wystarczy zauważyć, że każdy ułamek egipski `1/a` da się przedstawić jako suma dwóch innych ułamków egipskich: `1/(a + 1) + 1/(a(a + 1))`. Rzeczywiście, `1/(a + 1) + 1/(a(a + 1)) = a/(a(a + 1)) + 1/(a(a + 1)) = (a + 1)/(a(a + 1)) = 1/a`. A zatem `1/3 = 1/4 + 1/12`, `1/4 = 1/5 + 1/20`, `1/5 = 1/6 + 1/30` itd. (mianownik pierwszego ułamka jest o jeden większy, a mianownik drugiego jest iloczynem tej powiększonej o jeden liczby przez pierwotną wartość mianownika). Jeśli więc np. rozkład `1 = 1/2 + 1/3 + 1/6` z jakichś powodów nam się nie podoba, możemy zastąpić go innym, rozkładając jeden ze składników na mniejsze ułamki, np. `1 = 1/2 + 1/4 + 1/6 + 1/12`. Analogicznie, jeśli nie odpowiada nam rozkład `1/2 = 1/3 + 1/6`, łatwo zastąpimy go na przykład rozkładem `1/2 = 1/4 + 1/7 + 1/12 + 1/42` (niedowiarkowie proszeni są o sprawdzenie, że równość ta jest prawdziwa).
Podane przykłady sugerują, że znaleziony dość prosty rozkład można zastąpić innym, ale ten nowy jest bardziej skomplikowany. Istotnie, często tak właśnie jest, jednak nie zawsze. Istnieją bowiem ułamki, które udaje się rozłożyć na dwa lub więcej sposobów, a otrzymane wyniki mają tyle samo składników. Na przykład `3/10` można przedstawić jako `1/4 + 1/20` lub jako `1/5 + 1/10`. Ciekawym przykładem jest tu ułamek `3/7`; omówimy go szczegółowo w dalszej części (czytelników zachęca się, by już teraz samodzielnie spróbowali rozłożyć go na ułamki egipskie). Wiele ułamków można jednak rozłożyć do sumy określonej liczby składników tylko na jeden sposób (oczywiście każdy z nich możemy także rozłożyć, otrzymując sumy większej ilości składników).
Jak widać, rozkład na ułamki egipskie można przeprowadzać na różne sposoby, jednak ta wielość możliwości nie prowadzi do żadnych ciekawych i praktycznych rezultatów. Dlatego pójdziemy w ślady Egipcjan, i dodatkowo umówimy się, by (tak jak oni) rozkładać jedynie ułamki właściwe, czyli takie, których licznik jest mniejszy od mianownika, np. `3/4`, i w dodatku ułamki te nie były już ułamkami egipskimi. Całości i ułamków egipskich rozkładać nie będziemy. Jeśli ułamek jest niewłaściwy (np. `5/4`), to najpierw wyłączamy z niego całości, a na ułamki egipskie rozkładamy jedynie pozostały ułamek właściwy (o ile sam nie jest już ułamkiem egipskim). Zatem np. `5/4` doprowadzamy do postaci liczby mieszanej `1 1/4` (albo też sumy `1 + 4^(-1)`), i na tym kończymy nasze rachunki.
Podamy teraz warunki niezbędne do tego, by rozkład na ułamki egipskie nazwać rozkładem zwyczajnym. Oczywiście wciąż obowiązują warunki podane poprzednio, a dodatkowo także następujące:
Ostatni warunek ma głównie znaczenie estetyczne, natomiast warunek przedostatni spędza matematykom sen z powiek. Nikt dotąd nie potrafił bowiem pokazać, jaka jest maksymalna liczba składników, niezbędna do rozkładu każdego możliwego ułamka (spełniającego podane warunki). Istnieją tu tylko pewne hipotezy, np. takie, że ułamki o postaci `4/n`, a może i `5/n`, dadzą się rozłożyć na co najwyżej 3 ułamki egipskie.
Wielu matematyków rozpatruje tylko niektóre rozkłady, które tu nazwaliśmy zwyczajnymi. Żądają oni na przykład, by suma mianowników otrzymanych ułamków była jak najmniejsza. My nie będziemy stawiać takiego żądania (będziemy je rozpatrywać tylko jako wariant), tym bardziej, że algorytmy używane w poszukiwaniu rozkładu często prowadzą do całkiem innych rezultatów. Oznacza to jednak, że bardzo często będzie istnieć kilka rozkładów zwyczajnych danego ułamka nieegipskiego. A nasze zadanie polegać będzie nie na wyznaczeniu jednego, przypadkowo otrzymanego rozkładu, ale na wyznaczeniu wszystkich rozkładów.
Nazwa taka oznacza wieloetapowy sposób znajdowania rozwiązania jakiegoś problemu, który na każdym etapie przyjmuje tylko cząstkowe rozwiązania „zachłanne”, czyli takie, które uważa się za najlepiej rokujące (lokalnie optymalne), a odrzuca wszystkie inne rozwiązania, i dalej ich nie próbuje analizować.
Przy znajdowaniu rozkładu ułamków na egipskie często tego rodzaju algorytm stosuje się w praktyce. Nazywamy go algorytmem Fibonacciego, od nazwiska myśliciela, który go opracował (nie ma on nic wspólnego z postępowaniem starożytnych Egipcjan). Przedstawimy tu jego zasady.
Niech będzie dany ułamek `p/q` (spełniający narzucone wyżej warunki). Szukamy największego ułamka egipskiego `1/a`, który jest mniejszy bądź równy `p/q` (choć faktycznie na tym etapie nie może być równy, bo wówczas nie byłoby w ogóle mowy o rozkładzie). Ułamek ten jest pierwszym składnikiem rozkładu.
Odejmujemy ten ułamek od danego, otrzymując pewną różnicę, również w postaci ułamka. Ułamek ten doprowadzamy do postaci nieskracalnej. Jeśli jest to ułamek egipski, dopisujemy go do rozwiązania i kończymy rozkład. Jeśli nie, szukamy kolejnego największego ułamka egipskiego, niewiększego od tej różnicy.
Postępujemy tak kolejno tak długo, aż uda nam się otrzymać różnicę będącą ułamkiem egipskim (co często zauważymy, o ile nie zapomnimy o skróceniu).
Algorytm taki można stosunkowo łatwo zaimplementować w programie komputerowym. Jedyny poważny kłopot polega na konieczności sprawdzania, czy otrzymane ułamki są skracalne. Jeśli tak jest, program musi dokonać ich skrócenia – inaczej doprowadzi do błędnych rezultatów.
Działanie algorytmu Fibonacciego (w metodzie z użyciem przyborów do pisania, a nie programu komputerowego) pokażemy na przykładzie ułamka `u = 5/21`.
Aby znaleźć największy ułamek egipski, który nie jest większy od niego, rozpatrzymy odwrotność danego ułamka `1/u`, czyli `21/5`. Obliczmy wartość liczbową tego wyrażenia w postaci dziesiętnej; jest nią `4.2` (uwaga: tu i poniżej zamiast przecinka dziesiętnego pisać będziemy kropkę dziesiętną, która jest symbolem międzynarodowym, a w każdym razie występuje w programowaniu komputerowym). Skoro szukany ułamek `1/a` ma być mniejszy od danego `u`, to jego odwrotność `a` musi być większa od odwrotności `1/u`. Inaczej mówiąc, szukamy najmniejszej liczby naturalnej większej niż 4,2. Liczbą tą jest oczywiście 5. Szukanym ułamkiem jest więc `1/5`; jest to pierwszy składnik w rozkładzie. Zatem `5/21 = 1/5 +` …
Zgodnie z algorytmem odejmujemy teraz znaleziony ułamek od danego, a ponieważ mianowniki obu ułamków nie mają wspólnego czynnika, stosujemy metodę krzyża: `5/21 - 1/5 = (5*5 - 1*21)/(21*5) = (25 - 21)/105 = 4/105`. Otrzymany nieskracalny ułamek nie jest ułamkiem egipskim, musimy więc kontynuować poszukiwanie rozkładu.
Podobnie jak poprzednio, rozpatrujemy odwrotność różnicy, czyli `105/4`; jej wartością dziesiętną jest `26.25`. Najbliższa większa od niej liczba całkowita to `27`, zatem `1/27` będzie kolejnym składnikiem rozkładu: `5/21 = 1/5 + 1/27 +` …
Obliczamy kolejną różnicę: `4/105 - 1/27 = (4*27 - 1*105)/(105*27) = 3/2835`. Ułamek ten jest skracalny przez `3`. Dokonujemy więc skrócenia, i zapisujemy `4/105 - 1/27 = 1/945`.
Okazało się po skróceniu, że otrzymana różnica jest ułamkiem egipskim. Nasz algorytm dobiegł więc końca, a otrzymany rozkład ma postać `5/21 = 1/5 + 1/27 + 1/945`.
Jak już wspomnieliśmy, algorytm Fibonacciego sprawdza się przy układaniu programów komputerowych, jednak niestety nie zawsze doprowadza do rozwiązania spełniającego narzucone wyżej warunki. Otrzymany rozkład nie zawsze jest zwyczajny, co oznacza, że nie musi być najprostszy.
Mało to, jeśli narzucilibyśmy warunek, że mianowniki otrzymanych ułamków mają mieć najmniejszą możliwą sumę, wówczas algorytm Fibonacciego bardzo często nie doprowadzi nas do szukanego rozwiązania (nawet jeśli zawierać będzie ono najmniejszą możliwą liczbę składników). Jeśli z kolei nie narzucimy takiego warunku, będą nas interesować wszystkie rozwiązania o najmniejszej możliwej liczbie składników – a algorytm Fibonacciego dostarczy nam co najwyżej tylko jednego z tych rozwiązań.
I właśnie przykład ułamka `5/21` pokazuje, że algorytm Fibonacciego zupełnie się nie sprawdza. Nie dość, że nie uzyskamy z jego pomocą rozwiązania o najmniejszej sumie mianowników (gdybyśmy takiego właśnie rozwiązania żądali), to nawet nie otrzymamy rozwiązania o najmniejszej liczbie składników. W istocie więc nie otrzymamy rozkładu, który moglibyśmy określić jako zwyczajny.
Okazuje się bowiem, że jeśli w pierwszym kroku arbitralnie odrzucimy ułamek `1/5`, i zamiast niego równie arbitralnie (tj. nie kierując się żadnymi konkretnymi przesłankami) weźmiemy `1/6`, to otrzymamy różnicę (metodą sprowadzania do wspólnego mianownika, która w tym wypadku lepiej się sprawdza niż metoda krzyża) `5/21 - 1/6 = 10/42 - 7/42 = 3/42 = 1/14`. Okazuje się więc, że zwyczajny rozkład ułamka `5/21` ma postać o wiele prostszą od otrzymanej, a mianowicie `5/21 = 1/6 + 1/14`.
Widać chyba świetnie, do jakiego stopnia algorytm Fibonacciego nie spełnił swojego zadania! Nie dość, że zamiast dwóch zwrócił trzy składniki, to jeszcze ostatni ma mianownik astronomicznie wielki. Tymczasem najprostszy rozkład rozpatrywanego ułamka jest, jak się okazuje, o wiele prostszy i o ileż bardziej sympatyczny.
Powyżej postawiliśmy warunek, by rozkład zawierał jak najmniej składników. Jednocześnie oczekiwalibyśmy pewnie, by składniki te były jak największe (czyli by ich mianowniki nie były astronomicznej wielkości). Okazuje się, że różne otrzymane rozkłady nie muszą spełniać obu warunków jednocześnie.
Jako przykład rozpatrzymy ciekawy ułamek `3/179`. Algorytm Fibonacciego pozwala nam znaleźć rozkład `3/179 = 1/60 + 1/10740` (rzeczywiście, `179/3 = 59.666` …, stąd w rozkładzie może występować ułamek `1/60`). Jest to (jedyny!) rozkład dwuskładnikowy, ale występuje w nim nieprzyjemny ułamek o pięciocyfrowym mianowniku. Okazuje się, że można znaleźć inny rozkład omawianego ułamka, który ma co prawda trzy składniki, ale za to występują w nich o wiele przyjemniejsze ułamki: `3/179 = 1/63 + 1/1611 + 1/3759`. A jeśli szukamy ułamków o najmniejszych możliwych mianownikach, to powinien nas zaciekawić kolejny rozkład: `3/179 = 1/171 + 1/209 + 1/285 + 1/895 + 1/1611 + 1/1969 + 1/2685`. Mamy tu na końcu jeszcze większy ułamek (mniejszy mianownik), ale za to składników jest aż siedem…
Przykład ten pokazuje po pierwsze, że algorytm Fibonacciego czasami się jednak przydaje, a po drugie, że warto na rozkład narzucić jednak jakieś konkretne warunki (choćby dlatego, że bez nich każdy ułamek można rozłożyć na nieskończenie wiele sposobów). Żądanie najmniejszej możliwej liczby składników wydaje się najsensowniejsze. Jak jednak pokazuje analizowany przykład, niekiedy istnieją rozkłady o większej liczbie składników, ale takie, że występują w nich ułamki o mniejszych mianownikach. Jeśli chcemy jakoś zoptymalizować nasze oczekiwania, nie możemy wymogu najmniejszych mianowników traktować jako głównego. Właśnie dlatego wymieniliśmy go jedynie jako uzupełniający.