Cyfry o cyfrach, czyli biografistyka liczb

Jeżeli przyjąć – jak twierdzili Pitagorejczycy – że „wszystko jest liczbą”, to liczbę sensu stricto można by nazwać „nadliczbą”, bowiem będąc liczbą, jako pitagorejskie „wszystko”, jest nią także z definicji. Przejawów „nadliczbowości” bywa niekiedy więcej – na przykład w ciągu liczbowym, ponieważ każda liczba ma w nim nie tylko wartość, ale także numer, określający jej pozycję, oraz występuje w ciągu określoną liczbę razy.

Przed ponad półwieczem podobne rozważania zainspirowały amerykańskiego matematyka Solomona Golomba do wymyślenia ciągu liczb całkowitych dodatnich, łączącego wyżej wymienione nadliczbowe aspekty. Jego definicja jest bardzo krótka: każdy k-ty wyraz (a_k) równa się liczbie liczb k w ciągu. Innymi słowy, pierwszy wyraz równy jest liczbie jedynek, drugi – liczbie dwójek, trzeci – trójek itd. Jest jeszcze warunek gwarantujący jednoznaczność – ciąg jest niemalejący. Tworząc go, zaczynamy jedynką, co oznacza obecność w ciągu tylko jednej jedynki, więc następną liczbą powinna być przynajmniej dwójka. Czy a₂ może być większe niż 2? Nie, bo skoro ciąg jest niemalejący, to wówczas dwójka nie mogłaby się w nim w ogóle pojawić (niejako samoistnie powstaje warunek: każda następna liczba jest najmniejszą z możliwych). Zatem a₂=2, czyli dwójki są dwie, a więc także a₃=2, zaś to wskazuje na dwie trójki w rolach a₄ i a₅, co z kolei owocuje następnymi liczbami – trzema czwórkami i trzema piątkami itd. W rezultacie powstaje generowany jakby przez liczby porządkowe ciąg Golomba: 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, … Charakterystyczne, że każdy jego podciąg stały, obejmujący m kolejnych jednakowych liczb, generuje m nowych podciągów stałych. Wiedząc na przykład, że a₁₁=5 i a₁₂=6, powinniśmy po serii pięciu dziesiątek dopisać pięć jedenastek, a za nimi sześć dwunastek. Wartości następnych wyrazów są niejako narzucane hurtem przez poprzednie, a stałe podciągi są coraz dłuższe. Ciąg jest „bezwzględnie” nieskończony, tzn. nie można go przerwać, bo wtedy jego „ogon”, który stale się wydłuża, przestanie być zgodny z definicją. Przypomina to półprostą, która po ograniczeniu przestaje być sobą – staje się odcinkiem. Stąd ogólne określenia ciągu Golomba i podobnych: autobiograficzne, samoopisujące się albo krótko i nieco żartobliwie – samociągi.

Samociąg Golomba zadebiutował w 1966 roku w piśmie American Mathematical Monthly w zadaniu, polegającym na znalezieniu wzoru na jego k-ty wyraz. Ściślej, chodziło o wzór przybliżony, który okazał się prostszy, niż można by przypuszczać: a_k=φ^2–φ×k^φ–1, gdzie φ jest związaną ze złotym podziałem tzw. złotą liczbą równą (1+√5)/2. Dla k≤500 obliczone tym wzorem a_k prawie zawsze daje właściwą wartość po zaokrągleniu do liczby całkowitej. Wyjątków, gdy różnica przekracza 0,5, jest tylko pięć – dla k=273, 423, 437, 479 i 493. Dokładny, ale mniej praktyczny ze względu na ograniczony zakres jest poniższy wzór rekurencyjny – z trzystopniowym indeksem dolnym i oczywiście z warunkiem początkowym a₁=1.

