Wykładanie prostokątów

W kwietniowym UG z ubiegłego roku gościły prostokąty dominowe, czyli takie, których jeden bok jest dwukrotnie dłuższy niż drugi. Temat dotyczył jednak tylko części zagadnień związanych z tymi figurami, a konkretnie – dominowych parkietaży oraz niektórych łamigłówek. Pora na rozwinięcie i uzupełnienie.

Tym razem punktem wyjścia będzie formalnie prosta gra typu papier-ołówek, a więc pozornie niemająca z dominowymi prostokątami nic wspólnego. Grę spopularyzował na początku lat 50. ubiegłego wieku amerykański brydżysta i kryptolog (pracownik agencji wywiadu) Geoffrey Mott-Smith.

Na kartce w kratkę wydzielane jest pole gry, obejmujące układ punktów, zwykle prostokątny; punktami są skrzyżowania linii. Dwaj gracze wykonują ruchy na przemian. Każdy ruch polega na połączeniu poziomym lub pionowym odcinkiem dwóch sąsiednich punktów. Żaden punkt nie może łączyć się z dwoma punktami. Inaczej mówiąc: żaden z pary punktów łączonych w danym ruchu nie może być połączonym wcześniej z innym punktem. Wygrywa, kto wykona ostatni ruch.

Na rys. 1a oznaczony jest początek, a właściwie prawie połowa przykładowej rozgrywki na polu obejmującym 15 punktów (3×5). Mimo tak małej „planszy” gra nie jest trywialna. Rozpoczął czerwony i po jego drugim ruchu pozostały nietknięte dwa odrębne kropkowe fragmenty (żółte). W każdym z nich można wykonać dwa i tylko dwa ruchy, więc w sumie do końca partii pozostały dokładnie cztery. Zatem ten, na kogo teraz przypada posunięcie (niebieski) – przegra, bo ostatnie połączenie narysuje jego przeciwnik (czerwony). Ta krótka analiza sytuacji stanowi zalążek strategii, ale przed jej nieco szerszym omówieniem zmienimy entourage.

Gdy gra „trafiła pod strzechy”, punkty zastąpiono kratkami, a łączenie punktów przekreślaniem sąsiednich kratek, więc przykład z rys. 1a przybrał postać taką, jak na rys. 1b. Potem pojawiły się rekwizyty – układane na planszy domina (rys. 1c). I tak pozostało.

Nietrudno zauważyć, dlaczego przykładowa rozgrywka toczy się na prostokącie o nieparzystej liczbie pól. Następstwem parzystej liczby kratek wzdłuż przynajmniej jednego boku prostokąta byłaby bowiem trywialna strategia. Partii na planszy p×p (p – parzyste) nikt nie chciałby rozpocząć, bo oznaczałoby to pewną porażkę. Wystarczy, aby przeciwnik zastosował tzw. strategię symetryczną, czyli kładł każdy kamień symetrycznie względem środka planszy w stosunku do położonego w poprzednim ruchu przez przeciwnika (symetria środkowa). Przebieg zakończonej przegraną zaczynającego (czerwony) partii na planszy 4×4 mógłby wyglądać np. tak, jak na rys. 2a. Z kolei na planszy p×n (n – nieparzyste) każdy chciałby partię rozpocząć, umieszczając pierwszy kamień dokładnie w centrum i stosując strategię symetryczną od swojego drugiego ruchu. Wówczas zwycięska dla czerwonego partia na planszy 4×5 mogłaby mieć przebieg taki, jak na rys. 2b. W praktyce sensowna jest więc tylko potyczka na prostokątnej planszy o nieparzystej liczbie pól, która zwykle jest kwadratem 7×7, zaś gra nazywa się wykładanka lub z angielska – cram (wciskać, wpychać). Analiza komputerowa rozgrywki na takiej planszy wykazała, że rozpoczynający ma strategię wygrywającą, czyli może zapewnić sobie zwycięstwo, jeśli będzie wykonywał najlepsze ruchy. Niestety, strategia nie jest znana, poza teoretycznymi ogólnikami. Praktycznie o elementach strategii można mówić dopiero od etapu, w którym 49-polowy obszar dzielony jest dominami na mniejsze obszary. Dążą do tego obie strony, bo wtedy logiczne wnioskowanie staje się prostsze lub nawet w ogóle możliwe.

