Afiliacja: Wydział Matematyki Stosowanej, Politechnika Śląska
Dziwaczna i zachwycająca chemia audioaktywnego rozkładu. Jedną z popularniejszych rekreacyjnych sekwencji liczbowych jest ciąg look-and-say wprowadzony przez Johna Conwaya w 1986 roku: \[1,\,11,\,21,\,1211,\,111221,\,312211,\,13112221,\,\ldots\] Czytelnikowi, który widzi powyższy ciąg po raz pierwszy, sugeruję na chwilę zatrzymać lekturę i zastanowić się, jaka powinna być następna liczba.
J. H. Conway, The weird and wonderful chemistry of audioactive decay.
Nazwa look-and-say idealnie oddaje istotę ciągu – każdy kolejny wyraz powstaje przez opisanie tego, co widzimy, patrząc na wyraz poprzedni. Przykładowo, patrząc na piąty wyraz ciągu (111221), widzimy trzy (3) jedynki (1), dwie (2) dwójki (2) i jedną (1) jedynkę (1), więc kolejny wyraz to 312211. Rzeczona autodeskrypcyjność stanowi największy urok ciągu Conwaya: wyznaczenie kolejnych wyrazów nie ma nic wspólnego z niedostępną dla niewtajemniczonych matematyką wyższą. Można się nawet pokusić o przypuszczenie, że spostrzegawczy laik ma większe szanse na odgadnięcie reguły rządzącej ciągiem niż doświadczony matematyk. Moda na ciąg Conwaya nie ominęła Delty, na łamach której w ostatnich latach pojawiły się warte uwagi teksty traktujące o look-and-say: w \(\Delta^{11}_{21}\) o najważniejszych własnościach pisze Wojciech Czerwiński, a w \(\Delta^1_{23}\) można znaleźć bardziej szczegółowy tekst Karola Gryszki.
Sam John Conway przyznał, że nie udało mu się odgadnąć reguły rządzącej ciągiem, gdy ten został mu przedstawiony w formie zagadki przez jednego ze studentów. Należy tutaj dodać, że look-and-say jest nazywany ciągiem Conwaya, ponieważ rzeczony matematyk jako pierwszy ten ciąg zbadał, a nie odkrył.
Jak dotąd jest dobrze. Bohaterem niniejszego artykułu jest pewien mniej znany ciąg autodeskrypcyjny, który zadebiutował w OEIS (The On-Line Encyclopedia of Integer Sequences – bardzo przydatna baza ciągów) w 2005 roku jako wytwór Erica Angeliniego – belgijskiego pasjonata matematyki rekreacyjnej. Zanim przedstawimy sam ciąg, przyjmijmy następującą konwencję dekodowania liczb. Niech \(N\geq10.\) Liczba powstała przez ,,odcięcie” ostatniej cyfry liczby \(N\) (czyli część całkowita liczby \(N/10\)) będzie oznaczać ilość, a ostatnia cyfra liczby \(N\) (czyli reszta z dzielenia \(N\) przez 10) będzie oznaczała samą siebie, czyli – nomen omen – cyfrę. Liczbę \(N\) dekodujemy jako odpowiednią ilość tej cyfry.
Przykładowo 26 dekodujemy jako dwie cyfry ,,6”, a 8945 jako osiemset dziewięćdziesiąt cztery cyfry ,,5”.
Sekwencja true-so-far jest rosnącym ciągiem liczb całkowitych, którego pierwszym elementem jest liczba 10, a każdy kolejny to najmniejsza liczba, która po zdekodowaniu poprawnie opisuje liczbę wystąpień danej cyfry we wszystkich dotychczasowych elementach ciągu (łącznie z wprowadzonym). Zatem drugim elementem ciągu nie może być liczba 11 (11 dekodujemy jako jedna ,,jedynka”, podczas gdy ciąg \((10,11)\) zawiera trzy jedynki!), natomiast liczba 12 tak (ciąg \((10,12)\) faktycznie zawiera jedną cyfrę ,,2”). Sto początkowych elementów ciągu true-so-far to: \[\begin{array}{ccccccccccccc} 10,&12,&13,&14,&15,&16,&17,&18,&19,&20,&23,&24,&25,\\ 26,&27,&28,&29,&30,&34,&35,&36,&37,&38,&39,&40,&45,\\ 46,&47,&48,&49,&50,&56,&57,&58,&59,&60,&67,&68,&69,\\ 70,&78,&79,&80,&89,&90,&102,&103,&104,&105,&106,&107,&108,\\ 109,&112,&113,&114,&115,&116,&117,&118,&119,&123,&124,&125,&126,\\ 127,&128,&129,&134,&135,&136,&137,&138,&139,&145,&146,&147,&148,\\ 149,&156,&157,&158,&159,&167,&168,&169,&178,&179,&180,&189,&190,\\ 192,&193,&194,&195,&196,&197,&203,&204,&205. \end{array}\] Ostatnia z zapisanych powyżej liczb, 205, informuje, że w tabeli znajduje się dokładnie dwadzieścia cyfr ,,5”.
Czy rozpatrywany ciąg jest nieskończony? Odpowiedź uzyskamy, łącząc liczenie na palcach (komputerowych) z prostym rozumowaniem.
Jak się okazuje, po otrzymaniu dwa tysiące dwudziestego czwartego elementu ciągu true-so-far – 8945 – liczby wystąpień poszczególnych cyfr są następujące: \[\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline 0&1&2&3&4&5&6&7&8&9\\\hline 624&822&834&864&874&894&779&697&697&617\\\hline \end{array}\]
Kolejny, dwa tysiące dwudziesty piąty element ciągu musi mieć zakodowaną liczność jednej z dziesięciu cyfr. Zauważmy, że nie może on odnosić się do cyfry ,,5”: liczba 8955 nie pasuje, gdyż zwiększa liczbę piątek o dwie, a nie o jedną; podobnym argumentem odrzucamy liczbę 8965 (oczywiście większych kandydatów nie ma sensu rozpatrywać).
Analogicznie można uzasadnić, że kolejny element nie może mieć na końcu cyfry 8. Pozostali kandydaci to: \[6250,\,8231,\,8352,\,8653,\,8754,\,7806,\,6987,\,6189\mbox{ i }6199,\] jednak odrzucamy każdą z tych propozycji ze względu na założenie, że rozpatrywany ciąg ma być rosnący – każda z dziewięciu powyższych liczb jest mniejsza od 8945. Ostatecznie ciąg true-so-far ma dokładnie 2024 elementy.
Pod koniec powyższego uzasadnienia skończoności powołaliśmy się na monotoniczność rozpatrywanego ciągu. Jak się okazuje, true-so-far ma skończoną liczbę elementów również w wariancie, w którym nie zakładamy, że jest rosnący. Jednak liczba elementów tej wersji ciągu przez długi czas nie da nam dobrego pretekstu do przedstawienia go na łamach Delty – zgodnie z informacją zamieszczoną w bazie OEIS wynosi ona \(5\,191\,475.\)