Z początku na koniec, czyli wokół zagadki Dysona

Zamieszczony w tej rubryce przed trzema laty artykuł o liczbach kolistych rozpoczynał się wariantem zagadki kojarzonej zwykle z nazwiskiem Freemana Dysona:

(A) Która liczba X po przestawieniu jej ostatniej cyfry na początek zwiększa się k-krotnie?

Dyson jest bohaterem anegdoty, opisującej wydarzenie sprzed kilkunastu lat, kiedy to w ciągu kilku sekund, niczym komputer, podaje rozwiązanie tej zaprezentowanej przez innego uczonego zagadki (dla k=2) – jakby wcześniej sam ją wymyślił. Dlatego bywa ona nazywana zagadką Dysona, choć po raz pierwszy pojawiła się na łamach „American Mathematical Monthly” w roku 1941, ale nie była szerzej znana. Związany z tą zagadką ogólniejszy temat, dotyczący liczb kolistych, był poruszany już na początku XIX wieku w pracach „księcia matematyków” Gaussa i „ojca komputerów” Babbage’a w kontekście „generatorów” liczb kolistych, którymi są ułamki okresowe.

Tekst zagadki Dysona warto nieco zmodyfikować w celu ograniczenia liczby rozwiązań. Po pierwsze, należy dodać, że chodzi o liczbę najmniejszą. Po drugie, wypadałoby zastrzec, że liczba X nie może zaczynać się zerem, co w tym przypadku jest istotne. Można jednak tego zastrzeżenia uniknąć, „odwracając” zagadkę:

(B) Która najmniejsza liczba X po przestawieniu jej pierwszej cyfry na koniec zmniejsza się k-krotnie?

Teraz zero na początku traci sens także dlatego, że przestawienie go na koniec zawsze zwiększa liczbę. Jeśli zaś zero będzie drugą cyfrą i pojawi się po przeniesieniu pierwszej cyfry na początku nowej liczby X’, to zostanie pominięte. Gdyby w wersji (A) zagadki dopuścić X zaczynające się zerem, to k mogłoby być równe 10^m, a X składałoby się z cyfry poprzedzonej m zerami (np. k=10, X=01 lub k=1000, X=0001).

Na wstępie ciekawostka. Są dwie dwucyfrowe liczby X bliskie „ideału”, tzn. takie, że X±1=kX’. To 41 (k=3) i 73 (k=2); są też trzycyfrowe – 607 (k=8), 631(k=2).

Rozwiązywanie wersji (B) wypada zacząć od zapisania liczb większej X i mniejszej X’ jako: X=10^s-1b+a, X’=10a+b, gdzie b jest przestawianą cyfrą, a – liczbą X lub X’ pozbawioną b, s – liczbą cyfr tworzących X. Ponieważ X=kX’, więc

10^s-1b+a=k(10a+b)

Po przekształceniu:

(I) a(10k–1)=b(10^s-1–k)

Teraz dla danego k należy znaleźć najmniejsze s takie, dla którego b-ta wielokrotność wyrażenia 10^s-1–k (1≤b≤9) dzieli się przez 10k-1. Bez komputerowego wsparcia szukanie może być długie i żmudne. Na przykład, jeśli k=6, to s=58, czyli dopiero 10⁵⁷–6 dzieli się przez 59, a iloraz jest 56-cyfrowy. Względnie krótkie poszukiwania są w przypadku k=4, bo wtedy s=6 ((10⁵–4):39=2564). Po podstawieniu k i s do powyższego wzoru otrzymamy:

39a=99996b

Stąd do rozwiązania dla k=4 jest już bardzo blisko. Wystarczy znaleźć najmniejsze b, dla którego 10a będzie przynajmniej 5-cyfrowe. Tak jest już dla b=1; wówczas a=2564, X=10⁵+2564=102564, X’=25641. Dla b=2 a=5128, X=2×10⁵+5128=205 128, X’=51 282. Od b=4 zaczynają się 6-cyfrowe wartości X’, odpowiadające podanym w tabeli 1 wartościom X, które są wielokrotnościami najmniejszego X.

Oczywiście, dla k=4 są też dłuższe rozwiązania X niż 6-cyfrowe. Skoro bowiem przez 10k–1 podzielne jest 10^s-1–k, to podzielne jest także n(10^s-1–k). W konsekwencji rozwiązaniem jest każda konkatenacja (zlepek) liczb 6-cyfrowych z tabeli, czyli np. 410256410256410256… Zatem rozwiązań jest nieskończenie wiele.

