Drzewa przy autostradzie, czyli o porządkowaniu wymierności

Z liczbami naturalnymi nie ma kłopotu. Są zdyscyplinowane i uporządkowane. Każda stoi tam, gdzie powinna – za poprzednią, mniejszą o jeden. Można powiedzieć, że ciąg liczb naturalnych przypomina autostradę w budowie – rośnie w jednym miejscu, w jednym kierunku i równomiernie, choć w przeciwieństwie do autostrady – w nieskończoność.

W przypadku liczb wymiernych, czyli ułamków zwykłych a/b, gdzie a i b są liczbami naturalnymi (ograniczymy się do wartości dodatnich), sprawa nie jest już taka prosta. Tworzą one także nieskończony zbiór, ale ustawić je „według wzrostu” nie sposób, bo nieskończoność pojawia się na każdym kroku. Nie wiadomo nawet, jak zacząć, czyli jaki powinien być najmniejszy ułamek w hipotetycznym rosnącym ciągu liczb wymiernych. Jego licznik musiałby być równy 1, a mianownik nieskończenie duży, ale nieskończoność nie jest liczbą.

Mimo to możliwe jest przedstawienie wszystkich liczb wymiernych w postaci nieskończonego ciągu, choć nie rosnącego albo… rosnącego inaczej. Sprytnie i prosto poradził sobie z tym niemiecki matematyk Georg Cantor w roku 1873, sporządzając tabelę, której wiersze i kolumny oznaczone były kolejnymi liczbami naturalnymi. Przecięcia wierszy (w) i kolumn (k) takiej tabeli odpowiadają ułamkom (w/k), zaś cała jest nieskończenie pojemna i obejmuje wszystkie liczby wymierne, łącznie z kompletem ich kopii, czyli ułamkami skracalnymi. Ciąg powstaje, gdy spisujemy liczby „zygzakiem po skosie” (rys. 1) – wszystkie są jakby zgarniane przez pracujący przy budowie autostrady spychacz z nieskończenie szerokim lemieszem, jadący po przekątnej tabeli. Po pominięciu ułamków skracalnych ciąg przybiera osobliwą postać:

1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5,…

Osobliwą, ponieważ jest na przemian to malejący, to rosnący i stopniowo zmierza do objęcia wszystkich liczb wymiernych.

Cała ta konstrukcja była jednym z pierwszych kroków na drodze zmagań Cantora z nieskończonością – posłużyła mu do wykazania, że liczb wymiernych jest tyle samo, ile naturalnych. Wydaje się to sprzeczne ze zdrowym rozsądkiem, skoro zbiór liczb naturalnych N jest podzbiorem liczb wymiernych Q. Jednakże oba te zbiory są nieskończonymi ciągami, a ich wyrazy można ponumerować i połączyć w pary 1q₁, 2q₂, 3q₃,…, które utworzą ciąg i zbiór nieskończony, a więc równoliczny ze zbiorami N i Q.

Skoro Cantor wszystkie liczby wymierne ustawił w ciąg, dowiódł tym samym, że zbiór liczb wymiernych jest zbiorem przeliczalnym. W dalszych rozważaniach wystarczy jednak rozpatrywać tylko ułamki właściwe, czyli liczby wymierne zawarte w przedziale [0, 1). Każdej liczbie wymiernej z tego przedziału odpowiada bowiem przeliczalna liczba liczb różniących się od niej o liczbę całkowitą. Na przykład z liczbą 1–3 skoligacone są liczby mieszane 11–3, 21–3, 31–3 itd. Tabelę Cantora można więc obciąć, ograniczając ją do trójkąta obejmującego tylko ułamki właściwe (rys. 2). Spisywany z niej ciąg różni się od pełnotabelowego brakiem liczb większych od jedności:

1, 1/2, 1/3, 2/3, 1/4, 1/5, 3/4, 2/5, 1/6, 1/7, 3/5, 4/5, 2/7, 1/8, 1/9, 3/7…

Oba tabelowe ciągi Cantora powstają w nieco chaotyczny sposób i są w związku z tym trudne do zwięzłego, przejrzystego zdefiniowania. Istnieje jednak elegantsza metoda porządkowania liczb wymiernych. Przypomina ona budowanie jednej autostrady równocześnie w wielu oddalonych od siebie punktach – nie ma jednak wątpliwości, że punkty te pojawiają się we właściwych miejscach, czyli na wyznaczonej trasie.

