W kombinatoryce czasami spotykamy sytuację, w której można zastosować niejako dualne rozumowanie: jeśli do szuflad włożymy obiektów i żadna szuflada pusta nie będzie, to w żadnej szufladzie nie może się znaleźć więcej niż jeden obiekt. Możemy powiedzieć dosadniej: w każdej szufladzie będzie dokładnie jeden obiekt. Znowu, można powiedzieć, to widzi każdy przedszkolak, ale, wbrew pozorom, spostrzeżenie to ułatwia często rozumowanie w stopniu podobnym, jak wspomniana zasada szufladkowa.

Wynalazek systemu dziesiętnego był dla matematyki przełomowy. Zapisywanie liczb w układzie pozycyjnym uprościło niezwykle zarówno sam sposób opisu, jak i - przede wszystkim - algorytmy wykonywania na nich działań. (Jeśli ktoś nie wierzy, niech spróbuje w systemie rzymskim np. pomnożyć dwie liczby kilkucyfrowe.) Jedną z miłych i wcale nieoczywistych cech układu pozycyjnego jest to, że da się w nim wyrazić każdą liczbę naturalną i to na jeden tylko sposób, jeśli umówimy się, że nie piszemy zer przed właściwymi cyframi. To, że taka jednoznaczność przedstawienia nie jest oczywista, widać choćby gdy przejdziemy do liczb wymiernych. Na przykład 0,49999... i 0,50000... to dwa różne okresowe zapisy tej samej liczby Żeby było ciekawiej, z kolei liczby niewymierne mają zawsze jednoznaczne przedstawienie w postaci nieskończonego rozwinięcia dziesiętnego.

Okazuje się, że nie tylko system dziesiętny ma te własności. Wystarczy wziąć dowolną podstawę systemu pozycyjnego większą od 1 i otrzymamy analogiczne wyniki - też niektóre liczby wymierne będą miały dwa przedstawienia (ale będą to na ogół inne liczby niż w przypadku systemu dziesiętnego), też wszystkie wymierne liczby będą miały reprezentacje okresowe i też liczby naturalne będą miały jednoznaczne przedstawienie. Chyba jako pierwszy odkrył to w XVII wieku dla układu dwójkowego Gotfried Wilhelm Leibniz, który tak się zachwycił możliwościami systemu binarnego, że postulował powszechne przejście z systemu dziesiętnego na dwójkowy. Jakże przyjemna stałaby się nauka tabliczki mnożenia! Wystarczyłoby zapamiętać wyniki mnożenia zer i jedynek przez zera i jedynki.

Spróbujmy wykazać, że w systemie dwójkowym faktycznie wszystkie liczby naturalne mają jednoznaczne przedstawienie. Przypomnijmy: system dwójkowy operuje tylko dwiema cyframi: zerem i jedynką. Na pozycji -tej od końca (przy czym umówmy się, że ostatnia pozycja ma numer 0, przedostatnia 1, itd.) mamy cyfrę 1 lub 0, w zależności od tego, czy w skład liczby, którą chcemy reprezentować, wchodzi wartość czy nie. Taką cegiełkę możemy przy tym użyć co najwyżej raz - dlatego mamy tylko dwie cyfry w układzie dwójkowym. Na przykład liczba 13 ma przedstawienie dwójkowe 1101, gdyż Zatem komponujemy wartość każdej liczby jako sumę pojedynczych potęg dwójki.

Pokażemy najpierw, że każdą liczbę dodatnią da się przedstawić w zapisie dwójkowym co najmniej na jeden sposób. Zero to więc się da. Weźmy teraz dowolną dodatnią liczbę całkowitą Załóżmy (indukcja), że mniejsze od niej liczby mają przedstawienie dwójkowe, czyli dadzą się uzyskać przez zsumowanie różnych pojedynczych potęg dwójek. Niech będzie największą potęgą dwójki nieprzekraczającą Liczba jest nieujemna i mniejsza od więc na mocy założenia indukcyjnego ma przedstawienie dwójkowe. Jednocześnie bo inaczej nie byłoby największą potęgą dwójki mniejszą od Zatem biorąc jedynkę na pozycji a następnie dopisując rozwinięcie liczby (oczywiście, użyjemy tylko pozycji ), otrzymujemy liczbę reprezentowaną za pomocą cyfr binarnych. Czy jednak nie można liczby otrzymać w inny sposób, zakładając, że każdą potęgę dwójki bierzemy tylko co najwyżej raz? Okazuje się, że nie i w celu pokazania tej jednoznaczności użyjemy naszej odwróconej zasady Dirichleta.

Zauważmy, że największa liczba, którą da się zapisać za pomocą początkowych potęg dwójki, to Jeżeli bowiem złożymy liczbę z jedynek, czyli weźmiemy wszystkie wartości odpowiadające bitom to uzyskamy Zatem, jeśli jeszcze przypomnimy sobie o zerze, reprezentowanym przez zer, to okaże się, że na co najwyżej bitach możemy reprezentować liczb: wszystkie pomiędzy 0 a włącznie.

