nauki ścisłe
Autor: Marek Penszko | dodano: 2013-12-17
Co następne. Mała trwałość wielkich liczb

W testach na inteligencję i w zbiorkach łamigłówek nierzadko pojawiają się ciągi. Niektóre z nich na tyle często i od tak dawna, że można je uznać za „klasyczne”. Do takich należy następujący:

77, 49, 36, 18, …

Jak zwykle w tego typu zadaniach, chodzi o odkrycie reguły, rządzącej ciągiem i wpisanie kolejnego wyrazu. W tym przypadku szukana liczba kończy ciąg, a zasada jego budowy jest prosta: każdy następny wyraz otrzymujemy, mnożąc przez siebie cyfry poprzedniego; na końcu pojawi się więc 8.

Zapewne osoba, która jako pierwsza wpadła na pomysł takiego ciągu „iloczynowego”, a z pewnością niejedna, która się z nim zetknęła, próbowała utworzyć choć o jeden wyraz dłuższy ciąg oparty na takiej zasadzie. I szybko dochodziła do wniosku, że sprawa nie jest taka prosta, jak by się mogło w pierwszej chwili wydawać. W tym przypadku nie ma szybkiej logicznej metody, umożliwiającej znalezienie najmniejszej liczby, która doprowadziłaby do jednocyfrowej przynajmniej w pięciu krokach. Szukając jej, trzeba postępować jak komputer, czyli sprawdzać kolejne, coraz większe liczby. Część z nich można wprawdzie z góry wyeliminować, np. te z zerem, jedynką i niektóre z piątką (dlaczego?), co ułatwia zadanie, ale w gruncie rzeczy niewiele zmienia, ponieważ nie istnieje żaden ogólny schemat „przełożenia” zbioru cyfr, tworzących daną liczbę, na cyfry tworzące ich iloczyn.

Temat takich ciągów pierwszy poruszył w 1973 roku Neil Sloane, matematyk z Bell Labs, w artykule, który ukazał się na łamach magazynu poświęconego rozrywkom matematycznym. Bodźcem do napisania go były zaskakujące rezultaty szukania najdłuższych ciągów iloczynowych za pomocą komputera. Sloane sprawdził wszystkie liczby do 100 oktylionów (1050), znajdując najmniejsze (a1[min]), rozpoczynające ciągi złożone z n = 5, 6, 7… itd. wyrazów. Poniższa tabela obejmuje także najmniejsze liczby zaczynające krótsze ciągi, poczynając od n=2 (choć w istocie dwa wyrazy, to jeszcze nie ciąg), a w trzeciej kolumnie podane są ich ostatnie wyrazy an.

Trudno się dziwić, że znalezienie bez komputera ciągu 6-wyrazowego nie było proste, skoro zaczyna się on dopiero od 679:

679→ 378→ 168→ 48→ 32→ 6

Każda permutacja cyfr 6, 7 i 9 i każde jej uzupełnienie dowolną liczbą jedynek rozpocznie oczywiście taki sam ciąg. Można by więc zapytać, jaka nieutworzona w ten sposób następna liczba zaczyna ciąg 6-wyrazowy. Okazuje się, że od 679 jest do niej bardzo blisko, a rzut oka na tabelę stanowi podpowiedź, bo… roi się w niej od ósemek.

Właściwie rozważania o ciągach iloczynowych wypadałoby zacząć od udowodnienia, że każdy jest malejący, czyli zawsze zakończy się liczbą jednocyfrową. Dowód można ująć w jednym zdaniu: liczba złożona z c cyfr i zaczynająca się od a jest większa niż a×10c-1, czyli większa od iloczynu jej cyfr, który nigdy nie przekroczy a×9c-1, bo każda cyfra może być co najwyżej dziewiątką. Iloraz obu tych wartości – (9/10)c-1 określa, jaką co najwyżej część liczby stanowi iloczyn jej cyfr. Na przykład dla c=10 będzie to około 0,4, czyli iloczyn także może być 10-cyfrowy, ale dla c=50 tylko niespełna 0,006, więc po pomnożeniu ubędą co najmniej dwie cyfry. Z dalszych bardziej skomplikowanych obliczeń i rozważań wynika, że ciąg iloczynowy, zaczynający się od liczby c-cyfrowej, nie może składać się z więcej niż c+3 wyrazów. Korzystając z komputera, Sloane potwierdził praktycznie słuszność tego wniosku, a przy okazji odkrył zdumiewającą własność: jeśli pierwszy wyraz nie przekracza 1050, to żaden ciąg nie składa się z więcej niż 12 wyrazów. Najdłuższy, zaczynający się od najmniejszej liczby (ostatnia w tabeli), wygląda tak:

277777788888899→ 4996238671872→ 438939648→ 4478976→ 338688→ 27648→ 2688→ 768→ 336→ 54→ 20 → 0.

Sloane wprowadził pojęcie trwałości liczby, która jest o jeden mniejsza od liczby wyrazów, zaczynającego się od niej ciągu iloczynowego, czyli równa jest liczbie kroków (odstępów między wyrazami). Kojarzy się to z trwałością jąder atomowych, ale – w przeciwieństwie do jąder – nietrwałe są wszystkie liczby. Bardziej trwałe oczywiście te, które zaczynają dłuższe ciągi; można nawet określić ich „okres połowicznego rozpadu”, czyli liczbę kroków, po której stają się o połowę krótsze. Na podstawie obliczeń Sloane postawił hipotezę, że trwałość liczby nie może być większa od 11. Przed trzema laty na Uniwersytecie w Perth w Australii sprawdzono wszystkie liczby do 10333, a w ubiegłym roku w laboratorium informatycznym francuskiego Uniwersytetu Lille I – do 10500. Komputery nie mnożyły oczywiście cyfr każdej liczby, bo trwałoby to do końca świata i jeden dzień dłużej. Skorzystano z serii sprytnych trików, radykalnie upraszczających obliczenia i czas pracy urządzeń, czyli:

– pominięto liczby, których trwałość jest nie większa od 2, a więc wszystkie z przynajmniej jednym zerem albo zawierające piątkę i cyfrę parzystą;

– nie uwzględniono liczb z jedynkami, bo ich obecność nie wpływa na trwałość;

– cyfrę 4 zastąpiono parą 22, 6 – parą 23, 8 – tercetem 222, 9 – duetem 33; żadne z tych zastępstw nie zmienia trwałości;

– ponieważ dla trwałości kolejność cyfr nie ma to znaczenia, uwzględniano tylko niemalejące ciągi cyfr.

W efekcie do sprawdzenia pozostała „garstka” ciągów cyfr, odpowiadających dwu schematom:

a) 222…2333…3777…7

b) 333…3555…5777…7

Wniosek z obliczeń komputerowych okazał się taki, jakiego należało się spodziewać: trwałości większej niż 11 nie stwierdzono. Byłoby zresztą niemal sensacją, gdyby pojawiło się 12, bowiem już z obliczeń Sloane’a wynikało, że wraz ze wzrostem zakresu liczb ich średnia trwałość zmniejsza się. Wiele wskazuje na to, że gdy górna granica zakresu liczb dąży do nieskończoności, to ich średnia trwałość zmierza do 1. Zdarzają się wprawdzie „wyskoki”, które stwarzają nadzieję, ale ostatnia trwałość równa 10 pojawia się przy dwóch liczbach 29-cyfrowych – 2193476 i 2432075 (Xn oznacza ciąg złożony z n cyfr X, stanowiący część liczby). Dalsze wyskoki są coraz niższe. Trudno się temu dziwić, bo im większa liczba, tym większe prawdopodobieństwo, że w iloczynie jej cyfr pojawi się zero. Można założyć, że od pewnego momentu jest to prawie pewne.

Paul ErdÖs, jeden z najwybitniejszych matematyków XX wieku, po zapoznaniu się z pojęciem trwałości liczb zaproponował drobną, ale istotną modyfikację sposobu tworzenia ciągów iloczynowych: pomijanie zer w iloczynach przy wykonywaniu kolejnych mnożeń. Ich pojawienie się nie oznacza więc nagłego zakończenia ciągu i może on wyglądać na przykład tak:

99999→ 59049→ 1620→ 12→ 2

Nie wiadomo, czy trwałość Erdösa ma jakąś maksymalną wartość (Erdös uważał, że tak). Dotychczas znaleziono liczby, dla których sięga 20, ale są one tak gigantyczne, że możliwości komputerów i koszt ich pracy ograniczają dalsze poszukiwania.

Poniższe zadania (2 i 3) dotyczą ciągów tworzonych metodą Sloane’a.

1.         Ciągi jako testy lub łamigłówki są często niejednoznaczne, czyli można znaleźć więcej niż jedno rozwiązanie. Dotyczy to także ciągu zaczynającego ten artykuł. Gdyby jego piątym wyrazem było 9, to jaki byłby szósty wyraz, czyli następny w ciągu: 77, 49, 36, 18, 9, …? Odpowiedź należy oczywiście uzasadnić, czyli podać regułę budowy ciągu.

2.         W pochodzącej ze znanego kryminału Agathy Christie złowróżbnej wyliczance o dziesięciu małych Murzyniątkach, ubywa jednego z nich w każdej kolejnej zwrotce. Liczbowym odpowiednikiem takiej „zabawy” mógłby być ciąg iloczynowy, zaczynający się od 10-cyfrowej liczby złożonej z różnych cyfr, w którym każdy następny wyraz byłby także różnocyfrowy, ale krótszy o jedną cyfrę. Jest to oczywiście niemożliwe, czyli należałoby zacząć od mniejszej liczby „murzynków”.

 

      Z ilu wyrazów składa się najdłuższy ciąg iloczynowy, zaczynający się liczbą złożoną z różnych cyfr, w którym każdy następny wyraz różni się od poprzedniego tylko brakiem jednej cyfry i ewentualnie przestawieniem pozostałych? Jaka jest najmniejsza liczba, zaczynająca taki ciąg?

3.         W dwóch parach liczb cyfry zastąpiono kratkami. Druga liczba w każdej parze powstała tak, jak kolejny wyraz  w ciągu iloczynowym, czyli w wyniku przemnożenia przez siebie cyfr pierwszej liczby.

    Należy rozszyfrować obie pary, jeśli wiadomo, że w kratkach powinno znaleźć się dziesięć różnych cyfr, a liczby przed strzałkami powinny być jak najmniejsze.

Rozwiązania prosimy nadsyłać do 31 stycznia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG01/14, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Iana Stewarta Matematyka życia, ufundowaną przez wydawnictwo Prószyński Media.

 

Rozwiązanie  zadań z numeru listopadowego

1. 9 pól na przekątnych szachownicy zasłaniają kamienie.

2. Na przekątnych są 3 kółka, 2 krzyżyki
i 3 kwadraty.

3. Rozwiązaniem jest figura przedstawiona na rysunku powiększona o 2 pola umieszczone tak, by przy pokrywaniu większej figury kamieniami domina konieczne było zakrycie tych dwu dodanych pól jednym kamieniem. W sumie są 22 różne 12-polowe figury-rozwiązania. Wystarczyło podać jedną.

 

 

 

Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Jamesa D. Steina Kosmiczne liczby. Liczby, które definiują naszą rzeczywistość, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Grzegorz Adamski ze Śmiłowa, Bolesław Baniak z Rzeszowa, Magda Glapska z Krakowa, Zbigniew Górawski z Wrocławia, Jacek Tyburczyk z Krakowa.

 

Więcej w miesięczniku „Świat Nauki" nr 01/2014 »
Drukuj »
Ten artykuł nie został jeszcze skomentowany.
Aktualne numery
11/2017
10/2017 - specjalny
Kalendarium
Listopad
20
W 1985 r. Microsoft zaprezentował system operacyjny Windows 1.0.
Warto przeczytać
Chwila bez biologii… nie istnieje. W nas i wokół nas kipi życie. Dlaczego by wobec tego nie poznać go bliżej, najlepiej we własnym laboratorium? By nie sięgać daleko, można zacząć od siebie.

