Shutterstock
Strona główna

Do liczby ostatniej, czyli gry w ciągi

Wzór 1 Wzór 1
Wzór 2 Wzór 2
Wzór 3 Wzór 3
Wzór 4 Wzór 4
Rys. 1Marek Penszko Rys. 1
Rys. 2Marek Penszko Rys. 2
materiały prasowe
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.Scientific American 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.
Zagadka numeru.

Są dwie osoby. Jedna z nich rozpoczyna grę, wymieniając jakąś liczbę. Po niej liczbę podaje druga, potem znowu pierwsza, następnie ponownie druga itd. Takie „ruchy”, wykonywane na przemian, można by nazwać rachunkowymi, bowiem istotny jest warunek: każda nowo podana liczba musi być w określony sposób – zawsze taki sam – związana z liczbą wymienioną w poprzednim ruchu. Kolejne liczby są coraz większe, a kto osiągnie z góry ustaloną granicę, ten wygrywa. Nietrudno się domyślić, że gra jest raczej metagrą, czyli rodzajem łamigłówki o grze, chodzi bowiem o odpowiedź na pytanie: kto zwycięży, jeśli obie strony będą grać najlepiej, czyli nie popełnią błędu – rozpoczynający (nazwiemy go N, bo wykonuje pierwszy i Nieparzyste ruchy) czy jego przeciwnik (P – drugi i Parzyste ruchy) – oraz jak grać, aby tak się stało?

Na początek dwa proste przykłady – warianty gry zwanej „setką”. W obu N zaczyna, podając dowolną liczbę naturalną nie większą niż k, zaś każda następna powinna być większa od poprzedniej o co najwyżej k. Wygrywa, kto jako pierwszy osiągnie 100. Różnicą jest tylko to, że w pierwszym wariancie k=9, a w drugim k=10. Nietrudno ustalić strategie obu wariantów i wskazać potencjalnych zwycięzców. Gdy k=9, wygra P, wymieniając zawsze wielokrotność dziesięciu. Przy k=10 zwycięży N, zaczynając od 1 i podając w kolejnych ruchach liczbę utworzoną z dwu kolejnych cyfr (12, 23, 34, …, 89).

W pierwszej chwili może się wydawać, że strategie są różne, ale właściwie należałoby je nazwać bliźniaczymi, bo po uogólnieniu „setki”, polegającym na zamianie 100 na dowolną liczbę L, kolejne liczby, które powinien podawać zmierzający do wygranej, można wyrazić wzorem:

Dolne półklamry to tzw. podłoga – oznacza konieczność zaokrąglenia objętego nimi działania w dół do liczby całkowitej.

Do trudniejszej wersji prowadzi zmiana „setki”, polegająca na zastąpieniu dodawania mnożeniem: N w pierwszym ruchu wymienia dowolną liczbę jednocyfrową większą od 1. Następny i każdy kolejny ruch polega na pomnożeniu efektu poprzedniego ruchu także przez dowolną liczbę jednocyfrową większą od 1. Wygrywa, kto pierwszy przekroczy jakąś dużą liczbę, np. tysiąc, milion lub 1 234 567 890. Ustalenie, czy zwycięzcą będzie N czy P, tradycyjnie sprowadza się do analizy „od końca”. Jeśli celem jest 1000, to podanie w przedostatnim ruchu dowolnej liczby z przedziału [112; 999] oznacza porażkę, bo wówczas mnożenie przez 9 kończy grę. Dwa następne kroki wstecz prowadzą najpierw do zwycięskiego przedziału [56; 111], a potem do niefortunnego [7; 55]. I już widać, że N wygra, gdy zacznie liczbą 4, 5 lub 6, bo po żadnej z nich P w drugim ruchu nie uniknie wiodącego ku porażce iloczynu z przedziału [7; 55]. Wszystkie potencjalne rozgrywki korzystne dla N, złożone z pięciu ruchów, można zapisać w postaci:

1N. 4_6

(2P. 8_54)

3N. 56_111

(4P. 112_999)

5N. >1000

Gdyby grę uogólnić, jej zasady mogłyby wyglądać tak: N w pierwszym ruchu wymienia dowolną liczbę naturalną z przedziału [2; k]. Każdy kolejny ruch polega na pomnożeniu efektu poprzedniego ruchu także przez dowolną liczbę naturalną z przedziału [2; k]. Wygra, kto pierwszy osiągnie liczbę C.

