Przeskocz do treści

Delta mi!

Loading

Bity w szufladkach

Piotr Chrząstowski

o artykule ...

  • Publikacja w Delcie: grudzień 2016
  • Publikacja elektroniczna: 30 listopada 2016
  • Wersja do druku [application/pdf]: (227 KB)

Tak zwana zasada szufladkowa Dirichleta, jakże lubiana przez rozmaite komitety olimpiad matematycznych, łączy w sobie dwie atrakcyjne cechy. Z jednej strony jest tak prosta, że nawet dziecko w przedszkolu jest w stanie ją zrozumieć, z drugiej zaś zawiera zupełnie nieoczywisty element niekonstruktywny. Głosi ona mianowicie, że wkładając do n szuflad więcej niż n przedmiotów, mamy pewność, że w którejś szufladzie będą co najmniej dwa obiekty. W której - nie wiadomo, ale na pewno w którejś.

W kombinatoryce czasami spotykamy sytuację, w której można zastosować niejako dualne rozumowanie: jeśli do n szuflad włożymy n 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  1 |2. Ż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 i -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ść 2i, czy nie. Taką cegiełkę |2i 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ż |13 = 8+ 4 + 1 = 1⋅23 + 1⋅22 + 0 ⋅21 + 1⋅20. Zatem komponujemy wartość każdej liczby jako sumę pojedynczych potęg dwójki.

|---|---|---|---|--|--|---|--| | | 0 | 0 | 0 |1 |1 |0 |1 | |---|---|---|---|--|--|---|--| |2i-|64-|32-|16-|8-|4-|2--|1-| --i---6---5---4--3--2---1--0-|

Pokażemy najpierw, że każdą liczbę dodatnią da się przedstawić w zapisie dwójkowym co najmniej na jeden sposób. Zero to 0, więc się da. Weźmy teraz dowolną dodatnią liczbę całkowitą |n. 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  j |k = 2 będzie największą potęgą dwójki nieprzekraczającą n. Liczba |n′= n −k jest nieujemna i mniejsza od n, więc na mocy założenia indukcyjnego ma przedstawienie dwójkowe. Jednocześnie n ′< k, bo inaczej k nie byłoby największą potęgą dwójki mniejszą od n. Zatem biorąc jedynkę na pozycji  j, a następnie dopisując rozwinięcie liczby  ′ |n (oczywiście, użyjemy tylko pozycji  j− 1, j− 2,...,0 ), otrzymujemy liczbę |n reprezentowaną za pomocą | j+ 1 cyfr binarnych. Czy jednak nie można liczby n 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  j potęg dwójki, to |2 j− 1. Jeżeli bowiem złożymy liczbę z | j jedynek, czyli weźmiemy wszystkie wartości odpowiadające bitom | j− 1, j − 2,...,0, to uzyskamy  j −1 k j P k 02 = 2 −1. Zatem, jeśli jeszcze przypomnimy sobie o zerze, reprezentowanym przez | j zer, to okaże się, że na co najwyżej  j bitach możemy reprezentować |2 j liczb: wszystkie pomiędzy 0 a  j 2 − 1 włącznie.

