LX OM - I - Zadanie 9

Dana jest tablica $2008 \times 2008$ . Dwaj gracze na przemian
wykonują ruchy, z których każdy polega na wybraniu białego albo
czarnego pionka i postawieniu go na wybranym wolnym polu. Wygrywa
ten, którego ruch doprowadził do powstania ciągu 5 kolejnych
pionków tego samego koloru w linii pionowej, poziomej lub ukośnej.

Zbadać, czy istnieje strategia dla gracza rozpoczynającego grę
zapewniająca mu zwycięstwo.

Rozwiązanie

Odpowiedź: Nie istnieje.

Wskażemy strategię gry dla gracza nie rozpoczynającego
(zwanego w dalszej części rozwiązania drugim graczem), która
uniemożliwi graczowi rozpoczynającemu (pierwszemu) zwycięstwo.

Strategię tę można opisać następująco: Jeżeli drugi gracz może
wykonać ruch prowadzący do powstania ciągu 5 kolejnych pionków
tego samego koloru w jednej linii, wykonuje on taki ruch i wygrywa
grę. W przeciwnym razie drugi gracz stawia pionek na polu symetrycznym
względem środka szachownicy do pola, które przed chwilą zajął
pierwszy gracz, i w kolorze przeciwnym niż pionek postawiony
właśnie przez pierwszego gracza.

Rozmiary szachownicy są liczbami parzystymi, więc pole
symetryczne względem jej środka do danego pola jest innym polem.
Opisana strategia jest zatem poprawnie określona: po każdym ruchu
drugiego gracza dowolna para pól szachownicy symetrycznych względem
jej środka składa się albo z dwóch wolnych, albo z dwóch zajętych
pól, wobec czego po ruchu pierwszego gracza pole symetryczne do
pola przezeń zajętego jest wolne.

Wykażemy, że nie jest możliwe, by przy takiej strategii drugiego
gracza gracz rozpoczynający mógł odnieść zwycięstwo.

Przypuśćmy przeciwnie, że pewien ruch pierwszego gracza
zapewnił mu zwycięstwo. Rozpatrzmy pozycję na szachownicy przed
wykonaniem tego ruchu. Jak wykazaliśmy, w tej pozycji dowolne
pole jest zajęte przez pionek wtedy i tylko wtedy, gdy pole doń
symetryczne jest zajęte przez pionek przeciwnego koloru. Zatem
układowi 4 pionków jednego koloru $k$ , który pierwszy gracz przez
postawienie pionka na polu $P$ powiększył do wygrywającego układu
5 kolejnych pionków koloru $k$ w jednej linii, odpowiada w tej
pozycji układ 4 pionków koloru $k'$ przeciwnego do $k$ , a przy tym
pole $P'$ symetryczne do pola $P$ jest wolne. Wówczas jednak, zgodnie
z opisaną strategią, ostatni ruch drugiego gracza powinien polegać
na postawieniu na polu $P'$ pionka w kolorze $k'$ , co prowadzi
do powstania ciągu 5 kolejnych pionków koloru $k'$ w jednej linii,
i w konsekwencji do wygranej drugiego gracza — wbrew założeniu,
że zwycięstwo odniósł pierwszy gracz wykonując kolejny ruch.