Wielkie granie

Gra hex i punkty stałe

Hex jest jedną z najprostszych i jednocześnie jedną z najciekawszych z matematycznego punktu widzenia gier planszowych. Rozgrywka heksa jest prowadzona na romboidalnej planszy złożonej z sześciokątnych pól. Najbardziej typowe są plansze $11 × 11;$ jak na rysunku, ale można grać na dowolnie dużej planszy.

Reguły gry

Gracze na przemian stawiają na wolnym polu jeden pionek, kolorowy lub szary. Celem gracza I jest połączenie przeciwległych czarnych krawędzi za pomocą łańcucha szarych pionków, jak na rysunku. Taki łańcuch pionków będziemy nazywali wygrywającym dla gracza I. Gracz II chce zbudować łańcuch wygrywający łączący krawędzie kolorowe.

Remisy

Łatwo zaobserwować, że łańcuch wygrywający całkowicie izoluje od siebie krawędzie przeciwnika. Zatem nie mogą istnieć jednocześnie wygrywające łańcuchy dla szarych i kolorowych. A co będzie, jeśli po całkowitym wypełnieniu planszy żaden z graczy nie ma wygrywającego łańcucha? Pokażemy, że taka sytuacja nie może mieć miejsca. Innymi słowy, partia heksa nie może zakończyć się remisem.

Rozważmy przykładową planszę heksa. Dla wygody dodajmy sztuczne rzędy pól wzdłuż krawędzi planszy i oznaczmy skrajne punkty planszy literami: $,S,E,W,N$ jak na rysunku obok.

Rozpoczynając w punkcie $W,$ poruszajmy się po krawędziach między polami według następującej reguły. Na każdym rozgałęzieniu wybierzmy tę z dwóch krawędzi, która oddziela pola różnego koloru. Za każdym razem istnieje dokładnie jeden dobry wybór. Wyobraźmy sobie, że dochodzimy do pewnego rozgałęzienia. Przypuśćmy, że po lewej stronie mamy pole szare, a po prawej kolorowe (tak jak na pierwszym rozgałęzieniu, w wierzchołku $W$ ). Jeśli pole przed nami jest szare, to skręcamy w prawo, jeśli jest kolorowe, to skręcamy w lewo. Zwróćmy uwagę, że dzięki temu zawsze po lewej stronie mamy pola szare, a po prawej kolorowe.

Postępując w ten sposób, nigdy nie wrócimy do wierzchołka, w którym już byliśmy. Przypuśćmy przeciwnie, że doszliśmy do wierzchołka już raz odwiedzonego i że jest to pierwszy taki moment w naszej wędrówce. W takim razie musieliśmy dojść do niego krawędzią, której przedtem nie używaliśmy. Ale krawędź taka zawsze leży między polami tego samego koloru, więc nie mogliśmy jej wybrać - sprzeczność.

Plansza do heksa jest skończona, więc w końcu musimy z niej wyjść. Do dyspozycji mamy jedynie drogi przez $,S,E, |N$ gdyż wszystkie inne wiodą między polami tego samego koloru.

Jeśli ścieżka skończy się w wierzchołku $|S,$ jak to ma miejsce na rysunku powyżej, to wyznacza wygrywający łańcuch dla szarych. Analogicznie, jeśli ścieżka dotrze do wierzchołka $, N$ to wyznacza wygrywający łańcuch dla kolorowych. Zwróćmy uwagę, że ścieżka nie może opuścić planszy przez wierzchołek $|E,$ bo musielibyśmy minąć kolorowe pole po lewej, a szare po prawej.Uwaga!

Strategie

Istnieje sprytna metoda, która pozwala na wykazanie, że w grze hex gracz, który zaczyna (czyli szary), ma strategię wygrywającą. Metoda ta polega na podkradaniu strategii przeciwnikowi. Przypuśćmy, że wygrywającą strategię ma gracz II. Gracz I powinien rozpocząć od zupełnie dowolnego ruchu, a następnie postępować tak, jak nakazuje hipotetyczna strategia gracza II, zamieniając miejscami kolory. Jedyny kłopot, jaki może się pojawić, to sytuacja, w której podkradziona strategia nakazuje zająć pole, na którym już stoi pionek. Może się to zdarzyć tylko wtedy, gdy jest to pionek postawiony podczas rozpoczynającego, losowego ruchu (w przeciwnym przypadku strategia nie wskazałaby tego pola). Wtedy ponownie wykonujemy dowolny możliwy ruch. Jest jasne, że posiadanie dodatkowego pionka na planszy nie pogarsza sytuacji gracza, zatem podkradziona strategia gwarantuje zwycięstwo pierwszemu graczowi. W ten sposób otrzymujemy sprzeczność z założeniem o istnieniu strategii dla drugiego gracza.

Powyższe rozumowanie jest całkowicie niekonstruktywne, nie daje graczowi I żadnych wskazówek odnośnie tego, jak powinien grać. Rozwiązanie tego problemu w praktyce jest bardzo trudne. Dotychczas udało się wyliczyć strategię dla planszy o rozmiarze $9 × 9.$ Mimo to, żeby zniwelować ewidentną przewagę gracza I, zaawansowani gracze dodają dodatkową regułę zamiany. Po tym, jak gracz I postawi pierwszy pionek, gracz II może zdecydować, czy będzie grał kolorowymi, czy szarymi. W ten sposób teoretycznie istnieje strategia wygrywająca dla gracza II, ale w praktyce gra staje się wystarczająco sprawiedliwa.

Dualna plansza