A ile jest ciągów zerojedynkowych długości  j? Tyle samo, czyli |2 j. Zatem skoro każdą liczbę z zakresu  j |[0, ...,2 − 1] da się reprezentować na | j 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ś  j było wybrane dowolnie, więc rozumowanie to dotyczy każdego | j -bitowego zakresu. Szufladkami w tym przypadku są liczby z zakresu [0,...,2 j− 1], a obiektami  j -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 |F0 = 0, |F1 = 1, |Fn = Fn−1 + Fn−2 dla |n > 1. Liczby Fibonacciego tworzą nieskończony ciąg

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377, ....

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 |8+ 2, ale też jako 5+ 3 +2, jak również 5+ 3 +1 +1, czy wręcz | 5+ 3+ 1+ 1+ 0. 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: |8+ 2. Nie tylko 10. 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  j odpowiada za liczbę F j+1 dla  j > 0. 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 Fk będzie największą liczbą Fibonacciego, nieprzekraczającą n. Znowu dla n = 1 i n = 2 sprawdzamy bezpośrednio, że odpowiadają im ciągi | 1 oraz | 10. Załóżmy teraz, że | n > 2 i że wszystkie liczby mniejsze od |n mają przedstawienie Fibonacciego. Rozważmy największą liczbę Fibonacciego F j nieprzekraczającą n. Nasza reprezentacja będzie zatem |( j+ 1) -bitowa. Jej drugim bitem będzie zero, gdyż liczba |n− F j musi być mniejsza od F j−1, bo inaczej Fj +1 = F j + F j−1 byłaby mniejsza od n, co przeczyłoby definicji F j. 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 |10 o przedstawienie Fibonacciego liczby |n −F . j Będzie on na pewno poprawną reprezentacją n, 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 | j bitach. Zaczyna się od jedynki odpowiedzialnej za wartość F j+1, potem musi być zero (rezygnujemy z liczby F j ), a następnie największa liczba reprezentowana na  j −2 bitach, czyli znów jedynka odpowiadająca Fj −1, potem zero, jedynka, zero, aż dojdziemy do końca. W zależności od tego, czy  j jest parzyste, czy nie, zakończymy naszą reprezentację zerem lub jedynką. Pokażemy teraz, że |F + F + F + ... = F − 1, j+1 j−1 j−3 j +2 czyli że największa liczba reprezentowana na | j bitach jest |( j+ 2) -gą liczbą Fibonacciego pomniejszoną o |1. Dla | j = 1 zgadza się: największa liczba to 1, czyli F3 − 1. Dla  j = 2 też: ciąg |10 reprezentuje liczbę |2 = F4 −1. 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  j. Jeśli teraz | j > 2, to największa liczba | j -bitowa ma wartość równą Fj +1 plus, na mocy założenia indukcyjnego, największa liczba na  j− 2 bitach, czyli F j− 1. Ale |F + F −1 = F − 1 j+1 j j +2 i mamy tezę.

Skoro już wiemy, że na  j bitach można reprezentować wszystkie liczby od zera do |F − 1, j+2 to zadajmy standardowe pytanie: a ile jest takich | j -elementowych zerojedynkowych ciągów, że żadne dwie jedynki nie występują obok siebie. Oznaczmy tę liczbę przez T ( j). Dla  j = 0 mamy odpowiedź T (0) = 1 (pusty ciąg). Dla  j = 1 wiemy, że takich ciągów mamy 2, czyli T (1) = 2. Teraz zastanówmy się, jak to będzie w przypadku | j > 1. Albo taki | j -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 | j− 2 bitach dowolny układ, a ich jest T ( j− 2). Jeśli zaś taki ciąg kończy się zerem, to na pozostałych | j− 1 bitach może być dowolny układ, a jest ich T( j − 1). Ostatecznie mamy następujące równanie rekurencyjne:

T(0) = 1(= F2), T(1) = 2(= F3), T ( j) = T ( j− 2)+ T ( j− 1).

Rozwiązaniem tego układu jest T( j) = F j+2.

Wiemy więc, że na  j bitach można reprezentować co najwyżej |F j+2 liczb i wiemy, że można reprezentować wszystkie liczby od 0 do |F j+2 −1, a jest ich oczywiście też F j+2. 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.

obrazek

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?

obrazek

Liczby Fibonacciego, co zostało odkryte po raz pierwszy przez Eulera w 1768 roku, spełniają zupełnie nieoczywistą rekurencję: Fn+1 = φFn + ˆφn, gdzie  - |φ = 1+-5-= 1,618..., 2 a  - φˆ= 1−-5 =− 0,618 ... 2 Ze względu na to, że |ˆφn 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 0,486 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 34 +8 + 3 i przesuwamy indeksy z 34, robiąc 55, z 8 robiąc 13, a z 3 robiąc 5. Razem 55 + 13+ 5 = 73 km/h. 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: 100 = 89 + 8+ 3, więc bierzemy liczby Fibonacciego przesunięte w lewo: 55+ 5 +2 = 62 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 |F 2 jest jedynka |F1.

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

0,1,1,2,3,5,8,13,21,34, 55,89,144, 233,377,610,987,1597,2584,...


Errata

W wersji papierowej artykułu chochlik drukarski napisał w ostatnim wierszu 1567 zamiast 1597. Przepraszamy.