Pyrgokracja, czyli dominacja wież

Ile wież szachowych trzeba umieścić na szachownicy, aby każde pole było atakowane przez co najmniej jedną z nich? Skoro wiadomo, że wieża atakuje wszystkie pola w wierszu i kolumnie, na których przecięciu się znajduje i do których ma bezpośredni dostęp, i jeśli przyjąć, że pole, na którym stoi, także jest przez nią atakowane – to pytanie jest bardzo proste. Na planszy n×n należy ulokować n wież, bo gdyby było ich n–1, to w jakimś rzędzie (wierszu lub kolumnie) zabrakło by wieży, zaś n–1 umieszczonych wież nie „obsłużyłoby” n pól tego wolnego rzędu. W skrajnym przypadku niezagrożone pozostałoby jedno pole (np. niebieskie na rys. 1a), gdyby żadne dwie z n–1 wież nie stały w tym samym wierszu ani w tej samej kolumnie.

Czy dostawienie wieży na niebieskim polu zapewni pełną dominację? Niekoniecznie. Jeśli bowiem przyjmiemy, że pole, na którym stoi dana figura, nie jest przez nią atakowane – a tak jest w szachach – to na planszy pozostanie 8 niezagrożonych pól z wieżami. Zatem ustawienie wież należałoby zmienić – nie zmieniając ich liczby – na takie, w którym każda znajdzie się w zasięgu jakiejś innej (zakładamy – wbrew szachom – że wieże tego samego koloru mogą się atakować). Tak będzie, gdy w kolumnach (wierszach) ustawimy po jednej wieży, a w k wierszach (kolumnach) więcej niż po jednej, gdzie 1≤k≤n/2 lub 1≤k≤(n–1)/2 (dla n nieparzystych), jak na rys. 1b.

Jeśli najmniej wież ustawionych jest tak, że każde wolne pole jest przez nie atakowane, ale nie każda wieża „widzi” inną wieżę, czyli nie każda stoi w tym samym rzędzie, co jakaś inna – to takie ustawienie nazywamy minimalnym dominującym. Jeśli natomiast wieże umieszczone są tak, jak na rys. 1b, czyli atakowana jest każda z nich i każde puste pole, to ustawienie zwane jest minimalnym totalnie dominującym. Oba te określenia odpowiadają występującym w teorii grafów pojęciom najmniejszych podzbiorów – dominującego i totalnie dominującego. W tym przypadku chodzi o podzbiory zbioru wierzchołków grafu wieży, którymi są pola szachownicy.

Kolej na drugie pytanie, znacznie trudniejsze od poprzedniego: ile jest minimalnych totalnie dominujących ustawień wież na planszy n×n (odtąd określenie „plansza” będzie oznaczać szachownicę n×n lub o podanym konkretnym n, zaś „szachownica” – tylko planszę 8×8)? Dla n=2 i 3 sprawa jest prosta – wszystkie, czyli dwie lub trzy wieże muszą stać w rzędzie, przy czym rzędów – wierszy i kolumn – jest w pierwszym przypadku 4, a w drugim 6.

Dla planszy 4×4 liczba ustawień znacznie wzrasta. Na rys. 2 przedstawione są wszystkie trzy warianty ustawień po jednej wieży w kolumnach, a po dwie w wierszach (do konkretnych ustawień pary przemieszczane są względem siebie w kolumnach). W każdym wariancie różnych ustawień jest 16, ale 8 z wszystkich 48 to powtórki (4 wieże w jednym wierszu). Analogiczny tercet wariantów ustawień będzie, gdy w każdym wierszu znajdzie się po jednej wieży, a po dwie w kolumnach. Stąd ogólna liczba ustawień: (16×3–8)×2=80. Dla n≥5 obliczenia są coraz bardziej skomplikowane, bo rośnie liczba partycji (podziałów) co najmniej dwuskładnikowych bez składnika równego 1 oraz liczba wariantów ustawień wież. Jeśli n=5, to podobnie jak dla n=4 partycja jest jedna (3+2), ale wariantów ustawień (kombinacji) w=10 (rys. 3). Stąd liczba wszystkich ustawień u=[n²×w–n(w–1)]×2=[5²×10–5×(10–1)]×2=410.

Już jednak dla n=8 jest sześć partycji (6+2, 5+3, 4+4, 4+2+2, 3+3+2, 2+2+2+2), a ustawienia trzeba liczyć oddzielnie dla każdej z nich i na końcu zsumować. Końcowy wynik, czyli liczba wszystkich minimalnych totalnie dominujących ustawień wież na szachownicy równa jest 695 424. To oczywiście znacznie więcej niż ustawień dominujących, w których żadna wieża nie atakuje innej (jak na rys. 1a) – tych jest bowiem 8!=40 320. Z drugiej jednak strony to znacznie mniej niż liczba wszystkich minimalnych ustawień dominujących (totalnych i nietotalnych). W takich ustawieniach w każdym wierszu albo w każdej kolumnie musi stać dokładnie jedna wieża. W obu tych przypadkach wieża może stać na dowolnym polu danego rzędu, a więc zarówno dla wierszy, jak i dla kolumn planszy n×n liczba ustawień będzie równa nⁿ, czyli w sumie 2nⁿ. Ten wynik trzeba jednak zmniejszyć o ustawienia minimalnie dominujące, w których żadna wieża nie atakuje innej, bo takie ustawienia objęte są potęgowaniem nⁿ dwukrotnie – dla wierszy i dla kolumn. Stąd końcowy wzór: 2nⁿ–n!, czyli dla n=8 to 33 514 112 ustawień.