Czy hex może się przydać matematykowi do czegoś poza rozrywką? Okazuje się, że ta prosta gra ma głęboki związek z topologią. Żeby to dokładniej wyjaśnić, zastąpimy planszę do heksa przez planszę dualną. Na planszy dualnej pola reprezentowane są przez wierzchołki. Wierzchołki reprezentujące sąsiednie pola łączymy krawędzią. Dualną planszę $6 ×6$ przedstawia rysunek.

W tej interpretacji gracze stawiają pionki na wierzchołkach i usiłują zbudować ścieżkę łączącą przeciwległe krawędzie kwadratu. Nietrudno zauważyć, że jest to inny opis tej samej gry i wszystko, co powiedzieliśmy o heksie, jest prawdą również dla tej wersji.

Twierdzenie o punkcie stałym

Pokażemy teraz, jak wykorzystać grę hex na dualnej planszy w dowodzie ważnego twierdzenia topologicznego zwanego twierdzeniem Brouwera. Głosi ono, że każde ciągłe przekształcenie kwadratu w siebie pozostawia pewien punkt na swoim miejscu. Jeśli oznaczymy przez $|I2$ kwadrat $|[0, 1] ×[0,1],$ to twierdzenie powyższe można sformułować następująco: dla dowolnego ciągłego przekształcenia $f I2 I2$ istnieje taki punkt $2 |x∈ I ,$ że $f (x) = x.$ Taki punkt nazywamy punktem stałym przekształcenia $| f.$ Zauważmy najpierw, że wystarczy udowodnić, że istnieje ciąg punktów $x1,x2,x3,...,$ należących do $I2,$ spełniających warunek:

1 d( f (xn),xn) < n .

Rzeczywiście, kwadrat $2 I$ jest zbiorem domkniętym i ograniczonym, zatem z takiego ciągu $x1,x2,...$ można wybrać podciąg $xn1,xn2,...$ zbieżny do pewnego punktu $x ∈I2.$ Z nierówności trójkąta otrzymujemy

d( f (x ),x) ⩽ d( f (x ),x )+ d(x ,x). ni ni ni ni

jeśli $1 |d(x,y) < k,$ to $1 |d( f(x), f (y)) < 2n.$

Podzielmy kwadrat $I2$ tak, aby otrzymać dualną planszę do gry hex o rozmiarze $| 2k× 2k.$ Przyjmijmy $| ′ f(x) = x$ oraz $| x = (x1,x2),$ $| ′ ′ ′ x = (x1,x2).$ Przez $|G$ będziemy oznaczali zbiór wierzchołków, które pod wpływem $f$ przesuwają się w górę o co najmniej $21n,$ to znaczy $x′2 −x2 ⩾ 12n.$ Podobnie definiujemy zbiory $, D$ $|L,$ $P$ jako zbiory wierzchołków, które przesuwają się o co najmniej $-1 2n$ odpowiednio, w dół, w lewo i w prawo; przy czym do zbiorów $|L$ i $P$ kwalifikujemy tylko te wierzchołki, które nie trafiły ani do $G$ ani do $.D$

Ustalmy wierzchołki $,y∈D. x ∈G$ W takim razie,

x′2− x2⩾ -1-, y2 − y′2⩾ -1-. 2n 2n

Jeśli $|x$ i $y$ są połączone krawędzią, to ich pionowe współrzędne $|x 2$ i $|y2$ różnią się co najwyżej o $1- |2k,$ a zatem

1 x2 − y2⩾ − --. 2k

Dodając powyższe trzy nierówności stronami, dostajemy

′ ′ 1- -1- x2 −y 2⩾ n − 2k.

Stąd odległość między $x ′$ a $y′$ wynosi co najmniej $21n,$ to jednak jest sprzeczne z tym, że wierzchołki $|x$ i $y$ są połączone krawędzią. Jeśli bowiem dwa wierzchołki sąsiadują ze sobą, to odległość między nimi wynosi najwyżej $-2- |2k$ (długość skośnej krawędzi na planszy dualnej), zatem na mocy wyboru liczby $k$ odległość między ich obrazami musi być ostro mniejsza niż $|1-. 2n$ Wykazaliśmy więc, że wierzchołki ze zbiorów $|G$ i $| D$ nie mogą sąsiadować. Oczywiście, wierzchołki ze zbioru $| G$ nie mogą leżeć na górnej krawędzi planszy, bo stamtąd nie da się pójść do góry. Podobnie wierzchołek ze zbioru $|D$ nie może leżeć na dolnej krawędzi planszy. W takim razie zbiór $∪D |G$ nie może zawierać łańcucha wygrywającego dla gracza chcącego połączyć górną i dolną krawędź. Podobnie $L ∪P$ nie może zawierać łańcucha wygrywającego dla drugiego gracza. Skoro na planszy do gry w hex nie może być układu remisowego, to $∪D∪L∪P G$ nie może wyczerpywać wszystkich wierzchołków planszy. Weźmy dowolny wierzchołek $| xn,$ leżący poza $∪D∪L∪PG .$ Z definicji zbiorów $,D,L,P G$ wynika, że obraz wierzchołka $xn$ jest zawarty w kwadracie o środku $xn$ i krawędzi $|1. n$ Zatem obraz $x n$ jest odległy od $x n$ najwyżej o $- |-2<- -1. 2n n$ Podobny dowód z użyciem zwykłej szachownicy można znaleźć w Delcie 9/1980 (zadania 232-4).

Inny dowód twierdzenia Brouwera, także w wyższych wymiarach, Czytelnik może znaleźć w znakomitych książkach Co to jest matematyka? oraz Dowody z księgi.