W następstwie zainteresowania samociągiem Golomba wymyślono wiele podobnych ciągów oraz interesujących problemów i zadań, w tym także z pogranicza matematyki rekreacyjnej. Zaczątkiem jednego z najciekawszych były próby takiej modyfikacji ciągu, aby umożliwić jego skracanie, czyli niepowodujące sprzeczności obcinanie „ogona”. Kluczowymi okazały się dwie zmiany: rezygnacja z warunku, aby ciąg był niemalejący oraz uwzględnienie zera. Efekt końcowy takich zmian stanowiło zadanie opublikowane w roku 1967 na łamach Technology Review, czasopisma wydawanego przez Massachusetts Institute of Technology. Ciąg zastąpiła w nim liczba złożona z n cyfr, którą należało znaleźć, wiedząc, że: każda cyfra (a_i) oznacza liczbę cyfr i w tej liczbie (dla i=0, 1,…, n-1). Inaczej mówiąc, pierwsza cyfra (a₀) powinna być równa liczbie zer, druga (a₁) – liczbie jedynek, trzecia (a₂) – liczbie dwójek itd., aż do ostatniej (a_n-1), równej liczbie cyfr n. Ściśle rzecz biorąc, w pierwotnej wersji zadania chodziło o konkretną liczbę – 10-cyfrową (w systemie dziesiętnym dłuższa być nie może), czyli ostatnia cyfra miała oznaczać liczbę dziewiątek. Zadanie jest perełką, wymagającą nieco zakręconego logicznego myślenia, więc wkrótce wywędrowało w świat, trafiając w różnej formie do testów, konkursów i olimpiad matematycznych, głównie dla uczniów szkół średnich. Przyjęło się nazywać takie liczby autobiograficznymi; w skrócie liczby A. Spróbujmy znaleźć najkrótszą z nich.

Pierwsza cyfra nie może być zerem, bo byłoby to sprzeczne z warunkiem, by równała się ona liczbie zer. Zaczynamy zatem jedynką:

W tej sytuacji druga cyfra, określająca liczbę jedynek, nie będzie zerem ani jedynką, więc wpisujemy dwójkę:

Trzecia cyfra – równa liczbie dwójek – nie może być zerem (jest już jedna dwójka), ale może, a nawet powinna być jedynką ze względu na drugą cyfrę:

Pozostaje spełnić czwartą cyfrą, równą liczbie trójek, warunek postawiony przez pierwszą cyfrę: w liczbie powinno być jedno zero:

Gdyby w czwartej kratce wstawić a₃>0, odkładając zero na później, to zacząłby się tworzyć „ogon”, jak w ciągu Golomba, i liczby nie udałoby się zakończyć.

Zatem najkrótsza liczba ma cztery cyfry. Czy jednak 1210 jest jedyną 4-cyfrową liczbą A? Łatwo sprawdzić, zaczynając tworzenie liczby od dwójki (więcej niż 2 być nie może, bo powstałaby dłuższa liczba). Wówczas równie klarowna i elegancka ścieżka logicznego wnioskowania doprowadzi nas do drugiej 4-cyfrowej liczby: 2020. W podobny sposób udaje się wygenerować większe liczby A, ale jest to znacznie łatwiejsze, jeśli skorzystać z kilku ogólnych cech tych liczb. Dwie już znamy: liczba może być co najwyżej 10-cyfrowa i musi zaczynać się co najmniej jedynką. Poza tym suma cyfr równa jest liczbie cyfr, a ponieważ sumę tę tworzą tylko cyfry dodatnie, więc stąd kluczowy wniosek: suma cyfr dodatnich – z pominięciem pierwszej (a₀) – jest o jeden większa od liczby tych cyfr. Mamy więc sytuację, że p cyfr dodatnich daje sumę p+1. To oznacza, że jedna z nich jest dwójką, a pozostałe jedynkami. Zatem tworząc liczbę A, powinniśmy, po rozpoczęciu jej cyfrą a₀, wykorzystać jako kolejne cyfry wyłącznie następujące: a₀ zer, n-a₀-2 jedynek oraz jedną dwójkę. Pozostaje tylko ustalić ich konkretne miejsca, a to nie jest trudne, jeśli zauważyć, że a₃+a₄+…+a_n≤1, bo w przeciwnym wypadku powstałaby liczba ponad 10-cyfrowa. Zaczynając dwójką, można utworzyć liczbę A złożoną z więcej niż czterech cyfr. Wystarczy jako drugą cyfrę, czyli a₁, wpisać jedynkę. Warto spróbować. Liczby A można też tworzyć niejako od końca, korzystając z metody prób i błędów. W przypadku największej, 10-cyfrowej, zaczynamy od dziewiątki z dziewięcioma zerami:

Brakuje jedynki pod i=9, ale jeśli zastąpimy nią końcowe zero, to liczba zer zmaleje do ośmiu, więc trzeba będzie zmienić a₀ na 8, a końcową jedynkę przesunąć pod i=8:

Teraz błędem jest 0 pod i=1, ale nie można zmienić go na 1, bo wtedy w liczbie pojawią się dwie jedynki, więc trzeba wpisać 2, zmniejszyć a₀ do 7 i przenieść 1 z i=8 pod i=7:

Pora na końcową korektę błędnych cyfr pod i=0 i i=2, czyli zastąpienie zera pod i=2 jedynką oraz zmniejszenie a₀ do 6, a następnie przesunięcie jedynki spod i=7 pod i=6.

Cała kolekcja liczb A składa się z siedmiu eksponatów: 1210, 2020, 21 200, 3 211 000, 42 101 000, 521 001 000, 6 210 001 000. Jak widać, od czwartego eksponatu pojawia się schemat: [n–4]21[n–7 zer]1000. Dwie liczby 4-cyfrowe jakby rekompensują brak liczby 6-cyfrowej, który jednak łatwo wyjaśnić. Gdyby taka liczba istniała, to możliwe byłyby jej dwa schematy: a₀=2, a za nim odpowiednio rozmieszczone cyfry [00112] lub a₀=3 i [00012]. Niestety, żadna z najbliższych celu czterech możliwych liczb nie jest w pełni trafna (czerwone cyfry są błędne):

Zatem żadna z tych liczb nie jest liczbą A, ale wszystkie mogą być liczbami, które oznaczymy literą B. Są to tzw. liczby biograficzne albo krótko – biografie. Każda z nich stanowi „opis” jakiejś innej liczby na tej samej zasadzie, co opis samych siebie przez liczby autobiograficzne. Zatem każda cyfra (a_i) w liczbie B oznacza liczbę cyfr i w opisywanej liczbie Q (dla i=0, 1,…, n). Ściśle rzecz biorąc, konkretna liczba B może być „opisem” wielu liczb Q, bo kolejność cyfr w liczbie Q nie ma znaczenia. A czy każdej liczbie Q odpowiada dokładnie jedna B? Tegoroczne Q równe 2019, podobnie jak dowolna permutacja jego czterech cyfr, ma istotnie tylko jedną długą biografię – 1 110 000 001 (za kilka miesięcy zmieni się ona w krótką autobiografię – 2020). I tak jednoznacznie będzie dla każdego Q z dziewiątką. Gdy w Q dziewiątki brak, to n-cyfrową liczbę B zawsze można uzupełnić s zerami do (n+s)-cyfrowej, byleby n+s≤10. Aby zachować jednoznaczność, ustalmy więc, że liczba B oznacza tzw. biografię zamkniętą, czyli taką, która kończy się cyfrą dodatnią. Przyjmiemy także, że B i Q mogą zaczynać się zerem lub zerami, zwłaszcza że zero i tak zawsze pojawia się na początku B, gdy w Q zera brak.

Czy każda liczba naturalna ma swoją biografię? Oczywiście, nie. Ograniczenie stanowi system liczbowy, czyli w tym przypadku dziesiętny, w którym jest dziesięć cyfr. Jeśli w liczbie taka sama cyfra powtarza się więcej niż 9 razy, to jej biografia nie powstanie. Najmniejszą liczbą Q bez biografii jest więc 1111111111. Można też wskazać największą liczbę z biografią. Jest to 90-cyfrowy gigant, którego B=9 999 999 999.