Minimalne dominujące (nie totalnie) ustawienia wież są tożsame z rozwiązaniem klasycznego zadania, polegającego na rozmieszczeniu na szachownicy największej liczby wież w taki sposób, aby żadna z nich nie atakowała innej. Niejako standardowym spośród 8!=40 320 rozwiązań na planszy 8×8 jest to przedstawione na rys. 4 – gęsiego na przekątnej. Gdyby wieże rozróżniać, czyli na przykład ponumerować, to wszystkich ustawień byłoby oczywiście (8!)², czyli ponad półtora miliarda. Gdyby jednak wśród 8! ustawień za jednakowe uznać te, które powstają z innych w wyniku obrotu lub/i odbicia lustrzanego, wówczas liczba całkowicie różnych ustawień zmalałaby do 5282.

Tematem rozmieszczania wież interesował się w połowie XVIII wieku Leonhard Euler – zwykle w powiązaniu z innymi zagadnieniami kombinatorycznymi. Przykładem może być powyższy problem rozmieszczenia na szachownicy ośmiu nieatakujących się wież, ale z dodatkowym warunkiem: żadna wieża nie powinna znaleźć się na głównej przekątnej, czyli tej, na której stoją wieże na rys. 4. Chodziło o ustalenie liczby różnych ustawień. Zaproponowany przez Eulera nieco osobliwy warunek dodatkowy wynikał stąd, że tak sformułowane zadanie jest merytorycznie tożsame z na pozór całkiem innym, znanym wcześniej zadaniem autorstwa matematyka Nicolausa II Bernoulliego, które współcześnie ma zwykle łamigłówkową formę:

n różnych listów napisanych do n różnych osób należy umieścić w zaadresowanych do nich n kopertach. Na ile sposobów można to zrobić całkiem błędnie, czyli pomylić się tak, że żaden list nie trafi do właściwej koperty?

Dla n=1 liczba pomyłek W₁=0, dla n=2 pobłądzić można tylko na jeden sposób, czyli W₂=1. Dalsza analiza doprowadziła Eulera do wzoru rekurencyjnego: W_n=(n–1)(W_n–1+W_n–2), który „działa” także dla zadania z n wieżami na planszy i z dodatkowym warunkiem. Wzór ogólny na liczbę takich permutacji z zakazanymi pozycjami, które dziś nazywamy nieporządkami, podał później angielski matematyk William Whitworth. Liczba ta zwana jest podsilnią i oznaczana symbolem !n. A zatem W_n=!n=n![1–1/1!+1/2!–1/3!+…+(–1)ⁿ/n!].

Matematycy, zajmujący się kombinatoryką, rozważali także przypadek układów z bardziej restrykcyjnymi ograniczeniami, odpowiadający takiemu rozmieszczeniu nieatakujących się wież, w którym wolne od nich są obie przekątne. Liczba takich układów, a więc także liczba ustawień wież, jest z kolei tożsama z rozwiązaniem następującej łamigłówki:

Grupa małżeństw i ewentualnie jeden singiel lub singielka planują na mikołajki obdarować się prezentami. Każda osoba ma dać jeden prezent i jeden otrzymać, ale nikt nie może dać prezentu swojej drugiej połowie, ani – co oczywiste – sobie. Na ile sposobów można to zrobić.

Dla jednej osoby (singiel), dwóch (małżeństwo) i trzech (małżeństwo plus singiel) impreza się nie odbędzie, bo spełnić podanych warunków nie sposób. Podobnie ustawienie n wież na planszy tak, aby się nie atakowały i żadna nie stała na przekątnej, nie jest możliwe dla n≤3. Dla n=4 sposoby mikołajkowe (dwa małżeństwa – M₁+K₁ i M₂+K₂) i szachowe są cztery (rys. 5). Problem jako pierwszy opisał w roku 1879 duński matematyk Severin Hertzsprung (bardziej znany jako szachista) i podał wzór rekurencyjny na liczbę permutacji z przekątnymi bez wież:

Wiedząc, że W₂=0, W₃=0 i W₄=4, nietrudno dotrzeć do klasycznej szachownicy, czyli znaleźć wartość W₈=4752.

Opisane zagadnienia dały początek wielu problemom ze „stadkami” wież, które najczęściej mają postać zadań, goszczących w podręcznikach kombinatoryki lub na zawodach matematycznych. Z reguły chodzi w nich o określenie liczebności największego lub najmniejszego stadka oraz liczby różnie usytuowanych stadek. Prześledzimy kilka.