Istotne jest ustalenie, czy dany obszar, złożony na ogół z nie więcej niż 10 kratek, jest wygrywający (W) czy przegrywający (P) dla gracza, na którego przypada ruch. W praktycznej grze kształty takich obszarów są nieregularne, ale gwoli jasności wykorzystamy jako przykład najmniejszą planszę – 3×3. Na rys. 3 znajduje się fragment drzewa gry na takiej planszy, obejmujący wszystkie układy, które mogą się pojawić w trakcie dwóch początkowych ruchów. Po drugim ruchu wolny obszar zmniejsza się do pięciu kratek i wówczas łatwo określić, czy jest on W czy P. Jeżeli wśród możliwych układów po danym ruchu przynajmniej jeden obszar jest P, to znaczy, że przed ruchem obszar na planszy był W. Cofanie się w ten sposób prowadzi do oznaczenia początkowego pustego obszaru odpowiednią literą, czyli w tym przypadku planszy 3×3 literą P.

Analogiczne drzewo gry dla planszy 3×3 z usuniętym polem narożnym wydaje się bardziej wybujałe (rys. 4), ale znajduje się w nim więcej obszarów bliźniaczych (taki sam kształt i wielkość). Najistotniejsze jest jednak to, że jeden z pięciu różnych możliwych pierwszych ruchów prowadzi do obszaru P, co oznacza, że taka wyszczerbiona plansza jest W. Na tym drzewie wyraźnie widoczna jest także ważna z punktu widzenia strategii specyficzna cecha obszarów W i P: obszar W zawsze można zmienić w W lub P, odpowiednio kładąc domino, natomiast obszar P da się zmienić tylko w W, nigdy w P. W związku z tym, gdy plansza zostanie podzielona na kilka mniejszych obszarów, możliwa jest ich analiza parami, pozwalająca określić, czy dany układ dwóch obszarów jest W czy P. Podstawę stanowi twierdzenie: dwa obszary P tworzą układ P, zaś obszar P i W to układ W. Równie jednoznaczny wniosek nie jest jednak możliwy w przypadku dwóch obszarów W. Najprostszym, potwierdzającym tę niejednoznaczność przykładem są pary mini-obszarów W na rys. 5. Łatwo sprawdzić, że jedna z tych par tworzy układ P (kto wykonuje ruch, ten przegra), a druga układ W (wygrywa rozpoczynający). Ten przykład wiąże się z typową dla wykładanki strategią obszarów podobnych.

Dwa obszary są podobne, jeżeli można w nich umieścić takie same liczby kamieni oraz na każdy ruch w jeden z tych obszarów można odpowiedzieć takim ruchem w drugi, że obszary te pozostaną podobne. Taką parę tworzy duet obszarów z lewej strony na rys. 5, ponieważ w każdym można ulokować jedno lub dwa domina, co zapisujemy jako [1/2]. Nie są natomiast podobnymi dwa obszary z prawej, bo pierwszy jest [1/2], a drugi [1]. Strategia polega na takim prowadzeniu gry, aby po każdym ruchu na planszy pozostawały tylko pary obszarów podobnych oraz ewentualnie obszary przegrywające, czyli P. W tym celu po ruchu przeciwnika w jednym obszarze podobnym należy wykonać „symetryczny” ruch w drugim.

W sytuacji na rys. 6 po czterech kolejkach dziewiąty ruch przypada na czerwone. Gdzie powinno się umieścić domino, aby wygrać? Jeśli uwzględnić strategię obszarów podobnych, najlepszym wydaje się zapełnienie pól cd-4 (rys. 7), po którym pojawiają się dwa obszary podobne [2/3] oraz trzy podobne [2], które można potraktować także jako P. Poza tym jest obszar P w prawym górnym rogu. W obszarach P niebieski przegrywa, a w obszarach [2/3] zwycięstwo czerwonemu zapewnia wykonywanie „symetrycznych” posunięć – w szczególności odpowiedzią na a-56 powinno być cd-3 (i odwrotnie). Warto zauważyć, że obszar P w prawym górnym rogu, mimo że też jest [2/3], nie tworzy pary podobnych z żadnym z dwu pozostałych obszarów [2/3], bo nie można w nim ulokować domina „symetrycznie” jako odpowiedzi na ruch a-56 lub cd-3.

