Dołącz do czytelników
Brak wyników

Koło matematyczne

15 maja 2019

NR 38 (Maj 2019)

„Chińskie mutanty” liczb złożonych

0 146

Od końca ubiegłego roku moje artykuły w ramach „Koła”1–3 nieprzerwanie dotyczą pewnego starego zadania, pochodzącego z niegdysiejszego „Konkursu zadaniowego”, dziś już, niestety, nieistniejącego działu „Matematyki”. Zadanie to miało swój niezaprzeczalny urok, któremu sam uległem i w efekcie odkryłem najpierw dla siebie, a potem we wspomnianych wyżej artykułach także dla Czytelników (mam nadzieję) jego bogate tło teoretyczne.

W ostatnim z tych artykułów wstępnie omówiłem związki pewnego (prostszego) wariantu tego zadania z „bardzo klasycznym” twierdzeniem elementarnej arytmetyki (teorii liczb), tzw. Chińskim Twierdzeniem o Resztach. Dziś dokończę to omówienie i zaprzestanę w ten sposób, przynajmniej na jakiś czas, „męczenia” Czytelników tym zadaniem.

Dla krótkiego przypomnienia: urok wspomnianego zadania polegał na tym, że było ono stare – pochodziło z 1958 r.; miało „wielkiego” autora: – był nim prof. W. Sierpiński; miało „okrągły” numer – 1000; a jego treść była zwodniczo prosta – patrz niżej; ponadto bardzo długo pozostawało nierozwiązane. Rzeczywiście, jego rozwiązanie pojawiło się dopiero w 2007 r.4

I w końcu „wisienka na torcie” – rozwiązanie to było bardzo „nowoczesne”: zostało uzyskane z użyciem komputera. Ten fakt nie tylko dodawał temu zadaniu pewnego powabu nowoczesności, ale również kazał mi zapytać, czy rozwiązanie go bez użycia komputera, na bazie jakiejś teorii, jest w ogóle możliwe. Stąd wzięły się prostsze warianty tego zadania, które kolejno przedstawiałem i omawiałem w kilku wcześniejszych odcinkach „Koła”. Przy okazji można tu zauważyć, że nie jestem jedynym, który formułował jakieś uproszczone, aczkolwiek odmienne jego warianty5, 6.

Nie będę tu streszczał całości moich dotychczasowych rozważań (te można znaleźć w poprzednich artykułach1–3), ale dla ułatwienia Czytelnikowi lektury ponownie przytoczę treść samego zadania i jego prostszych, sformułowanych przez mnie wariantów. Tak więc zadanie, które nieustannie jest przedmiotem moich obecnych rozważań, w swoim pierwotnym sformułowaniu brzmiało następująco:

1000. Liczba złożona. Znaleźć liczbę złożoną, która pozostaje złożoną przy każdej zmianie którychkolwiek dwóch jej cyfr.

Niestety, jak wydaje się pokazywać to artykuł Jarnickiego i Żenczykowskiego4, w tej postaci zadanie to okazuje się być bardzo trudne do jakiegoś „teoretycznego” rozwiązania. W istocie jest ono zapewne za trudne do takiego (tzn. teoretycznego) rozwiązania go przez uczniów, nawet tych uzdolnionych matematycznie, np. olimpijczyków. Dlatego zaproponowałem zastąpienie powyższego oryginału zbiorem jego „uproszczonych analogonów” (definicję „analogonu” można znaleźć w literaturze7), w którym zmniejsza się liczbę cyfr podlegających zmianie do jednej, ale dopuszcza się podstawy zapisu cyfrowego odmienne od 103:

Liczba złożona (p, 1). Znaleźć liczbę złożoną, która pozostanie złożoną przy każdej zmianie którejkolwiek jej pojedynczej cyfry w zapisie przy podstawie p.

Okazuje się, że tak sformułowane zadanie jest dość łatwe do rozwiązania „teoretycznego”. Istotnie, szukamy liczby, która jest „bardzo” złożona, przy czym chcemy, żeby owa złożoność jakoś odzwierciedlała się w jej zapisie cyfrowym. Najprostszy pomysł sugeruje, by wyjść od liczby, której zapis przy zadanej podstawie p kończył się zerem, tzn. od liczby podzielnej przez p. 