Ile najwięcej wież można umieścić na planszy tak, aby każda atakowana była tylko przez jedną z pozostałych? Łatwo dojść do wniosku, że wieże muszą stać parami w rzędach i żadna z danej pary nie może być widziana przez wieżę trzecią. Para wież w rzędzie obsadzi więc jeden wiersz i dwie kolumny albo jedną kolumnę i dwa wiersze, czyli w sumie 3 rzędy, zaś wszystkich rzędów jest 2n. Stąd wniosek, że wystarczy miejsca dla co najwyżej [2n/3]×2 wież, czyli na szachownicy – dla dziesięciu, jak na przykład na rys. 6.

Z kilku wariantów powyższego zadania najciekawsze wydają się przynajmniej dwa. W pierwszym chodzi o największą liczbę wież tak ulokowanych, aby każda atakowała nieparzystą liczbę innych. Dla obsługi małych plansz przydaje się logika, przy większych dominuje metoda prób i błędów. Na szachownicy z dotychczasowym rekordem są 24 wieże (rys. 7).

Drugie zadanie polega na takim rozmieszczeniu maksymalnej liczby wież, aby każda była atakowana przez co najwyżej trzy inne. Tu do rozwiązania prowadzi wyraźna ścieżka logiczna. Na wstępie warto zauważyć, że każdą wieżę stojącą przy brzegu planszy mogą atakować co najwyżej 3 wieże. Jeśli w ustawieniu, które jest rozwiązaniem zadania, jakaś wieża znajduje się nie przy brzegu planszy, to jej pozycja dzieli dwa rzędy, na których przecięciu stoi, na cztery fragmenty, z których przynajmniej jeden jest pusty. Wzdłuż tego pustego fragmentu wieżę można więc przesunąć do brzegu, nie psując rozwiązania. Podobnie przesunąć można każdą inną wieżę, a zatem możliwe jest takie rozmieszczenie maksymalnej liczby wież, w którym wszystkie one znajdują się przy brzegu planszy i jest ich 28 (rys. 8).

Ile spośród 8! ustawień na szachownicy 8 nieatakujących się wież jest takich, w których wieże stoją tylko na białych polach? W przykładowym ustawieniu na rys. 9 brzegi białych pól oznaczono dwoma kolorami – niebieskim w kolejnych nieparzystych kolumnach, czerwonym w parzystych. W rezultacie 4 wieże znalazły się w niebieskiej otoczce, a 4 w czerwonej. Pola z niebieskim brzegiem tworzą kwadrat 4×4, podobnie jak pola z brzegiem czerwonym i w każdym z nich 4 wieże można rozmieścić bezkonfliktowo na 4! sposobów. Zatem liczba wszystkich ustawień jest równa (4!)²=576.

Na koniec szczypta magii. Numerujemy liczbami od 1 do n² pola planszy n×n – wierszami od góry, w każdym wierszu od lewej do prawej. Prosimy kogoś o ustawienie na planszy n wież tak, aby się nie atakowały, a następnie o zsumowanie liczb na polach zajętych przez wieże. Wcześniej na karteczce zapisujemy sekretną liczbę. Po obliczeniu sumy okazuje się, że jest ona równa sekretnej liczbie. Sztukę łatwo rozszyfrować. Kluczem do sekretnej liczby jest wzór n(n²+1)/2, określający także sumę w kwadratach magicznych n×n.

Zadania

1. Ile najwięcej wież można ustawić na szachownicy (8×8) tak, aby każda była atakowana przez parzystą liczbę wież?

2. Jak ustawić na planszy 4×4 16 wież ponumerowanych od 1 do 16 tak, by każde dwie z kolejnymi numerami, a także dwie z numerami 1 i 16, stały w tym samym wierszu lub w tej samej kolumnie, ale nie na sąsiednich polach?

3. Na szachownicy (8×8) należy ustawić n białych i n czarnych wież tak, aby żadne dwie wieże różnego koloru nie atakowały się. Jaka może być największa wartość n?

4. Na każdym polu szachownicy (8×8) stoi wieża. W kolejnych ruchach zdejmujemy po jednej, ale zawsze usuwając tylko taką, która atakuje nieparzystą liczbę wież. Ile najwięcej wież uda się w ten sposób zabrać z szachownicy?

Rozwiązania prosimy nadsyłać do 31 marca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 03/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ą Lee Smolina Niedokończona rewolucja Einsteina. W poszukiwaniu tego, co leży poza granicami teorii kwantowej 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 styczniowego

1. Planszami P (przegrywającymi dla rozpoczynającego) są B, C, F.

2. Najkrótsza partia wykładanki na planszy 7x7 składa się z 17 ruchów.

3. Pełna sytuacja na planszy przedstawiona jest na rys. 10. Ruch wykonuje X, który wygra (jeśli dalej nie popełni błędu), kładąc kamień na d45.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Chada Orzela Śniadanie z Einsteinem. Zdumiewające zjawiska kwantowe wokół nas, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Krystian Bugalski z Gdyni, Aleksander Urban z Rakowa oraz Bartosz Chroł, Karolina Piwko i Joanna Walicka z Warszawy.