Matematyków zajmujących się kombinatoryczną teorią gier interesuje przede wszystkim wynik partii wykładanki na różnych planszach, zwłaszcza prostokątnych i oczywiście o nieparzystej liczbie pól. Sposób ustalania tego wyniku jest jednak żmudnym zajęciem dla komputera, polegającym na analizowaniu drzewa gry. Gwoli usprawnienia tej czynności w analizie pojawia się liczba zwana z angielska nimber (number z „literówką”, dającą fragment „nim”, który jest nazwą pokrewnej, klasycznej gry bezstronnej, a więc takiej, w której nie ma podziału rekwizytów na moje i twoje; mój lub twój może być tylko ruch).

Czym jest nimber w drzewie wykładanki najlepiej wyjaśnić na przykładzie. Na rys. 8 powtórzone są dwie skrajne prawe gałęzie drzewa z rys. 4, ale w układzie poziomym i w uproszczonej formie (bez domin). Na każdym poziomie uwzględniono wszystkie całkiem różne (wskazane strzałkami) puste obszary, które mogą powstać po wykonaniu ruchu, czyli po położeniu domina na większym obszarze, znajdującym się piętro wyżej, od którego wychodzą strzałki. Każda gałąź kończy się zerami. Zerowe zakończenie oznacza zupełny brak obszaru albo obszar, w którym nie można wykonać ruchu, bo brak jest prostokąta na domino – a więc porażkę. Od tych zerowych końcówek zaczyna się wpisywanie w poszczególne obszary, czyli w układy pustych pól – nimberów o określonych wartościach (czerwonych liczb). Zasada wpisywania jest następująca: nimber umieszczany w danym układzie pól jest najmniejszą nieujemną liczbą całkowitą, której nie ma wśród liczb wskazanych strzałkami skierowanymi z danego układu ku układom na niższym poziomie. Jeśli więc z układu wychodzi tylko jedna strzałka wskazująca na zero, to w tym układzie pojawi się nimber 1, jeżeli zaś jest odwrotnie, czyli jedyna strzałka wskazuje na 1, to nimberem będzie zero. Teraz jest jasne, dlaczego w obszarze wyjściowym lewej gałęzi na rys. 8 znajduje się zero, a w prawej gałęzi trójka. A główny wniosek związany z nimberami jest następujący: dodatni nimber oznacza obszar W, natomiast zerowy to obszar P, czyli porażka – oczywiście tego, kto ma w tym obszarze wykonać ruch i przy założeniu, że przeciwnik nie popełni błędu.

O prostokątnych planszach wiadomo, że jeśli są n×n, to ich nimber może być zerem lub liczbą dodatnią; jeżeli są p×p, wtedy nimber ogranicza się do zera; gdy są n×p, to nimber ma wartość dodatnią. Analiza gry sprowadza się zatem do ustalania nimberów dla prostokątnych plansz, w których przypadku wzdłuż jednego lub dwóch boków jest nieparzysta liczba kratek. Taka analiza okazała się nieprosta nawet dla wąskich „kiszkowatych” plansz. Wprawdzie jeszcze w latach 70. matematyk amerykański David Singmaster ustalił, korzystając z programu komputerowego, wyniki partii na planszach będących rzędem pojedynczych kratek (1×m; m≤1000), gdy obie strony będą wykonywać najlepsze ruchy, ale już dla plansz 3×m dotąd nie udało się wyjść poza m=20, a dla plansz 5×m ustalenia kończą się na m=10. Gracz wykonujący parzyste ruchy ma szansę na zwycięstwo na planszach n×n znacznie rzadziej niż rozpoczynający: na planszach 3×n dla n=3, 11, 17, 19; na planszach 5×n tylko dla n=5. Co gorsza, na planszach n×p w ogóle nie ma takiej szansy. W tej sytuacji pocieszające jest to, że na planszach p×p może wygrać zawsze i bardzo łatwo – przynajmniej teoretycznie.