Ciekawe zagadnienie dotyczące liczb biograficznych wiąże się z procesem iteracji, który polega na wielokrotnym powtarzaniu tego samego typu działania – zawsze na rezultacie poprzedniego działania. Skoro biografia liczby Q, oznaczona jako B₁, jest liczbą, to możemy wyznaczyć biografię biografii, czyli B₂, a potem jej biografię – B₃ itd. (oczywiście pod warunkiem, że jako B₁ lub B₂ nie pojawią się liczby z dziesięcioma jednakowymi cyframi; jest to możliwe, gdy np. w Q będzie dziesięć różnych cyfr – każda powtórzona tyle samo razy). W rezultacie powstanie ciąg kolejnych biografii B_n. Przykładem początkowego fragmentu takiego ciągu jest kontynuacja tegorocznej biografii (rys. 1).

Można się domyślić, że skoro liczb z biografiami jest skończona liczba, to każdy ciąg biografii będzie nieskończony w szczególny sposób – taki mianowicie, że w końcu jakaś liczba się w nim powtórzy i pojawi się cykl. Tak właśnie się dzieje, ale przed dotarciem do cykli warto rozważyć, jak w ciągu zmieniają się biografie. W tym celu wprowadzimy pojęcie wymiaru liczby, a w tym konkretnym przypadku – wymiaru biografii.

Liczba ma długość i szerokość. Długość (D) równa jest liczbie tworzących ją cyfr, a szerokość (S) jest o jeden większa od największej z jej cyfr (C). Natomiast wymiarem liczby (W) jest większa z wartości D i S. Dla danego B_n wymiar jest więc zawsze jeden, choć jest nim D lub S, zależnie od tego, co jest większe; ewentualnie D i S, jeśli D=S. Łatwo zauważyć, że długość każdej kolejnej biografii w ciągu równa jest szerokości jej poprzedniczki, czyli D(B_n)=S(B_n-1), zaś szerokość kolejnej biografii jest nie większa niż długość poprzedniej: S(B_n)≤D(B_n-1). Stąd wniosek, że wymiar biografii w ciągu na pewno nie rośnie, a raczej „jest skłonny” maleć. Nietrudno dowieść, że stopniowo zmniejsza się do co najwyżej pięciu. W tym celu wystarczy – przy założeniu, że wymiar ciągu stabilizuje się na wartości W≥6 – przenalizować zmiany wymiaru kolejnych biografii dla różnych wartości początkowych W i C biografii B_n (W=D lub S; C mniejsze albo równe W–1). Analiza prowadzi do sprzeczności: jeśli wymiar B_n jest większy od 6, to W maleje zawsze najdalej w trzech krokach, czyli dla B_n+3. Trudniej dowieść, że praktycznie W maleje do co najwyżej 4. Tak wynika z cykli, do których docierają ciągi biografii. Cykle są tylko dwa. Gdyby kontynuować tegoroczny, zapoczątkowany na rys. 1, dotarlibyśmy do cyklu długiego złożonego z 6 wyrazów: 22, 002, 201, 111, 03, 1001. Cykl krótki jest 2-wyrazowy (12, 011). Można do niego dotrzeć, zaczynając od zera, jedynki lub dwójki, ale gdy na początku będzie trójka lub dowolna większa liczba jednocyfrowa, nieuchronnie dotrzemy do długiego cyklu (rys. 2).

Wracając do opisywanych wyżej autobiografii: wszystkie one są biografiami otwartymi, tzn. kończą się przynajmniej jednym zerem. Wynika to z warunku, by długość liczby i jej biografii była taka sama. Postawmy inny, bardziej zakręcony warunek: długość biografii liczby X powinna być taka, aby biografia tej biografii była liczbą X. O parze liczb spełniających ten warunek była mowa przed chwilą. To 2-wyrazowy cykl (12, 011), ale czy to jedyny przykład? Okazuje się, że nie. Takich par biografii wzajemnych jest 38. Dwie następne to 130 i 1101 oraz 230 i 10 110, a najdłuższą tworzą 6 300 000 100 i 7 101 001 000 – przy założeniu, że biografie nie mogą być dłuższe niż 10-cyfrowe. Takie najdłuższe biografie nazywamy pełnymi. Co ciekawe, jeśli utworzymy ciąg biografii, zakładając, że każda powinna być pełną, czyli każdą będziemy uzupełniać zerami do 10-cyfrowej, to zawsze dotrzemy do 2-wyrazowego cyklu utworzonego przez powyższą najdłuższą parę biografii wzajemnych. Dla biografii bieżącego roku nastąpi to już w szóstym kroku.