Wtedy zmiany każdej cyfry innej niż ostatnia zachowują końcowe zero i poza kilkoma „zdegenerowanymi” przypadkami liczby n (np. gdy tylko jedna cyfra zapisu n jest różna od zera) otrzymana po takiej zmianie liczba również będzie podzielna przez p, a więc na ogół złożona.

Jedynym problemem, który będzie należało rozwiązać w przypadku liczby n podzielnej przez p, będzie więc zagwarantowanie, że również liczby powstałe z n przez zastąpienie jej ostatniej cyfry, a więc przez zastąpienie zera dowolną inną cyfrą zapisu o podstawie p, są złożone.

Zauważmy, że w istocie chodzi tu o liczby n + 1, n + 2, …, n + (p − 2), n + (p  – 1). Ponieważ niewiele wiemy tak o n, jak i o p, więc najprostszy pomysł na zapewnienie złożoności wszystkich liczb postaci n + i, i = 1, 2, …, p – 1 polegałby na zagwarantowaniu, że i dzieli n + i, tzn. i | n + i, i = 1, 2, …, p – 1. Oczywiście, w konsekwencji oznacza to, że n musi być podzielne przez każde i = 2, 3, …, p − 1. Ponadto początkowy wybór n polegał na tym, że liczba ta miała być podzielna również przez p. Tak więc chcemy, by n było takie, że i | n, i = 2, 3, …, p. A ponieważ cały czas staramy się operować możliwie prostymi środkami, zatem wybór n nie powinien obecnie przedstawiać większych trudności – bierzemy n = 2 ∙ 3 · …· (p – 1) · p = p!, tzn. zaczynamy od liczby n będącej silnią liczby p.

Rzeczywiście, przy takim wyborze n mamy p | n, 2 | n + 2, 3 | n + 3, …, (p – 1) | n + (p – 1). Zatem, o ile tylko p > 2, to wszystkie te liczby są złożone, tak jak tego chcieliśmy. Jednak, niestety, to za mało. Istotnie, w powyższym ciągu liczb złożonych brakuje liczby n + 1, a warunki zadania wymagają, aby i ta liczba była złożona.
Czytelnicy dobrze znający (elementarną) teorię liczb powinni w tym momencie przypomnieć sobie, że istnieje twierdzenie, które w zasadzie gwarantuje złożoność liczb postaci p! + 1. Chodzi o następujące twierdzenie, znane jako twierdzenie Wilsona8:
 

TWIERDZENIE (WILSONA)

Jeśli liczba p + 1 jest pierwsza, to (p + 1) | p! + 1..


Oczywiście, jest to tylko twierdzenie o podzielności p! + 1 przez p + 1, skąd niekoniecznie wynika złożoność p! + 1. Na przykład dla p = 2 mówi ono tylko, że (2 + 1) | 2! + 1, tzn. że 3 | 3, co jest oczywiście prawdą, mimo że 2! + 1 = 3 nie jest liczbą złożoną. Cóż, doznaliśmy pewnego niepowodzenia, albowiem twierdzenie Wilsona nie gwarantuje nam, że przy każdym p ciąg liczb p!, p! + 1, p! + 2, …, p! + (p – 2), p! + (p – 1) składa się wyłącznie z liczb złożonych, choć na mocy tego twierdzenia dla wielu p tak rzeczywiście jest. Jednak postać liczb tego ciągu podpowiada nam oczywiste wyjście z tej niekorzystnej dla nas sytuacji. To, czego potrzebujemy, to zestaw p kolejnych liczb złożonych. W powyższym ciągu mamy na pewno p – 2 takie liczby, są to liczby p! + 2, …, p! + (p – 2), p! + (p – 1). Jak to widzieliśmy powyżej, liczba poprzedzająca pierwszy wyraz tego ciągu, a więc liczba p! + 1, może nie być złożoną; jednak liczba następująca po ostatnim jego wyrazie, a więc liczba p! + p, na pewno jest złożona dla p > 1, a tylko takie p tu rozważamy, gdyż p jest podstawą zapisu pozycyjnego. Jednak kolejny wyraz tego ciągu ma postać p! + (p + 1) i znów nie musi być liczbą złożoną, na przykład dla p = 2 lub p = 4 nie jest.

