Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Oto trzecia część cyklu poświęconego grom kombinatorycznym – zakładam, że Czytelnik zapoznał się już z dwiema poprzednimi. Na rozgrzewkę weźmy
Przykład 1. W grze chrup! gracz I ma strategię wygrywającą.
Dowód. Przypuśćmy, że drugi gracz ma strategię wygrywającą \(\mathcal{W}.\) Gracz I usuwa prawe-dolne pole, przechodząc ze stanu początkowego \(S\) do stanu \(S_1.\) Gracz drugi, według strategii \(\mathcal{W},\) przechodzi z \(S_1\) do pewnego stanu \(T.\) Plansza teraz wygląda tak, jakby gracz II przeszedł od razu ze stanu początkowego do stanu \(T.\) Ale przecież gracz I mógł to zrobić w pierwszym ruchu, a potem samemu stosować strategię \(\mathcal{W},\) która zapewniłaby mu zwycięstwo – i mamy sprzeczność. Fakt, że remis jest niemożliwy, kończy dowód. \(\square\)
To rozumowanie nazywane jest kradzieżą strategii, ale warto sobie uświadomić, że strategia \(\mathcal{W},\) którą chcielibyśmy ukraść... nie istnieje! Jest ona jedynie hipotetycznym wytworem rozumowania nie wprost, które można streścić tak: gdyby \(\mathcal{W}\) istniała, toby nie istniała. W szczególności nie mamy tu żadnych wskazówek, jaka powinna być strategia wygrywająca gracza I, a usunięcie jednej kostki nie zawsze jest dobrym pierwszym ruchem (zob. zadanie 2 z poprzedniego kącika).
Ten sam dowód napisany zwięźlej. Przypuśćmy, że stan początkowy \(S\) jest P. Ponieważ \(S\to S_1,\) stan \(S_1\) jest W. Wobec tego \(S_1\to T\) dla pewnego stanu \(T,\) który jest P. Ale przecież \(S\to T,\) więc \(T\) powinien być W – sprzeczność. \(\square\)
Przykład 2. W grze hex gracz I ma strategię nieprzegrywającą.
by.5cm Dowód. Przypuśćmy, że gracz II ma strategię wygrywającą \(\mathcal{W}.\) Gracz I zajmuje w pierwszym ruchu jakiekolwiek pole, a potem gra tak, jakby to pole – nazwijmy je polem nadmiarowym – było wolne. Wtedy jest w roli gracza II, więc może stosować strategię \(\mathcal{W}\) w każdej sytuacji, w której nie wskazuje ona pola nadmiarowego. Jeśli strategia \(\mathcal{W}\) nakazuje zajęcie nadmiarowego pola, to nic złego się nie dzieje, bo gracz I zajął je wcześniej, jest zatem tak, jakby ruch wskazany przez strategię został już wykonany. Trzeba jednak zająć jakieś pole – gracz I zajmuje pole dowolne i od teraz to ono jest nadmiarowe. W ten sposób gracz I, stosując zmodyfikowaną strategię wygrywającą gracza II, wygrywa (pole nadmiarowe może tylko mu pomóc) – sprzeczność. \(\square\)
Wygląda na to, że jeden z graczy jest w korzystniejszej sytuacji, więc powinien wygrywać. Należy tu jednak uważać, bo czasem to, co uznajemy za korzystne, wcale takie nie musi być (zob. zad. 4). Podobnie jak poprzednio, dowodzimy tu jedynie istnienia strategii wygrywającej dla gracza I, natomiast nie otrzymujemy żadnych informacji o tej strategii.
W rzeczywistości gracz I ma coś więcej – strategię wygrywającą, bo w grze hex remis jest niemożliwy. Dowód tego faktu można przeprowadzić na wiele sposobów, ale tutaj zmieści się tylko następująca intuicja. Patrzymy na obszar złożony z jednego z czerwonych brzegów oraz z czerwonych pól mających z nim połączenie. Jeśli \(C\) nie sięga drugiego czerwonego brzegu, to możemy przejść niebieskimi polami sąsiadującymi ze zbiorem \(C.\)
Zadania
Na tablicy napisano wszystkie dzielniki pewnej liczby naturalnej \(n > 1.\) Ruch polega na wybraniu jednej z liczb, które w danym momencie są na tablicy, a następnie zmazaniu wszystkich jej dzielników wraz z tą liczbą. Przegrywa ten, kto zmaże liczbę \(n.\) Udowodnić, że gracz I ma strategię wygrywającą.
Wskazówka Przypuśćmy, że gracz II ma strategię wygrywającą i jego odpowiedzią na liczbę \(1\) jest \(d.\) Wówczas gracz I może od razu zapisać \(d\) i dalej stosować hipotetyczną strategię gracza II.
Ciekawostka. Gra chrup! na planszy \(k\times l\) jest praktycznie tym samym co gra z zadania dla \(n = p^{k-1} q^{l-1}\) (\(p\) i \(q\) są pierwsze). W ogólności ta gra jest tożsama z uogólnieniem gry chrup! na czekolady wielowymiarowe.Gracz pierwszy w pierwszym ruchu zapisuje liczbę \(1,\) \(2\) lub \(3.\) W każdym kolejnym ruchu gracze na zmianę zamieniają zapisaną liczbę – nazwijmy ją \(n\) – na jedną z liczb \(n+1,n+2,n+3,\ldots,3n.\) Wygrywa ten, po czyim ruchu zapisana liczba przekroczy \(1\) googol. Kto ma strategię wygrywającą?
Wskazówka Jeśli gracz I wybierze \(1,\) to II może odpowiedzieć \(2\) lub \(3.\) Gracz I może wybrać \(2\) lub \(3\) już w pierwszym ruchu.
Gra gomoku jest wzorowana na grze kółko i krzyżyk – gramy na planszy \(19\times19\) i wygrywa ten, kto pierwszy postawi pięć swoich znaczków pod rząd, w linii poziomej, pionowej lub skośnej. Udowodnić, że gracz I ma strategię, która zapewnia mu co najmniej remis.
Wskazówka Wystarczy zastosować argument z drugiego przykładu.
Ciekawostka. W tej grze możliwy jest remis (dlaczego?), choć zdarza się bardzo rzadko (dlaczego?).Gra rex ma taki sam przebieg jak hex, z tą tylko różnicą, że przegrywa gracz, który jako pierwszy zbuduje połączenie. Ocenić poprawność następującego rozumowania:
Każde dodatkowe pole czerwone sprawia, że łatwiej zbudować czerwone połączenie, więc pierwszy ruch utrudnia grę graczowi I. Wobec tego, ponieważ remis nie jest możliwy, gracz II ma strategię wygrywającą.Wskazówka Nadmiarowe pole nie zawsze pomaga graczowi II – może mu zablokować możliwość uniknięcia zbudowania połączenia.
Ciekawostka. W grze rex na planszy \(n\times n\) gracz I ma strategię wygrywającą dla \(n\) parzystych, a gracz II – dla nieparzystych (J. Lagarias, D. Sleator, 1999).Udowodnić, że w grze hex wybór pola w wąskim rogu w pierwszym ruchu jest błędem gracza I.
Wskazówka W odpowiedzi na zamalowanie na czerwono narożnego pola \(P_1,\) gracz II maluje na niebiesko pole \(P_2,\) sąsiadujące z polem \(P_1\) oraz z niebieskim brzegiem. Gracz II przez całą grę halucynuje, że pole \(P_1\) jest niebieskie, a pole \(P_2\) puste. W grze halucynowanej gracz II pełni honory gracza I. Ponadto jeśli istnieje niebieskie połączenie w pozycji z halucynacją, to istnieje również na pozycji oryginalnej.