A ile jest ciągów zerojedynkowych długości Tyle samo, czyli Zatem skoro każdą liczbę z zakresu da się reprezentować na bitach, to nie jest możliwe, żeby dwa takie ciągi reprezentowały w tym zakresie tę samą liczbę - nie starczyłoby ich wtedy do reprezentowania wszystkich liczb. Ponieważ zaś było wybrane dowolnie, więc rozumowanie to dotyczy każdego -bitowego zakresu. Szufladkami w tym przypadku są liczby z zakresu a obiektami -bitowe ciągi zerojedynkowe.

Dopiero w XX wieku został odkryty nowy binarny system reprezentowania liczb naturalnych za pomocą liczb Fibonacciego. Przypomnijmy: liczby te wprowadzone zostały do matematyki na początku XIII wieku przez włoskiego uczonego Leonarda z Pizy zwanego Fibonaccim. Definiujemy je tak: pierwsze dwie liczby Fibonacciego to 0 i 1, a każda następna jest sumą dwóch poprzednich. Wygodniej jest zacząć numerację od zera, więc mamy dla Liczby Fibonacciego tworzą nieskończony ciąg

Powstaje pytanie: czy liczby Fibonacciego mogłyby służyć jako podstawa systemu binarnego, w którym liczby naturalne komponowalibyśmy, nie sumując wybrane potęgi dwójki, lecz poprzez dodanie wybranych liczb Fibonacciego? Na przykład liczbę 10 można by było otrzymać jako ale też jako jak również czy wręcz Co prawda każdej liczby Fibonacciego moglibyśmy w naszym rozkładzie użyć tylko raz, bo system ma być binarny, ale i tak widać, że niektóre z tych rozkładów są sztuczne. Wprowadźmy zatem dwa ograniczenia:

• nie używamy pierwszych dwóch liczb Fibonacciego, czyli zera i pierwszej z jedynek;
• nie używamy dwóch sąsiednich liczb Fibonacciego - ich suma jest następną liczbą Fibonacciego, więc nie rozmieniajmy na drobne samych liczb Fibonacciego; skupmy się na istotnie różnych reprezentacjach.

Przy tych ograniczeniach okaże się, że liczba 10 ma tylko jedno przedstawienie: Nie tylko Jeżeli będziemy próbowali z innymi liczbami naturalnymi, to przekonamy się, że one też dadzą się przedstawić za pomocą takich sum i to tylko na jeden sposób respektujący podane wyżej zastrzeżenia. To jest właśnie treścią twierdzenia udowodnionego jeszcze przed II wojną światową, ale opublikowanego dopiero w 1972 r. przez Édouarda Zeckendorfa, a sposób reprezentowania liczb naturalnych nazywa się binarną reprezentacją Fibonacciego lub kodowaniem Zeckendorfa. Kodowanie to zakłada, że bit o numerze odpowiada za liczbę dla Aby wykazać poprawność i jednoznaczność takiej reprezentacji, ponownie zastosujemy odwróconą zasadę Dirichleta.

Najpierw, tak jak poprzednio, pokażemy, że każda liczba ma przedstawienie Zeckendorfa. Podobnie jak w przypadku systemu binarnego użyjemy indukcji. Niech będzie największą liczbą Fibonacciego, nieprzekraczającą Znowu dla i sprawdzamy bezpośrednio, że odpowiadają im ciągi oraz Załóżmy teraz, że i że wszystkie liczby mniejsze od mają przedstawienie Fibonacciego. Rozważmy największą liczbę Fibonacciego nieprzekraczającą Nasza reprezentacja będzie zatem -bitowa. Jej drugim bitem będzie zero, gdyż liczba musi być mniejsza od bo inaczej byłaby mniejsza od co przeczyłoby definicji Dzięki temu, że drugi bit jest równy zeru, możemy skorzystać z założenia indukcyjnego i uzupełnić ciąg zaczęty od o przedstawienie Fibonacciego liczby Będzie on na pewno poprawną reprezentacją w której żadne dwie jedynki nie wystąpią obok siebie.

Teraz zajmiemy się jednoznacznością. Najpierw jednak zastanówmy się, jak wygląda największa liczba reprezentowana w systemie Zeckendorfa na bitach. Zaczyna się od jedynki odpowiedzialnej za wartość potem musi być zero (rezygnujemy z liczby ), a następnie największa liczba reprezentowana na bitach, czyli znów jedynka odpowiadająca potem zero, jedynka, zero, aż dojdziemy do końca. W zależności od tego, czy jest parzyste, czy nie, zakończymy naszą reprezentację zerem lub jedynką. Pokażemy teraz, że czyli że największa liczba reprezentowana na bitach jest -gą liczbą Fibonacciego pomniejszoną o Dla zgadza się: największa liczba to czyli Dla też: ciąg reprezentuje liczbę Podwójne sprawdzenie bazy indukcji jest tu konieczne, ze względu na dwa możliwe zakończenia: zerem lub jedynką, w zależności od parzystości Jeśli teraz to największa liczba -bitowa ma wartość równą plus, na mocy założenia indukcyjnego, największa liczba na bitach, czyli Ale i mamy tezę.

