Każda dodatnia liczba całkowita ma unikalny „kod” z liczb Fibonacciego

Nie tylko potęgi dziesięciu i dwóch

Zwykły zapis dziesiętny rozkłada liczbę na wielokrotności potęg 10, a zapis binarny — potęg 2. Twierdzenie Zeckendorfa pokazuje, że można zbudować sensowny, jednoznaczny sposób reprezentacji także z liczb Fibonacciego. Nie jest to klasyczny system pozycyjny, bo „wagi” 1, 2, 3, 5, 8, 13, … nie są kolejnymi potęgami jednej podstawy. Mimo to każda dodatnia liczba otrzymuje dokładnie jeden zapis, jeśli narzucimy właściwe ograniczenie.

Dlaczego trzeba zakazać sąsiednich wyrazów

Bez ograniczeń jedna liczba może mieć wiele rozkładów. Ponieważ każda liczba Fibonacciego jest sumą dwóch poprzednich, dowolny użyty wyraz można czasem zastąpić parą wcześniejszych. Na przykład 13 można zastąpić 8+5. Warunek „nie używaj dwóch kolejnych wyrazów” usuwa właśnie tę podstawową niejednoznaczność. W reprezentacji Zeckendorfa współczynniki są tylko 0 lub 1, a dwie jedynki nie mogą stać obok siebie w pozycjach odpowiadających kolejnym liczbom Fibonacciego.

Algorytm zachłanny działa

Reprezentację można znaleźć bardzo naturalnie: wybierz największą liczbę Fibonacciego nieprzekraczającą N, odejmij ją, a następnie powtarzaj procedurę dla reszty. Dla 100 najpierw wybieramy 89, zostaje 11; następnie 8, zostaje 3; na końcu 3. Otrzymujemy 89+8+3. Nie jest oczywiste, że taka zachłanna procedura zawsze zakończy się poprawnym i jedynym dopuszczalnym zapisem, ale właśnie to gwarantuje struktura stojąca za twierdzeniem.

Ciąg Fibonacciego jako system numeracji

W reprezentacji Zeckendorfa można myśleć o liczbie jako o ciągu zer i jedynek mówiących, które wyrazy Fibonacciego zostały użyte. Zakaz dwóch sąsiednich jedynek odróżnia ten zapis od binarnego. Powstaje system numeracji o własnej arytmetyce i powiązaniach z kombinatoryką oraz informatyką. Ciekawostka jest więc czymś więcej niż kolejną własnością znanego ciągu: pokazuje, że pojęcie „zapisu liczby” może działać znacznie szerzej niż szkolne systemy pozycyjne.

Jednoznaczność jest równie ważna jak istnienie

Łatwo byłoby skonstruować regułę, która pozwala zapisać każdą liczbę jako sumę wyrazów Fibonacciego — ponieważ mamy 1 i 2, możliwości jest bardzo dużo. Siła twierdzenia Zeckendorfa polega na tym, że po nałożeniu prostego zakazu sąsiednich wyrazów nie tylko zawsze otrzymujemy jakiś zapis, ale otrzymujemy dokładnie jeden. To analogiczna rola do zakazu cyfr większych niż 9 w systemie dziesiętnym: ograniczenia są tym, co usuwa niejednoznaczność reprezentacji. Dzięki temu można porównywać liczby na podstawie ich kodów Zeckendorfa i projektować algorytmy operujące na takich reprezentacjach. Twierdzenie pokazuje więc, że Fibonacci nie jest tylko ciągiem pojawiającym się w zadaniach o królikach czy złotym podziale — może pełnić funkcję fundamentu systemu numeracji o ścisłej zasadzie kanonicznego zapisu.

Przykład większej liczby pokazuje strukturę zapisu

Dla 1000 algorytm zachłanny wybiera 987, a po odjęciu pozostaje 13, więc reprezentacja Zeckendorfa ma prostą postać 1000=987+13. Dla innych liczb składników jest więcej, lecz zasada pozostaje ta sama. Największy możliwy wyraz jest wybierany pierwszy, a struktura ciągu Fibonacciego gwarantuje, że następny użyty wyraz nie będzie z nim sąsiadował. Dzięki temu lokalna decyzja zachłanna prowadzi do globalnie kanonicznego zapisu — własność, której wiele problemów optymalizacyjnych nie posiada.

Zakaz sąsiednich wyrazów ma naturalne uzasadnienie

Jeśli w sumie pojawiłyby się dwa kolejne wyrazy F_k i F_(k+1), można je zastąpić następnym F_(k+2), bo właśnie tak definiuje się ciąg Fibonacciego. Reprezentacja zawierająca sąsiednią parę nie jest więc w pewnym sensie „zredukowana”. Warunek Zeckendorfa wybiera postać, w której takich lokalnych uproszczeń już nie ma. Twierdzenie mówi, że po wykonaniu wszystkich możliwych redukcji otrzymujemy nie tylko postać poprawną, ale tę samą kanoniczną postać niezależnie od drogi. To tłumaczy intuicyjnie, dlaczego ograniczenie tak dobrze pasuje do rekurencji Fibonacciego.