Eliminacja dominacji

12 czerwca 2021
Marek Penszko

Amerykański filozof Max Black jest autorem zadania zamieszczonego po raz pierwszy w wydanej w 1946 roku książce „Critical thinking” i uchodzącego dziś za niemal klasyczne:
Czy można kamieniami domina pokryć szachownicę (8×8), z której usunięto dwa narożne pola, leżące na końcach tej samej przekątnej (zakładamy, że kamień domina pokrywa dokładnie dwa pola)?
Po usunięciu pary pól do dyspozycji pozostają 62 pola, więc wydaje się, że 31 kamieni umożliwi pokrycie. Wystarczy jednak zauważyć, że usunięto 2 pola takiego samego koloru (A), zatem pozostało 30 pól A i 32 pola B, zaś każdy kamień domina zasłania jedno A i jedno B. Stąd już tylko krok do odpowiedzi: „nie można”.

Logiczną konsekwencją powyższego zadania wydaje się następujące: czy pokrycie szachownicy dominem będzie możliwe po usunięciu jednego pola białego i jednego czarnego? Nietrudno dowieść, że jest to zawsze możliwe.
Zatem idźmy dalej: czy uda się „zdominować” szachownicę pozbawioną 4 pól – 2 białych i 2 czarnych? W tym przypadku odpowiedź twierdząca wymaga uzupełnienia pytania dodatkowym warunkiem: zubożona o 4 pola szachownica powinna pozostać spójna, czyli nie można np. usunąć dwóch białych pól przy czarnym rogu, odcinając tym samym ów róg – chyba że ten róg także uznamy za odcięty. Spójność wystarcza, aby „dominacja” na 60 polach była zawsze możliwa. A czy będzie możliwa na 58 polach po usunięciu trzech pól białych i trzech czarnych – oczywiście przy zachowaniu spójności planszy? Okazuje się, że teraz dominację łatwo uniemożliwić, ale tylko (? brak dowodu) wtedy, gdy przynajmniej jedno z usuniętych pól znajdzie się przy brzegu szachownicy. Wówczas wystarczy ograniczyć się do wskazania trzech pól jednego koloru, bo już ich rozmieszczenie skutecznie blokuje obsadzanie wszystkich pól kamieniami. Taką blokadę stanowią np. układy b3-c2-b1 lub b3-c2-d1.
Kolej na pytanie finałowe: ile co najmniej białych i czarnych pól – tyle samo jednych i drugich – należy usunąć z szachownicy 8×8, aby pokrycie wszystkich pozostałych pól kamieniami domina nie było możliwe? Ale warunki dodatkowe są tym razem dwa:
– pierwszy tradycyjny – zachowana musi być spójność pozostałej części szachownicy
– drugi „nowoczesny” – nie wolno usunąć żadnego pola brzegowego, czyli „dziury” mogą pojawić się tylko w środku.
Ustaloną liczbę proszę wesprzeć wskazaniem konkretnych odrzuconych pól.

Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.