Zaczynamy od punktów skrajnych, czyli od zera i jedynki przedstawionych w postaci pary ułamków 0/1 i 1/1. Następnie wpisujemy między nimi tzw. mediantę (nie mylić z medianą), czyli ułamek, którego licznik jest sumą liczników, a mianownik sumą mianowników tej pary, a więc 1/2. W kolejnych krokach postępujemy analogicznie z prawie każdą parą sąsiednich ułamków, umieszczając między nimi ich mediantę. Prawie, ponieważ aby zachowany był porządek, wprowadzamy ograniczenie: mianownik żadnego ułamka nie może przekroczyć ustalonej liczby n. Jeśli przyjmiemy n=9, to cały ośmioetapowy proces pojawiania się kolejnych fragmentów zaplanowanej autostrady będzie wyglądał jak na rys. 3. Fragmentami są czerwone ułamki, ukazujące się jako medianty w danym etapie.

Otrzymany ciąg zawiera wszystkie ułamki z przedziału [0, 1] o mianowniku nie większym niż 9, bez ułamków skracalnych, w dodatku uporządkowane w kolejności rosnącej. Wszystkie powstające w ten sposób ciągi zwane są ciągami Fareya, oznaczanymi ogólnie literą F, a konkretnie – F_n, gdzie n równe ekstremalnemu mianownikowi jest rzędem ciągu.

W trzech pierwszych etapach dochodzenia do niebieskiego ciągu F₉ tworzone są żółte ciągi F₁, F₂ i F₃, ale kolejny czwarty ciąg nie jest już ciągiem F₄, ponieważ nie spełnia warunku n=4. Aby takim był, należałoby usunąć z niego ułamki z mianownikiem równym 5. Na rys. 4 znajdują się ciągi od F₄ do F₈, które powstają po wykreśleniu z ciągów od czwartego do ósmego na rys. 3 ułamków z nadmiarowymi mianownikami. John Farey, angielski geolog, który opisał te ciągi w 1816 roku jako liczbową osobliwość, utworzył je w sposób odwrotny do opisanego wyżej. Po prostu ustawił w kolejności rosnącej wszystkie dodatnie ułamki właściwe nieskracalne o mianowniku nie większym niż n i ze zdziwieniem zauważył, że każdy jest mediantą dwu sąsiednich.

Farey nie potrafił wyjaśnić tej zależności. Uczynili to matematycy francuscy – w tym samym roku Augustin Louis Cauchy, a – jak się potem okazało – 14 lat wcześniej w przeoczonej lub zapomnianej publikacji Charles Haros. Z możliwych wyjaśnień najbardziej „obrazowe” jest geometryczne.

Każdy ułamek właściwy dodatni y/x można przedstawić w układzie współrzędnych jako wektor o początku w punkcie (0, 0) i końcu w (x, y). Na rys. 5 znajdują się wszystkie wektory (niebieskie; gwoli przejrzystości rysunku pominięto strzałki na końcach wektorów), odpowiadające ułamkom tworzącym ciąg F₆. Końce tych wektorów są widoczne z punktu (0, 0), co oznacza, że nie przecinają one żadnych punktów kratowych (o współrzędnych całkowitych).

Warto zauważyć, że im większy kąt nachylenia wektora do osi x, tym większa wartość odpowiadającego mu ułamka. Liczeniu medianty odpowiada na rysunku sumowanie dwu wektorów znaną z lekcji fizyki metodą równoległoboku, stosowaną na przykład przy wyznaczaniu siły wypadkowej. Koniec sumy wektorów (a, b) i (c, d) znajdzie się oczywiście w punkcie kratowym (a+c, b+d), odpowiadającym ułamkowi (b+d)/(a+c). Koniec ten może wypaść wewnątrz żółtego obszaru lub poza nim, czyli może odpowiadać mianownikowi ułamka mniejszemu lub większemu od 6. Może też być widoczny lub niewidoczny z punktu (0, 0). Jeśli jest niewidoczny, odpowiada ułamkowi skracalnemu, czyli przecina punkt ułamka nieskracalnego. Tak jest w oznaczonej na rys. 5 niebiesko-czerwonej sumie wektorów (3, 1) i (5, 1). Suma ta wyznacza ułamek 2/8, czyli 1/4, powstający w ciągu F między ułamkami, których odpowiednikami są wektory (1, 0) i (3, 1). Dodawanie przy tworzeniu ciągu F_n zawsze pary sąsiednich wektorów (liczników i mianowników ułamków) gwarantuje, że żaden ułamek nie powtórzy się, żadnego nie zabraknie i każdy będzie nieskracalny (koniec każdego wektora będzie widoczny). Wynika to pośrednio z następującej zależności między dwoma kolejnymi ułamkami a/b i a’/b’:

jeśli a/b<a’/b’, to a’b–ab’=1.

