99 balonów
Tytuł tego wpisu jest „plagiatem” tytułu przebojowego prostest songu Neny z 1983 r. Nena wciąż koncertuje (przed rokiem w Warszawie) skutecznie oszukując wiek — ma tyle lat, ile balonów wyśpiewuje (po obróceniu tej liczby „do góry nogami”). Jej długoletni partner perkusista Philipp Palm namówił ją na grę w „99 balonów”.
W rzędzie wisi 99 nadmuchanych balonów. Nena i Philipp w kolejnych ruchach na zmianę przekłuwają je szpilką, ale nie po jednym — w każdym ruchu wolno przebić tylko dokładnie 3 lub 5 balonów. Przebijanka kończy się, gdy nie będzie można wykonać ruchu, a wygrywa ten, kto wykona ostatni ruch. Nena zaczyna. Kto dysponuje wygrywającą strategią, czyli zawsze może wygrać, jeśli nie popełni błędu – Nena czy Philipp?
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Nena najpierw kłuje trzy (zostaje 96 = 8×12) a potem kontruje Philla do ośmiu w turze Phill – Nena.
Z treści nie wynika, czy przebijane balony muszą wisieć obok siebie czy nie,
ROZWIĄZANIE — WERSJA 1: przebijamy dowolne balony
————————————————-
Liczy się tylko liczba balonów, które zostały.
Przy 0, 1 lub 2 balonach nie ma ruchu, więc gracz, który ma ruch, przegrywa.
Kluczowe spostrzeżenie: 3 + 5 = 8. Na każdy ruch przeciwnika można
odpowiedzieć tak, by w parze ruchów ubyło dokładnie 8 balonów
(on 3 — my 5, on 5 — my 3).
Stąd pozycje przegrywające dla gracza na ruchu to liczby dające resztę
0, 1 lub 2 z dzielenia przez 8:
0, 1, 2, 8, 9, 10, 16, 17, 18, 24, 25, 26, …
99 = 12 · 8 + 3, więc:
1. Nena przebija 3 balony i zostawia 96 — wielokrotność 8.
2. Potem zawsze uzupełnia ruch Philippa do 8.
3. Po każdej jej odpowiedzi zostaje wielokrotność 8, aż w końcu
zostaje 0 i Philipp nie ma ruchu.
Odpowiedź: wygrywa Nena.
ROZWIĄZANIE — WERSJA 2: przebijamy 3 lub 5 balonów wiszących obok siebie
————————————————————————
Pęknięte balony mogą teraz rozdzielić rząd na dwa krótsze.
Strategia symetrii:
1. Nena przebija 3 środkowe balony (50., 51. i 52.). Zostają dwa
jednakowe rzędy po 48 balonów.
2. Potem odpowiada lustrzanie: gdy Philipp przebije jakieś balony
w jednym rzędzie, ona przebija balony na tych samych miejscach
w drugim.
Po każdym ruchu Neny układ jest symetryczny. Jeśli Philipp ma jakiś ruch,
Nena ma ruch lustrzany, więc to Philipp pierwszy zostanie bez ruchu.
(Ten sam pomysł działa, gdy Nena przebije 5 środkowych balonów — zostają
dwa rzędy po 47.)
Odpowiedź: wygrywa Nena.
Sprawdzenie: pełna analiza komputerowa (liczby Sprague’a–Grundy’ego dla
wszystkich długości rzędu do 99) potwierdza, że pozycja startowa jest
wygrywająca dla Neny, a przebicie trzech środkowych balonów jest jednym
z jej zwycięskich ruchów.
Morał: liczba 99 sprzyja zaczynającej. W wersji 1 działa para ruchów
3 + 5 = 8, w wersji 2 nieparzysta liczba balonów pozwala Nenie przebić
środek i odtąd tylko powtarzać ruchy Philippa.
PYTANIE DODATKOWE
—————–
Gra toczy się na tych samych zasadach, ale balonów może być dowolnie wiele,
nie więcej niż 1000. Zaczyna Nena.
Przy jakiej największej liczbie balonów (nie większej niż 1000) wygrywa
Philipp w OBU wersjach gry — zarówno wtedy, gdy wolno przebijać dowolne
balony, jak i wtedy, gdy przebijane balony muszą wisieć obok siebie?
ODPOWIEDŹ NA PYTANIE DODATKOWE
——————————
288.
W wersji 1 Philipp wygrywa, gdy liczba balonów daje resztę 0, 1 lub 2
z dzielenia przez 8; 288 = 36 · 8.
W wersji 2 pozycji przegrywających dla zaczynającego jest bardzo mało
i nie tworzą prostego wzoru. Do 1000 są to:
0, 1, 2, 28, 40, 66, 68, 104, 136, 174, 212, 224, 286, 288, 308, 854
Wszystkie są parzyste — przy nieparzystej liczbie balonów Nena wygrywa
symetrią.
Część wspólną obu warunków tworzą (pomijając 0, 1, 2): 66, 104, 136, 224
i 288. Największa z nich to 288. Kandydaci 308 i 854 odpadają, bo dają
reszty 4 i 6 z dzielenia przez 8.
(Pozycje wersji 2 wyznaczono komputerowo, liczbami Sprague’a–Grundy’ego.)
Liczba Sprague’a–Grundy’ego to ocena pozycji w grze, w której gracze robią ruchy na zmianę i przegrywa ten, kto nie ma ruchu. Najważniejsza jest jedna zasada:
0 znaczy: gracz, który ma teraz ruch, przegra. Każda inna liczba znaczy: wygra.
Jak się ją liczy (na balonach w rzędzie)
Zaczynamy od najkrótszych rzędów i idziemy w górę. Dla każdego rzędu sprawdzamy, jakie oceny mają pozycje, do których można przejść jednym ruchem. Oceną rzędu jest najmniejsza liczba, której wśród nich brakuje.
0, 1 lub 2 balony: nie ma żadnego ruchu, więc wśród ocen po ruchu brakuje już zera. Ocena to 0 (przegrana dla gracza na ruchu).
3 balony: jedyny ruch zostawia 0 balonów, czyli ocenę 0. Brakuje jedynki, więc ocena to 1 (wygrana).
I tak dalej, dla coraz dłuższych rzędów.
Ta reguła „najmniejszej brakującej” oznacza, że z pozycji z oceną 0 każdy ruch prowadzi do pozycji niezerowej. Z pozycji niezerowej da się natomiast zawsze przejść do zera. Wygrywający po prostu zawsze zostawia przeciwnikowi zero.
Po co liczby, a nie samo „wygrana/przegrana”?
Gdy przebijemy balony w środku rzędu, powstają dwa osobne rzędy, czyli dwie gry naraz. Wtedy samo „wygrywa/przegrywa” nie wystarcza, a liczby wystarczą. Ocenę kilku gier naraz liczy się szczególnym dodawaniem. Informatycy nazywają je XOR, w uproszczeniu to „alternatywa wykluczająca – albo” .Najważniejsza właściwość: dwie jtakie same wartości razem dają zawsze 0.(0+0 1+1)
Stąd bierze się symetria Neny. Gdy zostawi dwa rzędy po 48 balonów, ocena całości wynosi 0 dla Philippa, niezależnie od tego, ile jest wart jeden rząd 48 balonów. Philipp przegrywa.
W skrócie: to licznik, który dla każdej pozycji mówi „przegrana” (0) albo „wygrana” (inna liczba). Pozwala też ocenić pozycję złożoną z kilku kawałków. Oczywiście nie ma szans aby to liczyć na piechotę.
Jako zaczynająca, Nena zawsze może wygrać. W swoim pierwszym ruchu Nena powinna przebić 3 balony (zostawiając 96, wielokrotność 8) i w każdym kolejnym ruchu odpowiadać na ruch Philippa tak, aby w sumie w danej turze przebili 8 balonów.
Nena zaczyna od przekłucia trzech balonów.
W każdej następnej kolejce gry Nena reaguje na to, co zrobi przeciwnik (przekłuwa 8 minus ilość balonów przekłutych przez Philipa).
99 = 3 + 12 * 8
Nena przekłuwa 3 balony, a następnie reaguje na ruchy Philippa dopełnieniami do 8.
W uzupełnieniu można dodać, że rozpoczęcie od 5 jest przegrywające, ponieważ
99 = 5 + 5 + 11 * 8 + 1
Jeśli Nena przekłuje 3 balony, to zostanie 96. Teraz na każdy ruch Philippa Nena robi alternatywny, czyli on 3, to ona 5, a on 5, to ona 3. 96 dzieli się przez 8, więc ostatni ruch należy do Neny. Gdyby przekłuła 5 balonów w pierwszym ruchu, to wygrywającą strategię ma Philipp: też przekłuje 5 i potem naprzemiennie z Neną 5-3 lub 3-5. Dochodzimy do 90 przy ruchu Neny, i dalej, jak ona 3, to on 5, i odwrotnie, mamy 98, Nena nie ma już ruchu, ostatni był Philippa.
Ruchu nie można wykonać jak są 0, 1 lub 2 balony. Prosta obserwacja prowadzi do wniosku, że możemy przeciwnika zostawić z którąś z tych (0, 1, 2) ilości balonów startując z 3, 4, 5, 6 lub 7 balonami. Następna obserwacja mówi nam, że jeśli przeciwnik startuje z 8, 9 lub 10 balonami to musi nas zostawić z ilością balonów należąca do zbioru {3, 4, 5, 6, 7} i.t.d. Możemy więc napisać: (0,1,2) [3, 4, 5, 6, 7] (8,9,10) [11,12,13,14,15] (16,17,18) [19,2,21,22,23] i.t.d. Pozycje w nawiasach okrągłych są przegrywające a w kwadratowych wygrywające bo z tych drugich MOŻEMY zawsze zostawić przeciwnika na pozycji z listy przegrywającej a on MUSI nas zostawić na pozycji z listy wygrywającej. Jeżeli startujemy z N balonami to łatwo możemy sprawdzić czy nasza pozycja jest wygrywająca czy przegrywająca. Jeśli (N mod 8) należy do [3, 4, 5, 6, 7] to pozycja N jest wygrywająca. Jeśli (N mod 8) należy do (0, 1, 2) to pozycja N jest przegrywająca. Jeśli świadomy gracz startuje z pozycji “przegranej” to nie wszystko stracone. Jeśli jest na pozycji pierwszej listy 3 elementowej to powinien on wsadzać przeciwnika na pozycję pierwszą (a nie 3) na liście 5 elementowej. W takiej sytuacji gracz nieświadomy może go wsadzić na pozycję wygrywającą lub przegrywającą z prawdopodobieństwami ½ jeśli podejmuje decyzję losowo. Analogicznie z pozycji 3 przegrywającej należy wsadzać go na pozycję 5 (a nie 3) wygrywającą. Z pozycji 3 wygrywającej zawsze wrzuciłby nas w zbiór przegrywający i tracilibyśmy kolejkę na drodze do przejęcia kontroli nad grą. Natomiast z pozycji 2 przegrywającej jest obojętne czy wsadzimy go na pozycję 2 czy 4.Nena
99=3+96=3+8*12
8=3+5=5+3
Pierwsza jest Nena tylko w pierwszym ruchu (3). Dalej jest zawsze druga, dzięki temu może nie zrobić tego samego co Philipp.