ZADANIA

1. W n-cyfrowej liczbie (n≥2) można wyodrębnić co najwyżej n(n–1)/2 liczb k-cyfrowych (2≤k≤n). Na przykład, w liczbie 2019 są cztery liczby: 20, 19, 201, 2019; pomijamy zaczynające się zerem 01 i 019.

Zadanie polega na znalezieniu takiej 4-cyfrowej liczby X, której każda n-ta cyfra oznacza, ile w liczbie X jest liczb (przynajmniej dwucyfrowych) podzielnych przez n+1. A zatem pierwsza cyfra oznacza, ile w liczbie X jest liczb parzystych, druga – ile jest w niej liczb podzielnych przez 3, trzecia – ile jest w niej liczb podzielnych przez 4 itd. Ta sama wydzielona liczba może być podzielna przez więcej niż jedną liczbę.

Krótsze liczby o takiej własności są dwie: 10 i 121; dłuższych niż 4-cyfrowa prawdopodobnie nie ma.

2. W każdym polu obok strzałki (rys. 3) należy wpisać taką cyfrę (od 1 do 5), aby po wpisaniu wszystkich cyfr każda strzałka wskazywała na tyle różnych cyfr, jaka jest wartość umieszczonej obok niej cyfry (np. obok strzałki wskazującej na cyfry 2312 powinna być trójka, a obok strzałki wskazującej na 222 – jedynka). Osiem cyfr (w tym pięć różnych) zostało już ujawnionych, ale w zaszyfrowanej postaci. Różne litery odpowiadają różnym cyfrom. W rozwiązaniu wystarczy podać sumę cyfr na obu przekątnych.

3. W puste pola (rys. 4) należy wpisać takie cyfry, aby cyfra w każdej kratce oznaczała liczbę sąsiednich kratek z cyfrą nieparzystą. Sąsiednimi są nie tylko kratki stykające się bokiem ale także stykające się tylko rogiem. W rozwiązaniu wystarczy podać sumę cyfr na obu przekątnych.

4. W każdym wierszu i w każdej kolumnie (rys. 5) powinno się znaleźć dziewięć różnych cyfr, od 1 do 9; w białych kratkach – po jednej cyfrze, w szarych – po dwie, tworzące liczby dwucyfrowe. Suma cyfr w rzędzie wskazanym przez strzałkę przy szarym polu musi być równa liczbie w tym polu. W rozwiązaniu wystarczy podać sumę dwucyfrowych liczb, które znajdą się w szarych polach.

Rozwiązania prosimy nadsyłać do 31 sierpnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 8/19. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Elastyczny mózg. Kreatywne myślenie w czasach niepewności i chaosu Leonarda Mlodinowa ufundowaną przez wydawnictwo Prószyński Media. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem Konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji Konkursu.

Regulamin Konkursu jest dostępny na stronie www.swiatnauki.pl

***

Rozwiązania zadań z numeru czerwcowego

1. Grupa I – kamienie 0-1,2-4, 2-5; działania: 52×2=104, 10+42=52 lub 0+1+24=25. Grupa II – kamienie – 1-2, 4-5, 4-6; działania: 54×4=216, 12+44=56 lub 21+44=65.

2. Dodawanie: 1+1+4+4+5+325+320=660 (trzy dublety
w „kominie” można zamieniać miejscami).

3. Dodawanie 4×3, którego nie można ułożyć z domina dwójkowego: 1102+1100=2202.

4. Dodawanie (dodamino) 10×3 z domina czwórkowego
z minimalną sumą (bez zera na początku):

1001031210+1022313234=2023344444.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Tima Jamesa Spal tę wodę. Jak zmienić wodę w ogień, zrobić diament z masła i inne cuda z krainy pierwiastków ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Mariusz Figiel z Łodzi, Bartłomiej Goldman z Nadarzyna, Paweł Hołownia z Ożarowa Mazowieckiego, Wojciech Kawula z Gniezna, Maciej Mitręga z Raszyna.