Tabuny na polach, czyli o dominacji skoczków

Jeśli na szachownicy narysujemy okrąg o promieniu r=√5 ze środkiem w centrum dowolnej kratki (długość jej boku jest jednostką), to pola, których środki znajdą się na okręgu, będą tymi, na które będzie mógł wykonać ruch skoczek, stojący w środku okręgu, czyli tymi, które będzie atakował (rys. 1). Takiego „niewymiernego” określenia sposobu poruszania się konika szachowego w praktyce oczywiście się nie spotyka. Z reguły √5 zastępowany jest sformułowaniem „jedno pole w rzędzie (wierszu) i dwa w kolumnie” albo odwrotnie, co w istocie wskazuje na przekątną prostokąta 1×2.

Liczba pól planszy n×n (n≥5), które skoczek atakuje, bywa różna, w zależności od miejsca, w którym się znajduje: są to tylko a=2 pola, gdy konik okupuje róg, b=3 – gdy znajdzie się przy brzegu tuż obok rogu, c=4 – gdy stoi na jednym z pozostałych pól przy brzegu planszy lub na polu stykającym się tylko rogiem z narożnym polem, d=6 – gdy od jednego brzegu dzieli go jedna kratka, a od sąsiedniego więcej niż jedna, i wreszcie e=8 – gdy stoi na którymś z pól centralnego kwadratu (n–4)×(n–4) planszy n×n. Wszystkie te warianty dla szachownicy 5×5 są oznaczone na rys. 2. Taka szachownica jest więc najmniejszą, na której konik może wykazać pełnię swych możliwości bojowych (odtąd „szachownica” bez uściślenia będzie zawsze oznaczała planszę 8×8). Gdyby uwzględnić wszystkie plansze n×n dla n≥2 i wszystkie n² pól każdej wypełnić liczbami na takiej zasadzie, jak na rys. 2, to efektem byłby ciekawy ciąg, który mógłby stanowić wstęp do konikowej arytmetyki: 0, 16, 48, 96, 160, 240, 336, 448, … . Każdy wyraz tego ciągu jest sumą liczb na planszy o kolejnym n, poczynając od n=2, czyli wyraża się wzorem: A_n = 4a+8b+[4(n–4)+4]c+4(n–4)d+(n–4)(n–4)e= 8+24+(16n–48)+(24n–96)+(8n²–64n+128) = 8n²–24n+16 = 8(n–2)(n–1). Ciąg jest interesujący ze względu na zaskakujące powiązania z paroma pojęciami geometrycznymi. Na przykład jego wyrazy są 16-krotnie większe od wyrazów tworzących ciąg liczb trójkątnych.

Skoczek to jedyna figura, która:

– nie porusza się po liniach prostych (równoległych do boków lub przekątnych planszy),

– w każdym ruchu zmienia kolor zajmowanego pola,

– nie atakuje żadnego z ośmiu pól sąsiadujących z tym, na którym się znajduje, a więc pozostaje zawsze bezbronna wobec bierki umieszczonej obok.

Między innymi te osobliwości sprawiły, że skacząca figura jest główną bohaterką równie osobliwego działu królowej nauk – matematyki szachowej. W ramach tego działu wiodącym tematem są tzw. wędrówki konia, czyli analiza własności tras obchodzenia przezeń szachownic o różnych kształtach i wymiarach. Bibliografia takich wędrówek jest bardzo obszerna i sięga XVII wieku. Gościły one także przed wielu laty na łamach „Świata Nauki”*. Gwoli ogólnego przypomnienia, w czym rzecz – przykład: najmniejsze plansze, które konik może obejść po trasie zamkniętej liczą 30 pól (6×5 i 10×3). Grafy, będące tymi trasami, oznaczone są na rys. 3.

Tym razem nie będziemy jednak forsować rumaków – zajmiemy się zadaniami, w których wymaga się tylko ich właściwego umiejscowienia.

Zaczniemy od wielkiego tabunu, czyli klasycznego i na pozór trywialnego zadania, polegającego na umieszczeniu na szachownicy największej możliwej liczby nieatakujących się wzajemnie koników (zakładamy, że koniki tego samego koloru mogą się atakować). Trywialność bierze się stąd, że skoro skoczek zawsze atakuje pole innego koloru niż to, na którym stoi, to intuicja podpowiada, że rozwiązaniem jest obsadzenie wszystkich 32 pól jednakowego koloru, np. ciemnych, jak na rys. 4. Jednak intuicja to nie dowód, że 33 pól zająć się nie da.