Skoro już wiemy, że na bitach można reprezentować wszystkie liczby od zera do to zadajmy standardowe pytanie: a ile jest takich -elementowych zerojedynkowych ciągów, że żadne dwie jedynki nie występują obok siebie. Oznaczmy tę liczbę przez Dla mamy odpowiedź (pusty ciąg). Dla wiemy, że takich ciągów mamy 2, czyli Teraz zastanówmy się, jak to będzie w przypadku Albo taki -elementowy ciąg bitów kończy się jedynką, albo nie. Jeśli kończy się jedynką, to na przedostatnim bicie musi być zero, a na pozostałych bitach dowolny układ, a ich jest Jeśli zaś taki ciąg kończy się zerem, to na pozostałych bitach może być dowolny układ, a jest ich Ostatecznie mamy następujące równanie rekurencyjne:

Rozwiązaniem tego układu jest

Wiemy więc, że na bitach można reprezentować co najwyżej liczb i wiemy, że można reprezentować wszystkie liczby od 0 do a jest ich oczywiście też No to nie ma tu miejsca na niejednoznaczność! Odwrócona zasada Dirichleta działa i tutaj. Każda liczba naturalna ma zatem jednoznaczne przedstawienie Fibonacciego.

Powstaje pytanie, czy takie binarne reprezentacje Fibonacciego mogą się do czegoś przydać? Nieoczekiwanie - poza interesującą własnością jednoznacznego rozkładu - notacja Zeckendorfa daje nam pamięciową metodę przybliżonej konwersji mil na kilometry i na odwrót. Najpierw zastanówmy się, jak zmienia się wartość liczby zapisanej w notacji Zeckendorfa, gdy na końcu ciągu zer i jedynek reprezentujących jakąś liczbę dopiszemy zero. Sumowane wartości będą teraz odpowiadały liczbom Fibonacciego o indeksach o 1 większych. W układach pozycyjnych też jest podobnie: dopisanie zera na końcu liczby, np. w układzie dziesiętnym, powoduje, że każda cyfra zacznie odpowiadać dziesiątce podniesionej do potęgi o 1 wyższej, wskutek czego liczba zwiększy swoją wartość dziesięciokrotnie. Ilokrotnie jednak zwiększy się wartość liczby zapisanej w binarnej notacji Zeckendorfa po dopisaniu zera na końcu?

Liczby Fibonacciego, co zostało odkryte po raz pierwszy przez Eulera w 1768 roku, spełniają zupełnie nieoczywistą rekurencję: gdzie a Ze względu na to, że dąży szybko do zera, możemy przyjąć, że każda liczba Fibonacciego o w miarę dużym indeksie jest w przybliżeniu razy większa od swojej poprzedniczki i błąd będzie tym mniejszy, im wyższy numer. Zwiększenie numeru liczby Fibonacciego o jeden odpowiada zatem mniej więcej przemnożeniu przez 1,618.... Tymczasem jedna mila to około 1,609; prawie

Jak zatem zamieniać mile na kilometry? Wystarczy znaleźć reprezentację Zeckendorfa danej liczby mil, a następnie zsumować liczby Fibonacciego o numerach o 1 wyższych. Przykładowo, jedziemy w Stanach Zjednoczonych samochodem i widzimy ograniczenie do 55 mil/h. Uśmiechamy się tylko, bo 55 to przypadkowo dziesiąta liczba Fibonacciego, więc tylko przeskakujemy do jedenastej, czyli 89 km/h. W rzeczywistości powinno wyjść 88,514, zatem błąd to niespełna pół kilometra na godzinę. Idźmy dalej: inne częste ograniczenie 45 mil/h. Tym razem w pamięci rozkładamy 45 jako i przesuwamy indeksy z 34, robiąc 55, z 8 robiąc 13, a z 3 robiąc 5. Razem Tym razem błąd nieco większy: powinno wyjść 72,420, czyli dostaliśmy o 0,580 za dużo. Ale cały czas mieścimy się w granicach poniżej jedynki. Jak się okazuje, dla wszystkich liczb aż do 58 mil nie zrobimy błędu przekraczającego 1.

W drugą stronę analogicznie, tylko trzeba pomniejszać indeksy liczb Fibonacciego. Na przykład: ile mil to 100 kilometrów? Liczymy: więc bierzemy liczby Fibonacciego przesunięte w lewo: mile. W rzeczywistości powinno wyjść 62,137, więc tym razem błąd jest mały. Mieliśmy szczęście. Podobnie jak z milami, aż do 95 km podana konwersja nie oszuka nas o więcej niż 1. Przy czym stosujemy zasadę: zostawiamy ostatnią jedynkę rozwinięcia; przecież na lewo od jedynki jest jedynka

Pozostaje nauczyć się liczb Fibonacciego na pamięć. Pamiętajmy: