nauki ścisłe
Autor: Marek Penszko | dodano: 2014-05-20
Czyli o liczbach biegnących z powrotem

Amerykański aktor Robert Trebor to zapewne jedyna szerzej znana osoba (w Polsce głównie z serialu Herkules), którą można nazwać „podwójnie palindromową”. Po pierwsze dlatego, że jego imię z nazwiskiem tworzą palindrom, a po drugie – dwa lata w jego życiu były palindromami: 1991 i 2002. Pierwsza cecha jest niezwykle rzadka; na myśl przychodzi jeszcze tylko kambodżański polityk Lon Nol. Druga – przeciwnie, dotyczy większości osób żyjących współcześnie, jednak przed rokiem 2002 przez okres obejmujący ponad 900 lat bardzo trudno byłoby znaleźć kogoś tak wiekowego, aby mógł się „zaliczeniem” pary palindromowych lat pochwalić.

Z podanych przykładów łatwo wywnioskować – jeśli ktoś, co mało prawdopodobne, dotąd nie zetknął się z palindromem – że określenie to dotyczy wyrazu, grupy wyrazów (z reguły tworzących poprawną gramatycznie i sensowną całość) albo liczby, które nie zmieniają się po zapisaniu wspak. Inaczej mówiąc, chodzi o takie liniowe układy liter lub cyfr, w których znaki rozmieszczone są symetrycznie.

Słowo palindrom utworzył w XVII wieku angielski pisarz Ben Jonson, łącząc greckie wyrazy palin („powtórnie”, „odwrotnie”) i dromos („bieg”), można je więc przetłumaczyć jako „biegnący z powrotem”. Przez długi czas dotyczyło ono wyłącznie konstrukcji językowych, a układanie i zbieranie palindromów było i bywa nadal osobliwym hobby; w polszczyźnie jego zalążek stanowi zdanie „kobyła ma mały bok”. Od połowy XX wieku matematycy nazywają palindromami liczby z symetrycznym rozmieszczeniem cyfr, a od niedawna pojawiły się one także w innych naukach, np. w genetyce (sekwencja palindromowa DNA) i informatyce (zbiory palindromowe w teorii języków formalnych)

O ile palindromy słowne są niemal wyłącznie osobliwością i zabawą, o tyle z liczbowymi wiąże się kilka ciekawych zagadnień z zakresu teorii liczb. Palindromów liczbowych jest oczywiście nieskończenie wiele, zaczynając od trywialnych jednocyfrowych (0, 1, 2, 3,…) i ich dubletów (…11, 22, 33,…). Pytanie o to, ile ich jest, ma więc sens tylko wówczas, jeśli dotyczy jakiegoś zakresu. A zatem: ile jest palindromów n-cyfrowych dla n=1, 2, 3,…? Każdy z dziewięciu 2-cyfrowych, od 11 do 99, można zmienić w 3-cyfrowy na 10 sposobów, wstawiając w środek jedną z cyfr. Z kolei każdemu 3-cyfrowemu o schemacie aba odpowiada dokładnie jeden 4-cyfrowy abba. Uogólniając te zależności: palindromów (2n+1)-cyfrowych jest 10 razy więcej niż 2n-cyfrowych, których z kolei jest tyle samo, ile (2n-1)-cyfrowych – dla każdego n poza jednym wyjątkiem: jednocyfrowych jest 10, czyli o jeden więcej niż dwucyfrowych, bo trzeba uwzględnić zero. Stąd ciąg liczb palindromów n-cyfrowych: 10, 9, 90, 90, 900, 900, 9000, 9000, 90 000… Im większe palindromy, tym rzadziej występują w ciągu liczb naturalnych. Od 151 do 161 jest tylko dziesięć kroków, ale od 7 298 927 do następnego już stokroć dalej.