Logowanie

Nazwa użytkownika

Hasło

Autor: Marek Penszko | dodano: 2013-12-17
Co następne. Mała trwałość wielkich liczb

W testach na inteligencję i w zbiorkach łamigłówek nierzadko pojawiają się ciągi. Niektóre z nich na tyle często i od tak dawna, że można je uznać za „klasyczne”. Do takich należy następujący:

77, 49, 36, 18, …

Jak zwykle w tego typu zadaniach, chodzi o odkrycie reguły, rządzącej ciągiem i wpisanie kolejnego wyrazu. W tym przypadku szukana liczba kończy ciąg, a zasada jego budowy jest prosta: każdy następny wyraz otrzymujemy, mnożąc przez siebie cyfry poprzedniego; na końcu pojawi się więc 8.

Zapewne osoba, która jako pierwsza wpadła na pomysł takiego ciągu „iloczynowego”, a z pewnością niejedna, która się z nim zetknęła, próbowała utworzyć choć o jeden wyraz dłuższy ciąg oparty na takiej zasadzie. I szybko dochodziła do wniosku, że sprawa nie jest taka prosta, jak by się mogło w pierwszej chwili wydawać. W tym przypadku nie ma szybkiej logicznej metody, umożliwiającej znalezienie najmniejszej liczby, która doprowadziłaby do jednocyfrowej przynajmniej w pięciu krokach. Szukając jej, trzeba postępować jak komputer, czyli sprawdzać kolejne, coraz większe liczby. Część z nich można wprawdzie z góry wyeliminować, np. te z zerem, jedynką i niektóre z piątką (dlaczego?), co ułatwia zadanie, ale w gruncie rzeczy niewiele zmienia, ponieważ nie istnieje żaden ogólny schemat „przełożenia” zbioru cyfr, tworzących daną liczbę, na cyfry tworzące ich iloczyn.

Temat takich ciągów pierwszy poruszył w 1973 roku Neil Sloane, matematyk z Bell Labs, w artykule, który ukazał się na łamach magazynu poświęconego rozrywkom matematycznym. Bodźcem do napisania go były zaskakujące rezultaty szukania najdłuższych ciągów iloczynowych za pomocą komputera. Sloane sprawdził wszystkie liczby do 100 oktylionów (1050), znajdując najmniejsze (a1[min]), rozpoczynające ciągi złożone z n = 5, 6, 7… itd. wyrazów. Poniższa tabela obejmuje także najmniejsze liczby zaczynające krótsze ciągi, poczynając od n=2 (choć w istocie dwa wyrazy, to jeszcze nie ciąg), a w trzeciej kolumnie podane są ich ostatnie wyrazy an.

Trudno się dziwić, że znalezienie bez komputera ciągu 6-wyrazowego nie było proste, skoro zaczyna się on dopiero od 679:

679→ 378→ 168→ 48→ 32→ 6

Każda permutacja cyfr 6, 7 i 9 i każde jej uzupełnienie dowolną liczbą jedynek rozpocznie oczywiście taki sam ciąg. Można by więc zapytać, jaka nieutworzona w ten sposób następna liczba zaczyna ciąg 6-wyrazowy. Okazuje się, że od 679 jest do niej bardzo blisko, a rzut oka na tabelę stanowi podpowiedź, bo… roi się w niej od ósemek.