Warto zwrócić uwagę, że w tabeli 1 trzy pary liczb X – dla b=1 i 4, 3 i 9 oraz 5 i 8 – są względem siebie koliste, czyli po zapisaniu jednej równomiernie na okręgu można z tego okręgu odczytać drugą liczbę z tej samej pary, zaczynając od innej cyfry. Co ciekawe, „totalna” kolistość występuje w rozwiązaniu dla k=2. Wtedy najkrótszych 18-cyfrowych rozwiązań jest dziewięć i wszystkie można zapisać w postaci pierścienia złożonego z 18 cyfr-ogniw (rys. 1). Każde rozwiązanie zaczyna się od czerwonej cyfry i odczytywane jest wokół pierścienia zgodnie z ruchem wskazówek zegara – aż do zaliczenia kompletu cyfr. Najmniejsze to 105263157894736842 – po przeniesieniu jedynki na koniec i usunięciu początkowego zera powstaje liczba dwukrotnie mniejsza.

Zdecydowana większość najmniejszych rozwiązań X dla różnych k to liczby giganty. Wspomniana 58-cyfrowa dla k=6 jest maluchem przy k=38 (X liczy 378 cyfr) lub k=102 (1018-cyfrowe X). Rozwiązania nie dłuższe niż 6-cyfrowe są w tym gronie jak rodzynki w cieście. Poza „sztampowymi” dla k=10^m (X=10^m, X’=1) oraz już wymienionym 102 564 (k=4) takich rarytasów jest tylko osiem (tab. 2).

Wersję (B) zagadki Dysona można zawęzić:

(C) Która najmniejsza liczba X, zaczynająca się cyfrą k, po przestawieniu tej pierwszej cyfry na koniec zmniejsza się k-krotnie?

Po takim uściśleniu rozwiązywanie dla danego k staje się automatyczne, choć zwykle bardzo żmudne. Sprowadza się bowiem do odtwarzania mnożenia, w którym mnożnik, ostatnia cyfra mnożnej i pierwsza cyfra iloczynu są równe k (na rys. 2 k=8), a rząd kropek w mnożnej i iloczynie oznacza ten sam ciąg cyfr. Obliczane od końca cyfry iloczynu są przenoszone do mnożnej, by działanie mogło być kontynuowane na zasadzie przypominającej sprzężenie zwrotne (rys. 2b). Koniec rekonstrukcji następuje w momencie, gdy na początku mnożnej pojawia się „wolna” ósemka, czyli niebędąca jednostką liczby dwucyfrowej (rys. 2c). Rozwiązaniem, czyli liczbą X, jest oczywiście iloczyn. Najmniejsze X łatwo wskazać w tabeli 1.

Zadanie można też rozwiązywać, korzystając z wzoru (I), po zastąpieniu w nim k przez b:

(II) a(10b–1)=b(10^s-1–b)

Wersję (B) nietrudno uogólnić:

(D) Która najmniejsza liczba X, zaczynająca się liczbą b, zmniejsza się k-krotnie po przestawieniu b na koniec X?

W wersji (B) liczba b była jednocyfrowa. Tym razem może się składać z dowolnej liczby cyfr. Teoretycznie wersja (D) stanowi więc zagadnienie obejmujące nieskończenie wiele bliźniaczych zagadek, ale praktycznie w matematyce rekreacyjnej temat ograniczony jest do b złożonych z dwu cyfr.

Rozwiązywanie tego zadania dla dwucyfrowej liczby b prowadzi, podobnie jak w wersji (B), do wzoru:

(III) a(100k–1)=b(10^s-2–k)

I podobnie jak poprzednio dla danego k trzeba znaleźć takie najmniejsze s, dla którego n-ta wielokrotność wyrażenia 10^s-2–k (10≤n≤99) dzieli się przez 100k–1. Tym razem ze względu na duży zakres n skorzystanie z komputera wydaje się niezbędne, a wartość X jest z reguły gigantyczna. Krótkie, 6-cyfrowe liczby X są tylko dwie – dla k=3 (230 769) i k=4 (571 428).

Ograniczając wersję (D), można utworzyć analogiczną do (C) kolejną wersję:

(E) Która najmniejsza liczba X, zaczynająca się (dwucyfrową) liczbą b, zmniejsza się b-krotnie po przestawieniu b na koniec X?