Ciekawą własnością palindromów jest podzielność większości z nich przez 11. Jeśli ktoś z Państwa chciałby się samemu zmierzyć z dowodem, że przez 11 podzielne są wszystkie palindromy złożone z parzystej liczby cyfr, powinien teraz przerwać czytanie. Skuteczne, ale niezbyt eleganckie byłoby skorzystanie z cechy podzielności przez 11. Zaczniemy więc inaczej – od przedstawienia 2n-cyfrowego palindromu a1a2…an-1ananan-1…a2a1 w postaci:

a1102n-1+a2102n-2+…+an-110n+1+an10n+an10n-1+an-110n-2+…+a2101+a1100

Po redukcji otrzymamy:

100a1(102n-1+1)+101a2(102n-3+1)+…+10n-2an-1(103+1)+10n-1an(101+1)

W każdym składniku w nawiasie znajduje się liczba o 1 większa od nieparzystej wielokrotności 10 (11, 1001, 100001,…). Łatwo dowieść, na przykład przez indukcję, że liczby te są wielokrotnościami 11. Zatem przez 11 dzieli się także suma wielokrotności takich liczb, a więc każdy palindrom złożony z parzystej liczby cyfr. Natomiast wśród palindromów z nieparzystą liczbą cyfr (2n+1) średnio tylko co jedenasty dzieli się przez 11. Ich dokładna liczba wyraża się wzorem:

pn=[(10n+1+(-1)n]/11.

Palindromy mogą być kwadratami (0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, 69696, 94249, 698896, 1002001,…), sześcianami (0, 1, 8, 343, 1331, 1030301, 1367631, 1003003001, 10662526601, 1000300030001,…) i liczbami pierwszymi (2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501,…). Po przedstawionym wyżej dowodzie nie dziwi, że wśród tych ostatnich znajduje się tylko jedna złożona z parzystej liczby cyfr.

Z niektórych kwadratów i liczb pierwszych miłośnicy matematyki rekreacyjnej skonstruowali urokliwe piramidki – dwa przykłady na rys. 1. Druga piramidka składa się z liczb pierwszych i jest najwyższa, jaką można z liczb pierwszych zbudować, zaczynając od liczby jednocyfrowej i oczywiście zachowując charakterystyczną urokliwość. Podstawą prawie wszystkich palindromowych sześcianów także są palindromy; 10 662 526 601 jest jedynym, którego podstawa (2201) nie jest palindromem. Rarytas stanowi też kwadrat 698 896 – najmniejszy i jeden z bardzo nielicznych złożonych z parzystej liczby cyfr (następny jest 12-cyfrowy). Innych ciekawostek i osobliwości związanych z palindromami można by podać sporo, ale najbardziej spektakularne wiążą się z operacją zwaną „odwróć i dodaj”.

 

 

RYS. 1

 

                                                                                                                                  

                                                                                                                                                                   RYS. 2

W roku 1938 amerykański matematyk Derrick Lehmer opisał pewną niezwykłą własność liczb, a właściwie prostego cyklicznego procesu, któremu można je poddawać: do wybranej liczby dodajemy nią samą, ale zapisaną wspak; z otrzymaną sumą i z każdą następną postępujemy identycznie dotąd, aż jako kolejna suma pojawi się palindrom. Gdyby liczbą był na przykład wspomniany rok, czyli 1938, to zakończenie nastąpiłoby w trzecim etapie (rys. 2). Większość małych liczb, zaczynając od 10 (wykluczamy palindromy, które „obróbki” nie wymagają), dociera do palindromu w jednym kroku. 19 jest pierwszą wymagającą dwóch kroków (19+91=110 → 110+011=121), 59 – trzech (59+95=154 → 154+451=605 → 605+506=1111), 69 – czterech (same sumy: 69 → 165 → 726 → 1353 → 4884). Najmniejszą, przy której trzeba się solidnie napracować, jest 89 – palindrom pojawia się dopiero jako 24. suma równa 8 813 200 023 188. To jednak nic w porównaniu z „gehenną”, którą oferuje liczba 196. Lehmer wykonał przed 76 laty blisko sto dodawań – bezskutecznie. Nie omieszkał jednak zauważyć, że 56. suma jest bardzo bliska docelowej, wygląda bowiem tak:

934217310162393261013712428.

Zapewne ta obiecująca bliskość skłoniła go do postawienia hipotezy, że każda liczba poddana opisanemu procesowi zmieni się w palindrom – wszystko jest tylko kwestią etapu, w którym to nastąpi. 196 to nie jedyna „krnąbrna” liczba, ale najmniejsza, więc nią przede wszystkim zajęli się programiści, gdy do akcji wkroczyły komputery.

Jako pierwszy wyzwanie podjął John Walker – założyciel znanej firmy Autodesk, zajmującej się oprogramowaniem – uruchamiając w 1987 roku program na stacji roboczej Sun 3/260. Po blisko trzech latach nieprzerwanej pracy i wykonaniu 2 415 836 operacji „odwróć i dodaj” komputer dotarł do liczby złożonej z miliona cyfr i się zatrzymał. Palindromu nie było. Następcy Walkera posuwali się coraz dalej, korzystając z coraz lepszych komputerów. Jeden z nich nadał 196 i pozostałym równie opornym liczbom nazwę, która się przyjęła – liczby Lychrel, będącą jakoby anagramem imienia pewnej pani (zapewne równie niedostępnej jak wciąż nieosiągalny palindrom) – Cheryll.

Aktualny rekord w wędrówce od 196 do palindromu dzierży francuski programista Romain Dolbeau, który pod koniec 2011 roku dotarł po bilionie kroków do liczby złożonej z 413 930 770 cyfr. Oczywiście celu nie osiągając. Wydaje się, że to koniec „szaleństwa”, czyli że dalszej eksploracji nie będzie. Szansa na dotarcie do gigantycznego palindromu maleje wraz z wydłużaniem się sumy. Praktycznie jest już równa zeru i wiele wskazuje na to, że hipotezę podaną przez Lehmera należy uznać za błędną. Tym bardziej, że dla systemów liczbowych o mniejszych podstawach niż dziesiętny udowodniono, że niektóre liczby poddawane operacji „odwróć i dodaj” nigdy nie zmienią się w palindrom.

W systemie dwójkowym najmniejszą taką liczbą jest 10 110, odpowiadająca 22 w dziesiętnym. Niemiecki matematyk Roland Sprague jeszcze w latach 60. podał prosty dowód, że przekształcenie jej w palindrom nie jest możliwe. Zauważył, że w ciągu sum, poczynając od czwartej, cyklicznie powtarzają się cztery schematy liczb. Na przykład, dla czwartej sumy równej 10110100 schematem jest 10(1)n01(0)n. Dla tej sumy n=2, dla ósmej – 3, dla dwunastej – 4 itd. – schemat pozostaje taki sam. Zarówno ten schemat, jak i każdy z trzech pozostałych wyklucza pojawienie się palindromu. Znalezienie dowodu dla układu dziesiętnego ostatecznie rozwiązałoby problem i odesłało liczby Lychrel do lamusa. Niestety, dotąd nikomu się to nie udało.

ZADANIA

1.         Sudoku, ale z dodatkowym warunkiem (rys. 3). W puste pola należy wpisać liczby od 1 do 9 tak, aby w każdym wierszu, każdej kolumnie i w każdym kwadracie 3×3 ograniczonym grubą linią znalazło się dziewięć różnych cyfr. Dodatkowy warunek wiąże się z błękitnymi liniami łamanymi: kolejne cyfry, które znajdą się na każdej z tych linii (cyfr jest 7 lub 9), powinny tworzyć palindrom. W rozwiązaniu wystarczy podać sumę 17 cyfr na obu przekątnych.

 

                              

                                                           RYS. 3

2.         Z 35 pierwszych palindromów – od 0 do 252 – wybrano 16 i utworzono z nich kwadrat magiczny 4×4, czyli taki, w którym suma (zwana sumą magiczną) czterech liczb w każdym wierszu, kolumnie i na obu przekątnych jest taka sama. Na rys. 4 znajdują się: z lewej strony – 35 liczb, z których dokonano wyboru, z prawej – kwadrat z ujawnionymi 4 liczbami. Zadanie polega na wypełnieniu właściwymi liczbami pozostałych 12 pól tak, aby powstał wspomniany kwadrat magiczny. Jego suma magiczna także powinna być palindromem. W rozwiązaniu wystarczy podać tę sumę.

 

                 

RYS. 4

3.         Jaka jest największa liczba naturalna, której każda cyfra – oprócz pierwszej i ostatniej – jest mniejsza od średniej arytmetycznej dwu sąsiadujących z nią cyfr?

Rozwiązania prosimy nadsyłać do 30 czerwca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG06/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 Wielkie problemy matematyczne, ufundowaną przez wydawnictwo Prószyński Media.

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.

Rozwiązanie zadań z numeru kwietniowego

1. Wzór na pojemność krzyża: TK=PA*PB+1*PD*PC+1+PA+1*PB*PD+1*PC

2. Opisaną własność mają prostokąty, w których liczba pól wzdłuż jednego boku jest nieparzysta.

3. Trasę przebiegającą zgodnie z opisem można poprowadzić w każdym prostokącie (jej główny kierunek powinien być równoległy do boku o parzystej liczbie pól).

4. 8 domin.

Zadania były tym razem trudniejsze niż zwykle – w większości problemowe, a jedno (3) nawet nieco podstępne – więc odpowiedzi otrzymaliśmy znacznie mniej niż zwykle, w tym tylko dwa zestawy z przynajmniej dwoma zadaniami rozwiązanymi poprawnie. Ich autorzy zasługują więc nie tylko na nagrody – co oczywiste – ale także na gratulacje.

 Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Briana Coxa i Jeffa Forshawy Kwantowy Wszechświat. Dlaczego zdarza się wszystko, co może się zdarzyć, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Grzegorz Adamski ze Śmiłowa i Tomasz Migdałek z Poznania.

 

Więcej w miesięczniku „Świat Nauki" nr 06/2014 »
Drukuj »
Ten artykuł nie został jeszcze skomentowany.
Aktualne numery
12/2017
10/2017 - specjalny
Kalendarium
Listopad
24
W 1859 r. Karol Darwin opublikował dzieło O powstaniu gatunków na drodze doboru naturalnego.
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: 2014-05-20
Czyli o liczbach biegnących z powrotem

Amerykański aktor Robert Trebor to zapewne jedyna szerzej znana osoba (w Polsce głównie z serialu Herkules), którą można nazwać „podwójnie palindromową”. Po pierwsze dlatego, że jego imię z nazwiskiem tworzą palindrom, a po drugie – dwa lata w jego życiu były palindromami: 1991 i 2002. Pierwsza cecha jest niezwykle rzadka; na myśl przychodzi jeszcze tylko kambodżański polityk Lon Nol. Druga – przeciwnie, dotyczy większości osób żyjących współcześnie, jednak przed rokiem 2002 przez okres obejmujący ponad 900 lat bardzo trudno byłoby znaleźć kogoś tak wiekowego, aby mógł się „zaliczeniem” pary palindromowych lat pochwalić.

Z podanych przykładów łatwo wywnioskować – jeśli ktoś, co mało prawdopodobne, dotąd nie zetknął się z palindromem – że określenie to dotyczy wyrazu, grupy wyrazów (z reguły tworzących poprawną gramatycznie i sensowną całość) albo liczby, które nie zmieniają się po zapisaniu wspak. Inaczej mówiąc, chodzi o takie liniowe układy liter lub cyfr, w których znaki rozmieszczone są symetrycznie.

Słowo palindrom utworzył w XVII wieku angielski pisarz Ben Jonson, łącząc greckie wyrazy palin („powtórnie”, „odwrotnie”) i dromos („bieg”), można je więc przetłumaczyć jako „biegnący z powrotem”. Przez długi czas dotyczyło ono wyłącznie konstrukcji językowych, a układanie i zbieranie palindromów było i bywa nadal osobliwym hobby; w polszczyźnie jego zalążek stanowi zdanie „kobyła ma mały bok”. Od połowy XX wieku matematycy nazywają palindromami liczby z symetrycznym rozmieszczeniem cyfr, a od niedawna pojawiły się one także w innych naukach, np. w genetyce (sekwencja palindromowa DNA) i informatyce (zbiory palindromowe w teorii języków formalnych)

O ile palindromy słowne są niemal wyłącznie osobliwością i zabawą, o tyle z liczbowymi wiąże się kilka ciekawych zagadnień z zakresu teorii liczb. Palindromów liczbowych jest oczywiście nieskończenie wiele, zaczynając od trywialnych jednocyfrowych (0, 1, 2, 3,…) i ich dubletów (…11, 22, 33,…). Pytanie o to, ile ich jest, ma więc sens tylko wówczas, jeśli dotyczy jakiegoś zakresu. A zatem: ile jest palindromów n-cyfrowych dla n=1, 2, 3,…? Każdy z dziewięciu 2-cyfrowych, od 11 do 99, można zmienić w 3-cyfrowy na 10 sposobów, wstawiając w środek jedną z cyfr. Z kolei każdemu 3-cyfrowemu o schemacie aba odpowiada dokładnie jeden 4-cyfrowy abba. Uogólniając te zależności: palindromów (2n+1)-cyfrowych jest 10 razy więcej niż 2n-cyfrowych, których z kolei jest tyle samo, ile (2n-1)-cyfrowych – dla każdego n poza jednym wyjątkiem: jednocyfrowych jest 10, czyli o jeden więcej niż dwucyfrowych, bo trzeba uwzględnić zero. Stąd ciąg liczb palindromów n-cyfrowych: 10, 9, 90, 90, 900, 900, 9000, 9000, 90 000… Im większe palindromy, tym rzadziej występują w ciągu liczb naturalnych. Od 151 do 161 jest tylko dziesięć kroków, ale od 7 298 927 do następnego już stokroć dalej.

Ciekawą własnością palindromów jest podzielność większości z nich przez 11. Jeśli ktoś z Państwa chciałby się samemu zmierzyć z dowodem, że przez 11 podzielne są wszystkie palindromy złożone z parzystej liczby cyfr, powinien teraz przerwać czytanie. Skuteczne, ale niezbyt eleganckie byłoby skorzystanie z cechy podzielności przez 11. Zaczniemy więc inaczej – od przedstawienia 2n-cyfrowego palindromu a1a2…an-1ananan-1…a2a1 w postaci:

a1102n-1+a2102n-2+…+an-110n+1+an10n+an10n-1+an-110n-2+…+a2101+a1100

Po redukcji otrzymamy:

100a1(102n-1+1)+101a2(102n-3+1)+…+10n-2an-1(103+1)+10n-1an(101+1)

W każdym składniku w nawiasie znajduje się liczba o 1 większa od nieparzystej wielokrotności 10 (11, 1001, 100001,…). Łatwo dowieść, na przykład przez indukcję, że liczby te są wielokrotnościami 11. Zatem przez 11 dzieli się także suma wielokrotności takich liczb, a więc każdy palindrom złożony z parzystej liczby cyfr. Natomiast wśród palindromów z nieparzystą liczbą cyfr (2n+1) średnio tylko co jedenasty dzieli się przez 11. Ich dokładna liczba wyraża się wzorem:

pn=[(10n+1+(-1)n]/11.

Palindromy mogą być kwadratami (0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, 69696, 94249, 698896, 1002001,…), sześcianami (0, 1, 8, 343, 1331, 1030301, 1367631, 1003003001, 10662526601, 1000300030001,…) i liczbami pierwszymi (2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501,…). Po przedstawionym wyżej dowodzie nie dziwi, że wśród tych ostatnich znajduje się tylko jedna złożona z parzystej liczby cyfr.

Z niektórych kwadratów i liczb pierwszych miłośnicy matematyki rekreacyjnej skonstruowali urokliwe piramidki – dwa przykłady na rys. 1. Druga piramidka składa się z liczb pierwszych i jest najwyższa, jaką można z liczb pierwszych zbudować, zaczynając od liczby jednocyfrowej i oczywiście zachowując charakterystyczną urokliwość. Podstawą prawie wszystkich palindromowych sześcianów także są palindromy; 10 662 526 601 jest jedynym, którego podstawa (2201) nie jest palindromem. Rarytas stanowi też kwadrat 698 896 – najmniejszy i jeden z bardzo nielicznych złożonych z parzystej liczby cyfr (następny jest 12-cyfrowy). Innych ciekawostek i osobliwości związanych z palindromami można by podać sporo, ale najbardziej spektakularne wiążą się z operacją zwaną „odwróć i dodaj”.

 

 

RYS. 1

 

                                                                                                                                  

                                                                                                                                                                   RYS. 2

W roku 1938 amerykański matematyk Derrick Lehmer opisał pewną niezwykłą własność liczb, a właściwie prostego cyklicznego procesu, któremu można je poddawać: do wybranej liczby dodajemy nią samą, ale zapisaną wspak; z otrzymaną sumą i z każdą następną postępujemy identycznie dotąd, aż jako kolejna suma pojawi się palindrom. Gdyby liczbą był na przykład wspomniany rok, czyli 1938, to zakończenie nastąpiłoby w trzecim etapie (rys. 2). Większość małych liczb, zaczynając od 10 (wykluczamy palindromy, które „obróbki” nie wymagają), dociera do palindromu w jednym kroku. 19 jest pierwszą wymagającą dwóch kroków (19+91=110 → 110+011=121), 59 – trzech (59+95=154 → 154+451=605 → 605+506=1111), 69 – czterech (same sumy: 69 → 165 → 726 → 1353 → 4884). Najmniejszą, przy której trzeba się solidnie napracować, jest 89 – palindrom pojawia się dopiero jako 24. suma równa 8 813 200 023 188. To jednak nic w porównaniu z „gehenną”, którą oferuje liczba 196. Lehmer wykonał przed 76 laty blisko sto dodawań – bezskutecznie. Nie omieszkał jednak zauważyć, że 56. suma jest bardzo bliska docelowej, wygląda bowiem tak:

934217310162393261013712428.

Zapewne ta obiecująca bliskość skłoniła go do postawienia hipotezy, że każda liczba poddana opisanemu procesowi zmieni się w palindrom – wszystko jest tylko kwestią etapu, w którym to nastąpi. 196 to nie jedyna „krnąbrna” liczba, ale najmniejsza, więc nią przede wszystkim zajęli się programiści, gdy do akcji wkroczyły komputery.

Jako pierwszy wyzwanie podjął John Walker – założyciel znanej firmy Autodesk, zajmującej się oprogramowaniem – uruchamiając w 1987 roku program na stacji roboczej Sun 3/260. Po blisko trzech latach nieprzerwanej pracy i wykonaniu 2 415 836 operacji „odwróć i dodaj” komputer dotarł do liczby złożonej z miliona cyfr i się zatrzymał. Palindromu nie było. Następcy Walkera posuwali się coraz dalej, korzystając z coraz lepszych komputerów. Jeden z nich nadał 196 i pozostałym równie opornym liczbom nazwę, która się przyjęła – liczby Lychrel, będącą jakoby anagramem imienia pewnej pani (zapewne równie niedostępnej jak wciąż nieosiągalny palindrom) – Cheryll.

Aktualny rekord w wędrówce od 196 do palindromu dzierży francuski programista Romain Dolbeau, który pod koniec 2011 roku dotarł po bilionie kroków do liczby złożonej z 413 930 770 cyfr. Oczywiście celu nie osiągając. Wydaje się, że to koniec „szaleństwa”, czyli że dalszej eksploracji nie będzie. Szansa na dotarcie do gigantycznego palindromu maleje wraz z wydłużaniem się sumy. Praktycznie jest już równa zeru i wiele wskazuje na to, że hipotezę podaną przez Lehmera należy uznać za błędną. Tym bardziej, że dla systemów liczbowych o mniejszych podstawach niż dziesiętny udowodniono, że niektóre liczby poddawane operacji „odwróć i dodaj” nigdy nie zmienią się w palindrom.

W systemie dwójkowym najmniejszą taką liczbą jest 10 110, odpowiadająca 22 w dziesiętnym. Niemiecki matematyk Roland Sprague jeszcze w latach 60. podał prosty dowód, że przekształcenie jej w palindrom nie jest możliwe. Zauważył, że w ciągu sum, poczynając od czwartej, cyklicznie powtarzają się cztery schematy liczb. Na przykład, dla czwartej sumy równej 10110100 schematem jest 10(1)n01(0)n. Dla tej sumy n=2, dla ósmej – 3, dla dwunastej – 4 itd. – schemat pozostaje taki sam. Zarówno ten schemat, jak i każdy z trzech pozostałych wyklucza pojawienie się palindromu. Znalezienie dowodu dla układu dziesiętnego ostatecznie rozwiązałoby problem i odesłało liczby Lychrel do lamusa. Niestety, dotąd nikomu się to nie udało.

ZADANIA

1.         Sudoku, ale z dodatkowym warunkiem (rys. 3). W puste pola należy wpisać liczby od 1 do 9 tak, aby w każdym wierszu, każdej kolumnie i w każdym kwadracie 3×3 ograniczonym grubą linią znalazło się dziewięć różnych cyfr. Dodatkowy warunek wiąże się z błękitnymi liniami łamanymi: kolejne cyfry, które znajdą się na każdej z tych linii (cyfr jest 7 lub 9), powinny tworzyć palindrom. W rozwiązaniu wystarczy podać sumę 17 cyfr na obu przekątnych.

 

                              

                                                           RYS. 3

2.         Z 35 pierwszych palindromów – od 0 do 252 – wybrano 16 i utworzono z nich kwadrat magiczny 4×4, czyli taki, w którym suma (zwana sumą magiczną) czterech liczb w każdym wierszu, kolumnie i na obu przekątnych jest taka sama. Na rys. 4 znajdują się: z lewej strony – 35 liczb, z których dokonano wyboru, z prawej – kwadrat z ujawnionymi 4 liczbami. Zadanie polega na wypełnieniu właściwymi liczbami pozostałych 12 pól tak, aby powstał wspomniany kwadrat magiczny. Jego suma magiczna także powinna być palindromem. W rozwiązaniu wystarczy podać tę sumę.

 

                 

RYS. 4

3.         Jaka jest największa liczba naturalna, której każda cyfra – oprócz pierwszej i ostatniej – jest mniejsza od średniej arytmetycznej dwu sąsiadujących z nią cyfr?

Rozwiązania prosimy nadsyłać do 30 czerwca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG06/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 Wielkie problemy matematyczne, ufundowaną przez wydawnictwo Prószyński Media.

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.

Rozwiązanie zadań z numeru kwietniowego

1. Wzór na pojemność krzyża: TK=PA*PB+1*PD*PC+1+PA+1*PB*PD+1*PC

2. Opisaną własność mają prostokąty, w których liczba pól wzdłuż jednego boku jest nieparzysta.

3. Trasę przebiegającą zgodnie z opisem można poprowadzić w każdym prostokącie (jej główny kierunek powinien być równoległy do boku o parzystej liczbie pól).

4. 8 domin.

Zadania były tym razem trudniejsze niż zwykle – w większości problemowe, a jedno (3) nawet nieco podstępne – więc odpowiedzi otrzymaliśmy znacznie mniej niż zwykle, w tym tylko dwa zestawy z przynajmniej dwoma zadaniami rozwiązanymi poprawnie. Ich autorzy zasługują więc nie tylko na nagrody – co oczywiste – ale także na gratulacje.

 Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Briana Coxa i Jeffa Forshawy Kwantowy Wszechświat. Dlaczego zdarza się wszystko, co może się zdarzyć, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Grzegorz Adamski ze Śmiłowa i Tomasz Migdałek z Poznania.