Wygodnym sposobem analizy gry w takiej postaci jest zlogarytmowanie reguł. Zamiast liczb 2, k, C pojawią się odpowiednio log2, logk, logC, a co najistotniejsze – mnożenie zmieni się w dodawanie. Po zakończeniu analizy można będzie powrócić do liczb naturalnych. Efektem okaże się zaskakująco prosty wzór na wygrywające przedziały:

Konkretne przedziały otrzymamy podstawiając t=0,1,2,…

Sprawdźmy działanie i obsługę wzoru dla rozwiązanego wyżej wariantu (C=1000, k=9). Wzór przybierze postać:

Dla t=0 mamy zwycięski finał. Dla t=1 otrzymamy [55,5(5); 111,1(1)[. Ponieważ jednak liczby powinny być całkowite, zaś przedział jest z lewej strony domknięty, a z prawej otwarty (odwrócona klamra), więc ostatecznie otrzymamy właściwy przedział [56; 111]. Dla t=2 jest [3,0864; 6,1728[, a więc po uwzględnieniu liczb całkowitych zwycięskie [4; 6].

W analogiczny sposób łatwo sprawdzić, że dla C równego milion gracz N jest na straconej pozycji, bo wygrywający przedział startowy nie obejmuje liczb jednocyfrowych większych od 1. Odzyskałby szansę na wygraną po wydłużeniu przedziału do k=10. Wówczas komplet korzystnych dla N rozgrywek (nieparzystych ruchów) wyglądałby tak:

1N. 7_10

(2P. 14_100)

3N. 125_250

(4P. 250_2500)

5N. 2500_5000

(6P. 5000_50000)

7N. 50000_99999

(8P. 100000_999990)

9N. ≥1000000

A gdyby C było równe 1 234 567 890, to czy gracz N miałby zapewnioną wygraną przy k=9 czy 10?

Opisane gry są blisko spokrewnione z silnie zadomowioną od ponad wieku w matematyce rekreacyjnej grupą gier o nazwie nim. Główna różnica polega na tym, że nim i jego odmiany są subtraktywne, czyli w trakcie rozgrywki ciągi liczbowe maleją do zera – zwykle każda następna stanowi różnicę między poprzednią a jednym z odjemników określonych w regułach gry. Zwykle też zamiast abstrakcyjnych liczb pojawiają się konkretne obiekty, np. kamyki lub pionki, które tradycyjnie dzielone są na dwie lub więcej grup, a ich liczebność maleje alternatywnie. W najbardziej znanym klasycznym wariancie nima mamy trzy liczby – 3, 5 i 7. Ruch polega na zmniejszeniu tylko jednej z nich o dowolną liczbę, nawet do zera. Wygrywa, kto wykonuje ostatni ruch, czyli doprowadza do tercetu 0, 0, 0.

Powróćmy jednak do gier addytywnych, a więc z ciągami rosnącymi – choć niekoniecznie – co sugeruje nazwa (łac. adde – dodatek) – powstającymi bezpośrednio w wyniku dodawania. Wśród reguł rządzących tworzeniem wymienianych liczb na uwagę zasługują jeszcze przynajmniej dwie.

Zadanie z pierwszą regułą należy do tzw. matematycznego folkloru. Na początku jest dwójka. Gracz N dodaje do niej 1, tworząc 3. Każdy następny ruch polega na dodaniu do poprzedniej sumy liczby mniejszej od niej, ale większej od zera. Gracz P w drugim ruchu wybiera więc między utworzeniem sumy 4 lub 5. Teraz pełny zakres możliwych ruchów N obejmuje sumy od 5 do 9 itd. Liczba, do której dotarcie oznacza wygraną, jest kwestią wyboru, ale nie ma wpływu na prosty sposób ustalenia zwycięzcy. Jeśli np. założymy, że celem jest 2020, to ciąg sum, zmierzających ku wygranej, zapisany od końca, wygląda tak: 2020, 1010, 505, 252, 126, 63, 31, 15, 7, 3. Dowód, że każda finalna liczba należąca do tego ciągu zapewnia zwycięstwo graczowi N, zaczyna się od oczywistego stwierdzenia, że każda ma postać 2k lub 2k+1 (k>2). Jeśli założymy, że jest ona wygrywająca, to wygrywającą jest także liczba k. Jeżeli bowiem jeden gracz uzyskuje sumę k, to drugi może doprowadzić tylko do sumy z przedziału [k+1; 2k-1], na co pierwszy odpowie sumą 2k lub 2k+1. Początkowe k=3 prowadzi więc prosto do sukcesu, gdy liczba docelowa należy do ciągu: 6, 7, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, …. Tworzą go liczby większe od pięciu, których zapis w systemie dwójkowym zaczyna się od 11. Stąd każda finalna liczba z przedziału [1536; 2047] zapewnia zwycięstwo graczowi N.

Druga ciekawa reguła występuje w zadaniu z „palcówką” – grą zaproponowaną uczniom szkoły podstawowej przez amerykańskiego matematyka Dawida Silvermana. Dwaj gracze na przemian pokazują liczby na palcach jednej ręki. Liczby są cały czas dodawane, a suma po każdym pokazaniu (też liczba startowa) powinna być liczbą pierwszą. Kto jako pierwszy nie będzie w stanie „wypalcować” większej liczby pierwszej – przegrywa. Przed odpowiedzią na pytanie, ile palców pokazać na początku, aby wygrać, należy oczywiście uporać się ze znacznie prostszym zadaniem: znaleźć dwie najmniejsze liczby pierwsze, między którymi jest co najmniej pięć liczb złożonych. Mniejsza z nich będzie równa sumie, do której dotarcie zagwarantuje zwycięstwo, jeśli naszym przeciwnikiem nie okaże się… sześciopalczasty kosmita, który po 23 – bo o taką sumę chodzi – sięgnie 29 i w końcu wygra, doprowadzając do 53. Czy aby trafić w 23 powinniśmy zacząć od 2, 3 czy 5 palców? – samodzielne rozstrzygnięcie tego dylematu może być dobrym ćwiczeniem przed podobnym, ale trudniejszym zadaniem konkursowym.

Autorem kilku podobnych, wartych przeanalizowania gier liczbowych z ciągami jest znany amerykański teoretyk gier, zwłaszcza hazardowych, Richard Epstein. Wśród nich znajduje się jedna nieco zawiła, równocześnie addytywna i subtraktywna. Rozgrywka zaczyna się od wylosowania całkowitej, dodatniej liczby startowej, po czym gracze na zmianę przekształcają ją na jeden z dwu sposobów: w każdym ruchu można zmienić poprzedni wynik, dodając do niego lub odejmując największy możliwy, ale nie większy od tego wyniku kwadrat. Regułę tę można zapisać wzorem

Wygrywa, kto jako pierwszy uzyska zero. Rozgrywka jest kłopotliwa do analizy ze względu na teoretyczną niejednoznaczność – trudno ustalić ogólne reguły związane z liczbami startowymi. Przypomina w związku z tym grę losową, więc nic dziwnego, że Epstein poświęcił jej fragment jednego z rozdziałów swej klasycznej, kilkakrotnie wznawianej, choć dziś nieco kontrowersyjnej książki o matematyce hazardu*. Niektóre przypadki są łatwe do analizy i interesujące. Na przykład, reakcja na 11 oznacza wygraną, bo umożliwia utworzenie 20, na co przeciwnik ma dwie odpowiedzi – 20–16=4 lub 20+16=36, ale każda z nich prowadzi do zwycięskiego zera. Natomiast 5 równa się natychmiastowej porażce, bo można je zmienić tylko w kwadrat – 1 lub 9. Najciekawsza sytuacja wiąże się z trójką i dwójką. 3 można bezpiecznie zmienić tylko na 2, a z kolei z dwu możliwych reakcji na 2 bezpieczna jest tylko zmiana na 3. Powstaje zatem osobliwa dla tego rodzaju gier pozycja remisowa. Łatwo sprawdzić, że poza dwójką i trójką do remisowej pary 2–3 prowadzi także 7 (rys. 1; zielone strzałki oznaczają ruch prowadzący do wygranej, czerwone – do przegranej, niebieskie – do remisu). Trudniej wykazać – ze względu na rozmiary drzewa gry – że przy bezbłędnej grze obu stron do remisu prowadzą także liczby 6, 8, 10, 12, 13, 15, 17, 18, 19, 22, … i nieskończenie wiele innych. Ustalono tylko kilkadziesiąt początkowych wyrazów ciągów liczb przegrywających (gracz N w jednym z kolejnych ruchów nie ma wyboru – zostaje zmuszony do utworzenia kwadratu): 5, 20, 29, 45, 80, 101, 116 … oraz wygrywających (kwadraty i liczby nieuchronnie prowadzące gracza P do kwadratów): 1, 4, 9, 11, 14, 16, 21, …. W przypadku wielu liczb wygrywających droga do celu jest nieprosta, bo wiedzie przez liczby znacznie większe od startowej. Tak jest np. dla 92 (rys. 2). Gra Epsteina wciąż pozostaje obiektem zainteresowania teoretyków liczb i gier. Powstało też kilka jej odmian, w których kwadraty zastąpiono innymi liczbami, np. Fibonacciego lub trójkątnymi.

Autorem innej równie interesującej addytywno-subtraktywnej gry liczbowej jest znany z wielu dokonań na polu matematyki rekreacyjnej John Horton Conway. Dwaj gracze na zmianę podają liczby całkowite większe od 1. Żadna nie może się powtórzyć i żadna nie powinna być sumą wielokrotności dowolnych liczb podanych poprzednio (także wielokrotnością jednej z nich). Kto nie będzie w stanie wymienić liczby spełniającej ten warunek – przegrywa. A zatem rozpoczęcie dwójką lub trójką jest równoznaczne z natychmiastową porażką, bo przeciwnik odpowie drugą z pary {2, 3}, a nie ma takiej liczby większej od 1, której nie można by przedstawić w postaci sumy 2x+3y (x,y≥0). Gdyby natomiast po dwóch pierwszych ruchach na tapecie znalazła się para {3, 4}, to gracz wykonujący trzeci ruch, czyli N, wygrałby, wymieniając 5, bo wówczas wszystkie pozostałe liczby można by wyrazić wzorem 3x+4y+5z. Stąd wniosek, że odpowiedzenie na trójkę dwójką to dobry ruch, ale czwórką – nie. Jaka w takim razie powinna być reakcja na początkową czwórkę, aby prowadziła do wygranej, o ile to w ogóle możliwe?

W niektórych przypadkach kluczem do odpowiedzi na to pytanie – dotyczące zresztą reakcji nie tylko na czwórkę, ale na dowolną liczbę startową – jest twierdzenie i wzór podane w roku 1884 przez angielskiego matematyka Jamesa Sylvestra: każdą liczbę naturalną większą od abab można przedstawić w postaci ax+by, jeśli a i b są liczbami naturalnymi względnie pierwszymi (nie mają wspólnego dzielnika), zaś x i y – liczbami całkowitymi nieujemnymi.

Wracając do gry – gdybyśmy po czwórce podali np. piątkę, to przeciwnik, czyli gracz N, musiałby szukać następnego ruchu wśród liczb nie większych niż 4×5–4–5=11, bo każda większa jest określona wzorem 4x+5y. Liczbę takich liczb określa wzór (a–1)(b–1)/2–1, a zatem w tym przypadku jest ich pięć: {2, 3, 6, 7, 11}. Łatwo sprawdzić, że jeśli N wybierze 11, to pozostawi kwartet {2, 3, 6, 7} i wygra co najwyżej w czterech ruchach. Zatem piątka jako drugi ruch po czwórce oznacza porażkę „piątkowicza” P. A szóstka? Tym razem wzór Sylvestra nie działa, bo 4 i 6 nie są względnie pierwsze, ale łatwo zauważyć, że po pojawieniu się na początku dubletu {4, 6} graczowi N pozostaną do wyboru dwójka i wszystkie liczby nieparzyste. Liczby te można połączyć w pary: {(2, 3), (5, 7), (9, 11), … , (4k+1, 4k+3)} dla k≥1. Teraz P ma prostą strategię wygrywającą: podawać zawsze drugą liczbę z tej pary, z której liczbę wymienił N w poprzednim ruchu, bo pojawienie się pary liczb 4kn+1 i 4kn+3 eliminuje z gry wszystkie liczby większe od 4kn+1.

A zatem wiemy, jak zakończy się gra, gdy N zacznie dwójką, trójką, czwórką lub szóstką (drugim ruchem jest 4) – zawsze zwycięży P. A co z pozostałymi liczbami startowymi? Stopień zawiłości analizy rozgrywek zaczynających się od 5, 7 i wyższych liczb szybko rośnie. Dotąd udało się ustalić finały i strategie partii rozpoczynających się od wszystkich liczb z przedziału [2, 15] oraz kilku większych – rzecz jasna przy najlepszej grze obu stron. We wskazanym przedziale N wygrywa tylko, gdy zacznie od 5, 7, 11 i 13. Znane jest w związku z tym twierdzenie, że jeśli partia zaczyna się od dwóch liczb względnie pierwszych, to wygrywa zawsze N; inaczej mówiąc, wygraną zapewnia rozpoczęcie liczbą pierwszą. Dowód tego twierdzenia jest jednak niekonstruktywny – korzysta z tzw. kradzieży strategii, a w związku z tym nie podaje konkretnego sposobu na sukces. Największą zagadką pozostaje liczba startowa 16. Na tego, kto ustali, komu w tym przypadku przypadnie zwycięstwo, czeka nagroda w wysokości tysiąca dolarów (biorąc pod uwagę trudność zadania, raczej symboliczna) ufundowana przez Conwaya. Ustalenie powinno być oczywiście solidnie udowodnione i wsparte opisem strategii.

Zadania

1. Gra z komputerem polega na pisaniu liczb na ekranie. Komputer zaczął jedynką. Człowiek wystukał dwójkę. Dalej obie strony piszą liczby na przemian, a każda kolejna powinna być albo większa o jeden, albo większa dwukrotnie – od dowolnej, która na ekranie pojawiła się wcześniej. Po dwójce komputer może więc umieścić na ekranie trójkę lub czwórkę, a następnie człowiek na trójkę odpowie czwórką lub szóstką, a na czwórkę – trójką, piątką lub ósemką. Zabronione jest powtarzanie takich samych liczb. Kto wygra – człowiek czy komputer – zakładając, że obaj wykonywać będą najlepsze ruchy, jeśli celem jest napisanie liczby 1000?

2. Dwaj gracze na przemian pokazują liczby na palcach obu rąk, a więc od 1 do 10. Liczby są cały czas dodawane, a liczba startowa oraz suma po każdym pokazaniu powinna być liczbą pierwszą lub kwadratem. Kto jako pierwszy nie będzie mógł „wypalcować” właściwej liczby – przegrywa. Inaczej mówiąc – wygrywa, kto wykona ostatni ruch. Gracz N ma na początku siedem możliwości: 1, 2, 3, 4, 5, 7, 9. Którą z nich powinien wybrać, aby wygrać?

3. Dwaj uczniowie uczestniczą w grze, polegającej na pisaniu na tablicy bardzo długiej liczby X. Ruchy polegają na dopisywaniu na przemian przez każdego po jednej kolejnej cyfrze, ale w grę wchodzą tylko cyfry 1, 2, 3, 4, 5. Celem tego, który zaczął (gracz N), jest uniemożliwienie przeciwnikowi (P), a więc wykonującemu parzyste ruchy, utworzenia liczby X podzielnej przez 9. Komu, N czy P uda się osiągnąć cel, zakładając że żaden nie popełni błędu, jeśli finałem pojedynku będzie liczba X: a) 20-cyfrowa; b) 30-cyfrowa?

Rozwiązania prosimy nadsyłać do 31 grudnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 12/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ą Jak nauczyć teorii względności swojego psa Chada Orzela 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

*Richard Epstein, The Theory of Gambling and Statistical Logic, Academic Press, 2012.

***

Rozwiązania zadań z numeru październikowego

1. Dziesiąty wyraz w ciągu – 84; ciąg: 6, 8, 15, 20, 21, 28, 45, 60, 63, 84, 112, 180, 189, ….

2. a=141, b=188, c=235 (c2=a2+b2=55225, 552=23×24).

3. a=112, b=418.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Nathalie Deruelle, Jeana-Pierre’a Lasoty Fale grawitacyjne. Nowa era astrofizyki, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Maciej Barełkowski z Kostrzyna, Dariusz Laskowski z Bydgoszczy, Paulina Rowińska z Łomianek, Sonia Warzyńska z Tarnobrzegu, Marcin Wojtkowski z Warszawy.

Świat Nauki 12.2019 (300340) z dnia 01.12.2019; Umysł giętki; s. 70

Ta strona do poprawnego działania wymaga włączenia mechanizmu "ciasteczek" w przeglądarce.

Powrót na stronę główną