Zadania

1. Na rys. 9 jest sześć „plansz” o nieregularnych kształtach. Które z nich są planszami P, czyli gra na nich w wykładankę zawsze zakończy się porażką rozpoczynającego, jeśli obie strony wykonywać będą najlepsze ruchy?

2. Łatwo określić, z ilu ruchów składa się najdłuższa (teoretycznie, bo praktycznie nikt by tak nie grał) partia wykładanki na prostokątnej planszy m×k: mk/2, gdy liczba pól jest parzysta lub (mk–1)/2 przy nieparzystej liczbie pól. Trudniej ustalić najmniejszą możliwą liczbę ruchów, czyli grę do chwili, gdy na planszy pozostaną tylko puste pojedyncze kratki (1×1), a ich liczba będzie największą możliwą. Przykładowa pozycja kończąca najkrótszą, złożoną z 9 ruchów partię na planszy 5×5 przedstawiona jest na rys. 10. Z ilu ruchów składa się najkrótsza partia na standardowej planszy 7×7?

3. Gra w wykładankę na szachownicy 8×8 ma sens przy dodatkowym warunku: nie wolno wykonywać symetrycznych ruchów, czyli kłaść domina symetrycznie względem środka planszy w stosunku do położonego przez przeciwnika w poprzednim ruchu. Rys. 11 przedstawia „niepełną” sytuację w trakcie rozgrywki na takiej planszy. „Niepełną”, ponieważ ujawnione są tylko pola zajmowane przez połówki niektórych (nie wszystkich) domin obu stron – czerwonego (X) i niebieskiego (Y). Zadanie polega na odtworzeniu pełnej pozycji, jeśli wiadomo, że:

a) pola zajmowane przez dwa kamienie tego samego gracza nigdzie nie mają wspólnego boku, a mogą się stykać tylko rogami;

b) kamienie nigdzie nie pokrywają czterech pól tworzących kwadrat 2×2;

c) wszystkie kamienie zajmują spójny obszar, czyli jeden wielokąt (inaczej mówiąc, z pola zajętego przez jakiś kamień można dotrzeć do każdego pola zajętego przez inny kamień, przechodząc zawsze tylko przez boki stykających się kamieni, a nie przez rogi).

W rozwiązaniu wystarczy podać, kto (X czy Y) w ujawnionej sytuacji wykonuje ruch, oraz kto wygra, jeśli obie strony będą wykonywać najlepsze ruchy (w dalszej grze nie obowiązują podane wyżej warunki a, b, c).

Gwoli jasności na rys. 11 u góry znajduje się przykład zadania z rozwiązaniem na mniejszej planszy. Ruch przypada na gracza X, który wygrywa natychmiast, lokując kamień w jedynym wolnym „dwupolu”.

Rozwiązania prosimy nadsyłać do 31 stycznia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 01/21.
Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Chada Orzela Śniadanie z Einsteinem. Zdumiewające zjawiska kwantowe wokół nas 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

***

Rozwiązania zadań z numeru listopadowego

1. Liczbami pierwszymi, których różnica piątych potęg także jest liczbą pierwszą, są 2 i 3.

2. 16, 25, 32, 41 – to cztery liczby, z których trzy są potęgami oraz pięć z sześciu różnic par tych liczb także jest potęgami.

3. 165=324=220=1048576

4. 82. Jest 8+2=10 sposobów zapisania 82 jako sumy czterech liczb, przy czym we wszystkich tych sposobach zapisu występuje 40 różnych liczb: 1+20+21+40, 2+19+22+39, 3+18+23+38, 4+17+24+37, 5+16+25+36, 6+15+26+35, 7+14+27+34, 8+13+28+33, 9+12+29+32, 10+11+30+31.

Za poprawne rozwiązanie przynajmniej trzech zadań książkę Davida Attenborough, Podróże na drugi kraniec świata. Dalsze przygody młodego przyrodnika, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Jakub M. Gac z Kadów, Robert Galiński z Łodzi, Zbigniew Kapusta z Banina, Renata Pasławska z Warszawy, Ireneusz Sowa z Gdańska.