Dowodów wymyślono kilka. Najprostszy polega na podzieleniu szachownicy na 8 prostokątów 2×4 i zauważeniu, że w każdym można ulokować co najwyżej 4 nieatakujące się skoczki. Zatem na całej szachownicy więcej niż 32 się nie zmieszczą. W innym dowodzie korzysta się z trasy skoczka na szachownicy, zaliczającej wszystkie 64 pola, każde tylko raz – analogicznej do tras na rys. 3, ale niekoniecznie zamkniętej. Na takiej trasie przeplatają się pola ciemne i jasne, więc na kolejnych polach nie można ulokować nieatakujących się koników, czyli więcej niż 32 umieścić nie sposób.

Analogiczny dowód dotyczy wszystkich szachownic n×n, gdy n jest liczbą parzystą – najliczniejszy tabun zgodnie ulokowanych koników tworzy zawsze grupa n²/2 figur. Dla n nieparzystych dowód jest podobny i również prowadzi do wniosku zgodnego z intuicją, czyli że na planszy zmieści się co najwyżej (n²+1)/2 skoczków, okupujących bezkonfliktowo wszystkie pola takiego koloru, jak pole centralne.

Rys. 4 wygląda jak przykład totalnej dominacji skoczków na szachownicy, ale tak byłoby tylko wówczas, gdybyśmy uznali, że pole zajęte przez daną figurę jest przezeń atakowane. Tymczasem w szachach tak nie jest, więc praktycznie na rys. 4 połowa planszy, czyli 32 ciemne pola pozostają niezagrożone, choć są obsadzone figurami. To spostrzeżenie prowadzi do zagadnienia dominacji – działu teorii grafów, zapoczątkowanego formalnie w latach 50. XX wieku, dotyczącego w tym przypadku grafu skoczka. Graf ten składa się z odcinków (krawędzi), łączących środki pól (wierzchołki) i np. dla planszy 5×5 jest plątaniną niebieskich linii na rys. 2.

O dominacji można mówić w odniesieniu do jednego skoczka lub do ich grupy. Pojęcia te nieco się różnią. Dominacja skoczka indywidualisty może być dwojaka:

– słaba, czyli szachowa, gdy skoczek nie atakuje pola, na którym stoi;

– silna, gdy uznamy, że skoczek atakuje zajmowane pole.

W przypadku dominacji grupy (zbioru) skoczków występuje zawsze tylko słaba dominacja, czyli żaden skoczek nie atakuje pola, które zajmuje. Istotne jest, że dominacja grupy zawsze polega na atakowaniu przez nią wszystkich pustych pól, a poza tym dzieli się na trzy rodzaje. Są to:

– dominacja minimalna (D_M), gdy skoczki nie mogą się nawzajem atakować;

– dominacja totalna (D_T), gdy atakowanych jest n² pól, a więc wszystkie, wolne i zajęte;

– dominacja pośrednia (D_P), gdy nie jest istotne, czy skoczki nawzajem się atakują, czy nie; byleby atakowane były wszystkie puste pola.

Podstawowe pytanie dotyczące dominacji grupy brzmi: ile co najmniej skoczków potrzeba, aby zdominowały planszę n×n? Ta najmniejsza liczba zwana jest liczbą dominowania i oznaczana symbolem γ(D). Oczywiście, ze względu na trzy rodzaje dominacji możliwe są trzy odpowiedzi, choć dla planszy danej wielkości niekoniecznie różne.

Problem był po raz pierwszy analizowany pod koniec XIX wieku na łamach francuskiego czasopisma „L’Intermédiaire des mathématiciens” i ograniczał się do dominacji pośredniej na szachownicy i kilku mniejszych planszach. Dla szachownicy ustalono, że mniej niż tuzin koników nie zapewni D_P. Łatwo tego dowieść, choć nieco trudniej odpowiednio rozmieścić skoczki. Najpierw warto zauważyć, że do zdominowania każdych trzech pól oznaczonych na rys. 5 krzyżykami potrzeba trzech koników, co wskazuje na wymagany tuzin. Następnie należy skoczki każdej trójki spróbować tak rozmieścić – po jednym skoczku na polach A, B i C oraz na odpowiednich polach w sąsiedztwie pozostałych krzyżyków – aby:

a) atakowane były cztery pola narożnego kwadratu 2×2, bo są one w zasięgu tylko jednej trójki;