Właściwie rozważania o ciągach iloczynowych wypadałoby zacząć od udowodnienia, że każdy jest malejący, czyli zawsze zakończy się liczbą jednocyfrową. Dowód można ująć w jednym zdaniu: liczba złożona z c cyfr i zaczynająca się od a jest większa niż a×10c-1, czyli większa od iloczynu jej cyfr, który nigdy nie przekroczy a×9c-1, bo każda cyfra może być co najwyżej dziewiątką. Iloraz obu tych wartości – (9/10)c-1 określa, jaką co najwyżej część liczby stanowi iloczyn jej cyfr. Na przykład dla c=10 będzie to około 0,4, czyli iloczyn także może być 10-cyfrowy, ale dla c=50 tylko niespełna 0,006, więc po pomnożeniu ubędą co najmniej dwie cyfry. Z dalszych bardziej skomplikowanych obliczeń i rozważań wynika, że ciąg iloczynowy, zaczynający się od liczby c-cyfrowej, nie może składać się z więcej niż c+3 wyrazów. Korzystając z komputera, Sloane potwierdził praktycznie słuszność tego wniosku, a przy okazji odkrył zdumiewającą własność: jeśli pierwszy wyraz nie przekracza 1050, to żaden ciąg nie składa się z więcej niż 12 wyrazów. Najdłuższy, zaczynający się od najmniejszej liczby (ostatnia w tabeli), wygląda tak:

277777788888899→ 4996238671872→ 438939648→ 4478976→ 338688→ 27648→ 2688→ 768→ 336→ 54→ 20 → 0.

Sloane wprowadził pojęcie trwałości liczby, która jest o jeden mniejsza od liczby wyrazów, zaczynającego się od niej ciągu iloczynowego, czyli równa jest liczbie kroków (odstępów między wyrazami). Kojarzy się to z trwałością jąder atomowych, ale – w przeciwieństwie do jąder – nietrwałe są wszystkie liczby. Bardziej trwałe oczywiście te, które zaczynają dłuższe ciągi; można nawet określić ich „okres połowicznego rozpadu”, czyli liczbę kroków, po której stają się o połowę krótsze. Na podstawie obliczeń Sloane postawił hipotezę, że trwałość liczby nie może być większa od 11. Przed trzema laty na Uniwersytecie w Perth w Australii sprawdzono wszystkie liczby do 10333, a w ubiegłym roku w laboratorium informatycznym francuskiego Uniwersytetu Lille I – do 10500. Komputery nie mnożyły oczywiście cyfr każdej liczby, bo trwałoby to do końca świata i jeden dzień dłużej. Skorzystano z serii sprytnych trików, radykalnie upraszczających obliczenia i czas pracy urządzeń, czyli:

– pominięto liczby, których trwałość jest nie większa od 2, a więc wszystkie z przynajmniej jednym zerem albo zawierające piątkę i cyfrę parzystą;

– nie uwzględniono liczb z jedynkami, bo ich obecność nie wpływa na trwałość;

– cyfrę 4 zastąpiono parą 22, 6 – parą 23, 8 – tercetem 222, 9 – duetem 33; żadne z tych zastępstw nie zmienia trwałości;

– ponieważ dla trwałości kolejność cyfr nie ma to znaczenia, uwzględniano tylko niemalejące ciągi cyfr.

W efekcie do sprawdzenia pozostała „garstka” ciągów cyfr, odpowiadających dwu schematom:

a) 222…2333…3777…7

b) 333…3555…5777…7

Wniosek z obliczeń komputerowych okazał się taki, jakiego należało się spodziewać: trwałości większej niż 11 nie stwierdzono. Byłoby zresztą niemal sensacją, gdyby pojawiło się 12, bowiem już z obliczeń Sloane’a wynikało, że wraz ze wzrostem zakresu liczb ich średnia trwałość zmniejsza się. Wiele wskazuje na to, że gdy górna granica zakresu liczb dąży do nieskończoności, to ich średnia trwałość zmierza do 1. Zdarzają się wprawdzie „wyskoki”, które stwarzają nadzieję, ale ostatnia trwałość równa 10 pojawia się przy dwóch liczbach 29-cyfrowych – 2193476 i 2432075 (Xn oznacza ciąg złożony z n cyfr X, stanowiący część liczby). Dalsze wyskoki są coraz niższe. Trudno się temu dziwić, bo im większa liczba, tym większe prawdopodobieństwo, że w iloczynie jej cyfr pojawi się zero. Można założyć, że od pewnego momentu jest to prawie pewne.