Teraz powinno już być oczywiste, że gdybyśmy zaczęli nasz ciąg konstruować od liczby (p + 1)! zamiast od p!, to biorąc liczby (p + 1)! + 2, (p + 1)! + 3, …, (p + 1)! + p, (p + 1)! + (p + 1), otrzymujemy żądany ciąg p kolejnych liczb złożonych, jako że i | (p + 1)! + i, i = 2, 3, …, p, p + 1. Ba, obecnie powinno być równie oczywiste, że mamy w istocie następujące twierdzenie, które zawiera w sobie rozwiązanie wyżej sformułowanego zadania Liczba złożona (p, 1).
 

Twierdzenie 1

Niech m i k będą takimi liczbami naturalnymi, że:
 m ≥ 2k – 1 i k > 1. 

Wtedy
k | m! + k, (k + 1) | m! + (k + 1), …, (2k – 1) | m! + + (2k – 1), zatem ciąg liczb m! + i, i = k, …, 2k – 1 jest ciągiem k kolejnych liczb złożonych.


Wniosek
Niech p będzie podstawą zapisu pozycyjnego, tzn. niech p będzie liczbą naturalną, p > 1.

Niech ponadto m będzie dowolną liczbą naturalną ≥ 2p – 1. Wtedy liczba n = m! + p jest rozwiązaniem powyższego zadania Liczba złożona (p, 1).

Zauważmy, że powyższy wniosek dla każdego p > 1 generuje nieskończony ciąg rozwiązań. W szczególności dla p = 2, dowiadujemy się z niego, że np. liczby 3! + 2 = 8, 4! + 2 = 26 i 5! + 2 = 122 są (pierwszymi trzema) rozwiązaniami wspomnianego zadania. Aczkolwiek, ponieważ 8 = 10002, więc nie jest jasne, czy wolno nam zmienić wiodącą 1 tego zapisu na 0. Pozostałe dwa zapisy, tzn. 26 = 110102 i 122 = 11110102, nie stwarzają takiej trudności (dokładniejsze omówienie tej kwestii w „Matematyce” 1/20192). Zauważmy dalej, że ponieważ funkcja silnia bardzo szybko rośnie, więc jest właściwie pewne, że ciąg rozwiązań zawarty we wniosku jest „mocno dziurawy”. Istotnie, łatwe, bezpośrednie sprawdzenie pozwala przekonać się, że choć dla p = 2 najmniejszym rozwiązaniem zadania o liczbie złożonej odpornej na zmianę jednej cyfry jest n = 8, to jednak między 8 a 26 mamy jeszcze trzy takie rozwiązania, a mianowicie n = 14, n = 20 i n = 24. 

Skąd ten efekt? Cóż, tak to bywa z warunkami, które są tylko wystarczające, ale jednocześnie nie są konieczne na określoną własność – gubi się niektóre obiekty, które mają daną własność. W naszym przypadku powyższe Twierdzenie i Wniosek zawierają właśnie tylko takie warunki, które wystarczają do tego, by dana liczba n była odporna na jednomiejscowe „mutacje”1 swojego zapisu przy danej podstawie p. Dlatego, żeby trochę bardziej zacieśnić sieć, w którą próbujemy łowić rozwiązania naszego zadania, przyjrzymy się teraz dokładniej liczbom, które są jego rozwiązaniami, a więc trochę bliżej przeanalizujemy warunki konieczne na to, by n była odporna na wspomniane wyżej „mutacje”.

W tym celu wprowadzimy następujące, kolejne pojęcie pomocnicze:

Definicja
Niech p > 1 będzie podstawą systemu pozycyjnego i niech n będzie dowolną liczbą naturalną. Wtedy sygnaturą liczby n przy podstaw...

Pozostałe 70% treści dostępne jest tylko dla Prenumeratorów.

Co zyskasz, kupując prenumeratę?
  • 6 wydań czasopisma "Matematyka"
  • Dostęp do wszystkich archiwalnych artykułów w wersji online
  • Możliwość pobrania materiałów dodatkowych, testów i zadań
  • ...i wiele więcej!
Sprawdź

Przypisy