b) liczba nieatakowanych pól narożnej ćwiartki 4×4 była jak najmniejsza.

Ustawienia spełniające warunek (b) przy spełnionym warunku (a) są w każdej narożnej ćwiartce tylko cztery, ale parami „bliźniacze” – z trzema nieatakowanymi polami (oznaczone kółkami na rys. 6). I jest jedyna nieekwiwalentna (z dokładnością do obrotów i odbić lustrzanych) kombinacja czterech tych ustawień, w dodatku czterech bliźniaczych, która gwarantuje γ(D_P)=12 (rys. 7).

Ta dominacja jest pośrednia, ponieważ atakowane są tylko cztery skoczki, stojące najbliżej środka planszy. Gdyby udało się przestawić je bez utraty dominacji tak, aby nigdzie nie doszło do ataku, to pojawiłaby się D_M. A gdyby położenie pozostałych skoczków zmieniło się tak, że wszystkie przy zachowanej dominacji wstąpiłyby w szranki, wówczas mielibyśmy do czynienia z D_T. W obu przypadkach dokonanie takich zmian jest trudnym zadaniem. Bez wątpienia, aby przekształcić D_P na rys. 7 w D_M lub D_T, konieczne będzie zwiększenie liczby skoczków, czyli γ(D_M) i γ(D_T) będą większe niż 12. Wydaje się też, że zacząć należy od niektórych spośród najkorzystniejszych elementarnych ustawień z rys. 6. Zmierzając ku D_M z najmniejszą liczbą skoczków, można by na przykład zacząć od dwu niekolidujących ze sobą tercetów z rys. 7, czyli od układu przedstawionego na rys. 8a. Wcześniej jednak wypada skonkretyzować cel. Utworzenie D_M z 16 skoczków to zadanie trywialne – wystarczy choćby ustawić je po 8 w trzecim i szóstym rzędzie. Zatem ambitnym celem jest D_M, której 13≤γ(D_M)≤15.

24 pola z kółkami na rys. 8a nie są atakowane, więc tylko w nich wolno lokować skoczki – oczywiście tak, aby sobie nie zagrażały. Symetryczny układ tych pól sugeruje, że γ(D_M) powinna być liczbą parzystą. Warto więc spróbować, czy każdego tuzina kółek w górnej i dolnej połowie planszy nie uda się pokojowo zdominować czterema skoczkami. Kuszące wydaje się umieszczenie konika na różowym kółku, bo wówczas atakuje on 4 kółka, czyli w sumie eliminuje 5 pól. Jednak po dwu takich „różowych” ruchach u góry i u dołu planszy pozostanie po 7 nieatakowanych pól, których w żaden sposób nie uda się „obsłużyć” bezkonfliktowo trzema skoczkami. Alternatywnym rozwiązaniem jest równie owocne, bo także eliminujące po 5 pól, postawienie koników na dwóch niebieskich polach. Dalej po kilku próbach udaje się bezpiecznie ustawić po 3 skoczki na 7 nieatakowanych polach w górnej i dolnej części szachownicy, czyli doprowadzić do γ(D_M)=14 (rys. 8b). Dwa koniki mają dwie możliwości lokalizacji (żółte kółka), co praktycznie daje trzy nieekwiwalentne ustawienia. Nie jest znany dowód, że dla szachownicy γ(D_M)=14, ale trzy nieznacznie różniące się układy z rys. 8b są jedynymi znanymi z dominacją minimalną 14 skoczków.

Szukanie liczby dominacji totalnej γ(D_T), czyli najmniejszej liczby skoczków ustawionych na szachownicy tak, by atakowały wszystkie 64 pola, w tym siebie nawzajem, można, podobnie jak przy dominacji minimalnej, zacząć od zauważenia, że rozmieszczenie w taki sposób 16 skoczków jest bardzo proste. Wystarczy np. dostawić 4 koniki w środku szachownicy z dominacją pośrednią na rys. 7. Zakres poszukiwań dotyczy więc 13≤γ(D_T)≤15, a ze względu na parzystość szachownicy można się spodziewać parzystej γ(D_T), czyli równej 14, podobnie jak dla γ(D_M). Tym razem warto zacząć od dwóch prostoliniowych ustawień z rys. 6, lokując 6 koników w rzędzie, jak na rys. 9a. Po tym do zaatakowania pozostaje połowa planszy, czyli 32 pola – 26 żółtych kółek i 6 skoczków, a w arsenale jest 8 koników (jeśli w sumie ma ich być 14).