Paul ErdÖs, jeden z najwybitniejszych matematyków XX wieku, po zapoznaniu się z pojęciem trwałości liczb zaproponował drobną, ale istotną modyfikację sposobu tworzenia ciągów iloczynowych: pomijanie zer w iloczynach przy wykonywaniu kolejnych mnożeń. Ich pojawienie się nie oznacza więc nagłego zakończenia ciągu i może on wyglądać na przykład tak:

99999→ 59049→ 1620→ 12→ 2

Nie wiadomo, czy trwałość Erdösa ma jakąś maksymalną wartość (Erdös uważał, że tak). Dotychczas znaleziono liczby, dla których sięga 20, ale są one tak gigantyczne, że możliwości komputerów i koszt ich pracy ograniczają dalsze poszukiwania.

Poniższe zadania (2 i 3) dotyczą ciągów tworzonych metodą Sloane’a.

1.         Ciągi jako testy lub łamigłówki są często niejednoznaczne, czyli można znaleźć więcej niż jedno rozwiązanie. Dotyczy to także ciągu zaczynającego ten artykuł. Gdyby jego piątym wyrazem było 9, to jaki byłby szósty wyraz, czyli następny w ciągu: 77, 49, 36, 18, 9, …? Odpowiedź należy oczywiście uzasadnić, czyli podać regułę budowy ciągu.

2.         W pochodzącej ze znanego kryminału Agathy Christie złowróżbnej wyliczance o dziesięciu małych Murzyniątkach, ubywa jednego z nich w każdej kolejnej zwrotce. Liczbowym odpowiednikiem takiej „zabawy” mógłby być ciąg iloczynowy, zaczynający się od 10-cyfrowej liczby złożonej z różnych cyfr, w którym każdy następny wyraz byłby także różnocyfrowy, ale krótszy o jedną cyfrę. Jest to oczywiście niemożliwe, czyli należałoby zacząć od mniejszej liczby „murzynków”.

 

      Z ilu wyrazów składa się najdłuższy ciąg iloczynowy, zaczynający się liczbą złożoną z różnych cyfr, w którym każdy następny wyraz różni się od poprzedniego tylko brakiem jednej cyfry i ewentualnie przestawieniem pozostałych? Jaka jest najmniejsza liczba, zaczynająca taki ciąg?

3.         W dwóch parach liczb cyfry zastąpiono kratkami. Druga liczba w każdej parze powstała tak, jak kolejny wyraz  w ciągu iloczynowym, czyli w wyniku przemnożenia przez siebie cyfr pierwszej liczby.

    Należy rozszyfrować obie pary, jeśli wiadomo, że w kratkach powinno znaleźć się dziesięć różnych cyfr, a liczby przed strzałkami powinny być jak najmniejsze.

Rozwiązania prosimy nadsyłać do 31 stycznia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG01/14, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Iana Stewarta Matematyka życia, ufundowaną przez wydawnictwo Prószyński Media.

 

Rozwiązanie  zadań z numeru listopadowego

1. 9 pól na przekątnych szachownicy zasłaniają kamienie.

2. Na przekątnych są 3 kółka, 2 krzyżyki
i 3 kwadraty.

3. Rozwiązaniem jest figura przedstawiona na rysunku powiększona o 2 pola umieszczone tak, by przy pokrywaniu większej figury kamieniami domina konieczne było zakrycie tych dwu dodanych pól jednym kamieniem. W sumie są 22 różne 12-polowe figury-rozwiązania. Wystarczyło podać jedną.

 

 

 

Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Jamesa D. Steina Kosmiczne liczby. Liczby, które definiują naszą rzeczywistość, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Grzegorz Adamski ze Śmiłowa, Bolesław Baniak z Rzeszowa, Magda Glapska z Krakowa, Zbigniew Górawski z Wrocławia, Jacek Tyburczyk z Krakowa.