Teraz wzór końcowy ma postać:

(IV) a(100b–1)=b(10^s-2–b)

Każda liczba całkowita X, wynikająca pośrednio z tego wzoru, składa się z co najmniej kilkudziesięciu cyfr, a większość z kilkuset lub kilku tysięcy. To skutecznie zniechęca do korzystania z „automatycznej” metody, polegającej na rekonstrukcji mnożenia – jak na rys. 2. Jedno z krótszych X, dla b=19, liczy s=30 cyfr: 19100052659294365455502896261, a bodaj najmniejsze, 24-cyfrowe, jest dla b=46: 460100021743857360295716.

„Odwrócenie” oryginalnej zagadki Dysona w wersjach od (B) do (E) można uznać za jakby podwójne. Dwie zmiany dotyczą: kierunku przemieszczania cyfry (liczby) oraz odwrócenia relacji większa-mniejsza. Warto jednak zastanowić się nad skutkami pojedynczego odwrócenia, a więc na przykład tylko kierunku. Rezultatem będzie zadanie:

(F) Która najmniejsza liczba X po przestawieniu jej pierwszej cyfry na koniec zwiększa się k-krotnie?

Efekty tej zmiany są zaskakujące w porównaniu z poprzednimi wersjami, jeśli chodzi o liczbę rozwiązań.

Jeżeli liczba X składa się z s cyfr i zaczyna cyfrą b, to:

10(X–b×10^s-1)+b=kX

Po przekształceniu:

X(10–k)=b(10^s–1)=9b×J_s

gdzie J_s jest liczbą złożoną z s jedynek.

Łatwo sprawdzić, że dla każdego k>1 i k≠3 X będzie liczbą złożoną z s jednakowych cyfr, więc nie zwiększy się po przestawieniu pierwszej cyfry na koniec. Natomiast gdy k=3, to 7X=b(10^s–1), zaś 10^s–1 jest podzielne przez 7 tylko wtedy, gdy s jest wielokrotnością sześciu. Zatem najmniejsze X=b(10⁶–1)/7, a skoro k=3 i s=6, to b=1, czyli X₁=142 857. Dla b=2 jest jeszcze sześciocyfrowe X₂=285 714. Każda większa liczba X jest 6n-cyfrową konkatenacją liczb X₁ lub X₂. Nietrudno też zauważyć, że X₁ i X₂ są dla k=2 rozwiązaniami jeszcze jednej wersji zagadki Dysona, analogicznej do wersji (D):

(G) Która liczba X, zaczynająca się dwucyfrową liczbą b, zwiększa się k-krotnie po przestawieniu b na koniec X?

Jest jeszcze trzecie „bliźniacze” rozwiązanie tej zagadki – 428 571. Więcej rozwiązań, poza kontaminacyjnymi, nie ma, ponieważ zaczynające się zerem (np. 076923, k=9) – pomijamy.

Zadania

1. Należy znaleźć wszystkie 3-cyfrowe liczby X o następującej własności: po przestawieniu pierwszej cyfry na koniec powstaje liczba o 1 większa lub o 1 mniejsza od wielokrotności X.

2. Która najmniejsza liczba X, zaczynająca się dwucyfrową liczbą b, zwiększa się k-krotnie po przestawieniu b na koniec X z równoczesną zmianą kolejności cyfr w liczbie b?

3. Jeśli liczbę pⁿ+1 zapisać wspak, to powstanie liczba p^m+1. Jaką liczbą jest p, jeżeli m≠n? Dla m=n rozwiązań jest nieskończenie wiele, np. 2⁵+1=33 lub 5⁴+1=626.

Rozwiązania prosimy nadsyłać do 31 stycznia br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 01/22. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Michio Kaku Kosmos Einsteina. Jak wizja wielkiego fizyka zmieniła nasze rozumienie czasu i przestrzeni 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 listopadowego

1. Na przekątnych jest 6 skalnych pól (rys. 3).

2. Na przekątnych także jest 6 skalnych pól (rys. 4).

3. Liczba skalnych pól – 21 (rys. 5).

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Franka Wilczka Podstawy. Dziesięć kluczy do rzeczywistości, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Krzysztof Jawor z Krynicy-Zdroju, Mariusz Jędrzejewski z Wilkowej Wsi, Krystyna Kruszy z Olkusza, Kamil Zaborowski z Suwałk, Szczepan Zdybowicz z Warszawy.