Umieszczenie 4 z nich w niebieskich kółkach dokonuje „spustoszenia”: niezaatakowane pozostaje tylko 12 pól (rys. 9b), a z nimi łatwo się rozprawić, doprowadzając czterema pozostałymi skoczkami do dominacji totalnej (rys. 9c). Różne nieekwiwalentne ustawienia z γ(D_T)=14 także są trzy. Dwa pozostałe na rys. 10. Osobliwością trzeciego jest brak symetrii.

Matematycy analizowali dominacje skoczków na planszach n×n różnej wielkości. Podstawowe efekty tych analiz, czyli wartości γ(D) dla 3≤n≤14 i dla różnych rodzajów dominacji, przedstawione są w tabeli. W nawiasie przy każdej liczbie dominacji pośrednich podana jest liczba różnych (nieekwiwalentnych) ustawień skoczków z tą liczbą. Zaskakuje duża i okrągła liczba ustawień D_P dla n=11. Poza tym ciekawe są przypadki, gdy γ(D_P)= γ(D_M) lub γ(D_P)= γ(D_T), bo wówczas każdy układ D_M lub D_T jest równocześnie D_P (ale oczywiście nie odwrotnie). Skoro więc na przykład dla n=9 γ(D_P)= γ(D_M)=14 i jest tylko jedno ustawienie D_P, to musi być ono także jedynym D_M (rys. 11). Jeśli natomiast γ(D_P)= γ(D_T)=10 dla n=7 i ustawienia D_P są trzy, to przynajmniej jedno z nich także jest D_T, ale to temat na… jedno z poniższych zadań konkursowych.

Zadania

1. Rys. 12 przedstawia dwa ustawienia D_P skoczków na szachownicy 7×7. Są one bardzo podobne i oba są także D_T. Proszę znaleźć trzecie ustawienie D_P na tej szachownicy z γ(D_P)=10 – całkowicie inne, czyli niepowstające w wyniku obrotu lub/i odbicia lustrzanego któregoś układu z rys. 12. W rozwiązaniu wystarczy podać, czy ustawienie to jest tylko D_P, czy także D_T.

2. Ile najwięcej skoczków można ustawić na szachownicy 6×6 tak, aby każdy z nich atakował dokładnie dwa inne? W przykładzie na rys. 13 ustawionych jest w ten sposób tylko 8 koników. Jako rozwiązanie wystarczy podać liczbę.

3. Na rys. 14 należy oznaczyć trasę (linię łamaną), złożoną z odcinków równoległych do brzegów diagramu. Trasa powinna zaczynać się w jednej czerwonej kropce i kończyć w drugiej, przechodząc po drodze przez niektóre czarne kropki (środki pól). Liczba w każdym skoczku oznacza, ile pól, które zalicza łamana, jest przez niego atakowanych. Trasa nigdzie nie może przechodzić przez cztery pola, tworzące kwadrat 2×2, ani przez pola z konikami. Gwoli jasności nad diagramem znajduje się rozwiązany mały przykład. Jako rozwiązanie wystarczy podać liczbę zakrętów (załamań) trasy i liczbę pól na trasie (rozwiązaniem przykładu jest więc ułamek 7/15).

4. Na rys. 15 jest diagram sudoku. Do pustych pól należy wpisać, jak w typowym zadaniu tego rodzaju, cyfry od 1 do 9 tak, aby w każdym wierszu, w każdej kolumnie i w każdym kolorowym sektorze znalazło się dziewięć różnych cyfr – od 1 do 9. Jest jednak dodatkowy warunek: po umieszczeniu konika na dowolnym polu wypełnionego diagramu nie może on jednym skokiem dostać się na pole z taką samą cyfrą, jak to, na którym się znajduje. Inaczej mówiąc: żadna para pól z jednakową cyfrą nie może być sko(mu)nikowana, czyli połączona ruchem skoczka. W rozwiązaniu wystarczy podać dziewięć cyfr na przekątnej łączącej lewy dolny róg z prawym górnym – kolejno od lewego do prawego.

Rozwiązania prosimy nadsyłać do 31 lipca br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 07/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ą Rebekki Wragg Sykes Krewniacy. Życie, miłość, śmierć i sztuka neandertalczyków 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

* Wędrówki konia szachowego. Ian Stewart; „Świat Nauki”, czerwiec 1997.