Zależność tę łatwo udowodnić przez indukcję (proszę spróbować). Z innych własności ciągów F dobrze widoczne są dwie związane z symetrią, wynikającą z faktu, że środkowym wyrazem ciągu zawsze jest 1/2: suma ułamków położonych symetrycznie względem 1/2 jest zawsze równa 1, zaś ich mianowniki są takie same. Inaczej mówiąc, mianowniki wszystkich ułamków tworzą ciąg palindromowy, czyli niezmieniający się po zapisaniu wspak.

Pisząc o „osobliwych ciągach”, Farey zauważył także, że liczba wyrazów w kolejnych, od F₁ do F₉, tworzy rosnący ciąg liczb pierwszych – od 2 do 29. Są to liczby kolejne – z jednym wyjątkiem – brak jest ciągu 17-wyrazowego. Szybko wykluczono jednak ogólniejsze powiązanie ciągów F z liczbami pierwszymi w tym przypadku (jak się później okazało, całkowicie nie można tego wykluczyć), bowiem od F₁₀ zaczynają się pojawiać ciągi liczące nie pierwsze liczby wyrazów. Wzór na liczbę wyrazów nietrudno wyprowadzić, przyglądając się ciągom od F₁ do F₉ na rys. 3 i 4. W każdym kolejnym ciągu przybywa tyle ułamków, ile jest liczb mniejszych od n względnie pierwszych z rzędem n tego ciągu. Liczba ta, zwana stałą Eulera lub tocjentem, oznaczana jest jako φ(n). Na przykład: ciąg F₄ ma o dwa wyrazy więcej niż F₃, bo φ(4)=2 (liczby 1 i 3; 1 jest względnie pierwsza z każdą liczbą); F₇ jako liczba pierwsza ma o n–1, a więc o sześć wyrazów więcej niż F₆, ponieważ φ(7)=6 (1,2,3,4,5,6) – liczby w nawiasie pojawiają się w licznikach nowych ułamków, czyli tych z mianownikiem równym n. Stąd prosty wzór rekurencyjny na liczbę wyrazów ciągu: |F_n|=|F_n-1|+φ(n). Asymptotyczne oszacowanie funkcji |F_n|, czyli określenie granicy, do której ona zmierza, gdy rośnie n, wyraża się nieco zaskakującym wzorem |F_n|≈3n²/π². To jeden z tych dziwnych przypadków, gdy liczba π pojawia się w sytuacji, niemającej nic wspólnego z okręgiem.

Wszystkie ciągi F są skończone i obejmują ten sam zakres liczb z przedziału [0, 1]. Każdy następny jest jednak nieco gęstszy, bo bogatszy o nowe liczby. Jeśli zrezygnować z ograniczenia wartości mianowników, to ciągi połączą się, tworząc nieskończenie wybujałe i rozłożyste drzewo Fareya (rys. 6). A jeśli zakres liczb rozszerzyć do nieskończoności, oznaczonej jako ułamek z zakazanym zerem w mianowniku – 1/0, to drzewo F zmieni się w drzewo Sterna-Brocota (S-B), owocujące wszystkimi dodatnimi liczbami wymiernymi (rys. 7). Schemat owocowania jest podobny, jak na drzewie F, czyli para sąsiednich ułamków zawsze rodzi mediantę na niższym poziomie. Różnica jest tylko taka, że na drzewie F medianta ułamków z poziomu n o mianowniku b+d pojawia się na poziomie n_m=b+d, a na drzewie S-B zawsze na poziomie n+1, czyli jedno piętro niżej.

Najmłodszym drzewem liczb wymiernych dodatnich, „posadzonym” w roku 1999, jest drzewo Calkina-Wilfa (C-W). Jego zalążek stanowi liczba 1 w postaci ułamka 1/1, a każdy ułamek a/b rodzi dwa ułamki: a/a+b z lewej strony i a+b/b z prawej (rys. 8). Co istotne, także tutaj, podobnie jak w drzewach F i S-B, nie brak żadnej dodatniej liczby wymiernej, każda występuje tylko raz i każda w postaci nieskracalnego ułamka.

Łatwo zauważyć podobieństwa między drzewami S-B i C-W. Na przykład: na kolejnych poziomach obu drzew pojawiają się jako nowe te same liczby, ale inaczej rozmieszczone. Jeśli jednak powrócimy z drzew na autostradę, czyli do ciągów, okaże się, że ustawienie ułamków na drzewie C-W generuje elegantszy ciąg liczb wymiernych niż jakikolwiek inny. Przede wszystkim nie jest to ciąg ciągów, jak w przypadku Fareya, lecz jeden ciąg C-W, który powstaje po spisaniu ułamków z drzewa kolejno rzędami poziomymi:

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4,…

W pozornym szaleństwie tego ciągu jest metoda, a ściślej dwie metody, zapewniające porządek:

(I) mianownik (b) każdego ułamka jest licznikiem (a) następnego;

(II) liczniki kolejnych ułamków tworzą tzw. ciąg Sterna (1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,...), w którym n-ty wyraz oznacza, na ile sposobów da się przedstawić liczbę n–1 jako sumę potęg dwójki, przy czym ta sama potęga może wystąpić w sumie co najwyżej dwa razy (np. dziewiąty wyraz a₉=4, ponieważ 8=2³=2²+2²=2¹+2¹+2²=2⁰+2⁰+2¹+2²). Ponadto między wyrazami tego ciągu występuje wiele ciekawych zależności. Jedna z nich – a_2n=a_n – wskazuje na miejsca takich samych wyrazów, czyli oznacza, że jednakowe są, na przykład, wyrazy pierwszy, drugi, czwarty, ósmy,… (równe 1) albo trzeci, szósty, dwunasty, dwudziesty czwarty… (równe 2). Inna zależność – a_2n+1=a_n+a_n+1 umożliwia np. obliczenie 4035. wyrazu (56), jeśli znane są 2017. (31) i 2018. (25).

Niestety, niezależnie od rodzaju ciągu budowa autostrady z liczb wymiernych skazana jest na niepowodzenie. Można ją zacząć, ale nie sposób skończyć. Będzie „dziurawa”, bo między każdymi dwiema liczbami wymiernymi zawsze pozostaje wolne miejsce na nieskończenie wiele innych. Jeśli więc pojawiają się informacje o kłopotach związanych z budową jakiejś drogi szybkiego ruchu, to niewykluczone, że ich przyczyną jest użycie niewłaściwego surowca – wymiernego zamiast naturalnego.

Zadania

1. Do białych pól diagramu na rys. 9 należy wpisać dziewięć ułamków tworzących ciąg F₅ (wszystkie oprócz pierwszego i ostatniego). Ich rozmieszczenie powinno być takie, aby w wierszach i kolumnach powstały poprawne działania, tzn. wynikiem każdego powinna być liczba naturalna. Działania należy wykonywać po kolei, czyli bez uwzględniania pierwszeństwa mnożenia i dzielenia (uwaga ta dotyczy środkowej kolumny).

2. Ułamek 2/5 występuje w ciągach Fareya, poczynając od F₅ (rys. 4). W tym i w dwóch kolejnych ciągach F₆ i F₇ poprzedzony jest 1/3; dopiero w F₈ pojawiają się przed nim 3/8. Jaki ułamek poprzedza bezpośrednio 2/5 w ciągu F₁₀₀₀?

3. Jaki jest największy ułamek właściwy a/b w drzewie C-W, przy którym spełniony jest następujący warunek: trzy liczby – a, b i a+b – składają się w sumie z dziesięciu różnych cyfr? Przykład: najmniejszym ułamkiem o takiej własności jest 269/784 (a+b=1053).

Rozwiązania prosimy nadsyłać do 28 lutego br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 02/18, lub listownie: Świat Nauki, ul. Gintrowskiego 28, 02–697 Warszawa. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Richarda Mabeya Roślinny kabaret ufundowaną przez wydawnictwo Prószyński Media.

***

Rozwiązania zadań z numeru grudniowego

1. Liczba kolorów k>4 powinna być taka, aby wyrażenie (k³+2k)/3, określające liczbę kamieni pełnego kompletu domina trójkątnego, było kwadratem. Ten warunek spełniony jest tylko dla k=24.

2. Sposobów umieszczenia kamieni jest z pominięciem kolorów 81, a po uwzględnieniu trzech kolorów 81×6=486.

3. Tetraplikacja nie jest możliwa w przypadku heksamentu zwanego „motylem” – jedynym z czterema kątami 60 stopni. Układ czterech kolorów (A, B, C, D) na tworzących go kamieniach będzie taki, jak na rys. 10. Jedynym miejscem dla kamieni z trzema różnymi kolorami są w każdym z 4 „motyli” dwa środkowe kamienie – z sektorami oznaczonymi znakiem zapytania. Jednak jakikolwiek kolor nie pojawiłby się zamiast znaków zapytania, na jednym z tych kamieni znajdą się tylko dwa różne kolory, a zatem uda się ulokować tylko 4 kamienie trójkolorowe. Dla 4 pozostałych zabraknie miejsca.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę To nie jest miejsce do życia. Stalinowskie wysiedlenia znad Bugu i z Bieszczad Krzysztofa Potaczały, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Bartosz Chroł i Dariusz Pączkiewicz z Warszawy, Kajetan Siepielski z Poznania, Michał Stańczuk z Kobyłki, Andrzej Żołyński z Zielonej Góry.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.