Przeganianie dziurki

Czy szachownicę (8×8), z której usunięto dwa przeciwległe narożne pola leżące na tej samej przekątnej, można szczelnie pokryć kamieniami domina, zakładając, że każdy kamień zasłania dwa pola? To pytanie z długą brodą, klasyka wędrująca po zbiorkach łamigłówek od ponad półwiecza. Jej urok polega na sprytnym i prostym sposobie udowodnienia, że to niemożliwe. Dowodu nie będę przypominał, bo jeśli jakimś dziwnym trafem zdarzy się, że ktoś z moich gości go nie zna, to będzie okazja do pogłówkowania. Warto wspomnieć, że zadanie wymyślił pod koniec lat 40. nie byle kto – sam John von Neumann.

Zabaw dominowo-szachownicowych jest sporo. Ostatnio tkwię w grach typu wykładanka, polegających na umieszczaniu przez graczy na planszy na przemian po jednym kamieniu do momentu, aż ktoś (przegrywający) nie będzie mógł wykonać ruchu. Przy tej okazji trafiłem na ciekawą łamigłówkę podobną trochę do wspomnianej klasyki, ale, jak mi się wydaje, jeszcze bez zarostu.

Dysponujemy prostokątną szachownicą, a właściwie kratownicą lub kratkownicą o wymiarach mxn, gdzie m i n są nieparzyste. Pokrywamy ją kamieniami domina 1×2. Po wykorzystaniu (mn-1)/2 kamieni w pokryciu pozostanie „dziurka”, czyli jedna niezasłonięta kratka. Załóżmy, że znajdzie się ona w rogu planszy. Będzie do niej przylegał krótszym bokiem przynajmniej jeden kamień. Jeśli go przesuniemy, zasłaniając narożną dziurkę, to „przeskoczy” ona za przemieszczony kamień. Teraz możemy przesunąć kolejny kamień, „przeganiając” dziurkę na następne pole itd.

Czy komuś z Państwa uda się udowodnić – albo chociaż przedstawić pomysł na dowód – że postępując dalej w taki sposób można przegonić dziurkę w inny, dowolny róg planszy.
Znany mi dowód oparty jest na pomyśle równie sprytnym, jak klasyka von Neumanna, choć nie tak prostym.

Komentarze

[Jazz_on]

Wyobraźmy sobie, że mamy do czynienia z biało-czarną szachownicą. Przyjmijmy, że jedno z pól narożnych jest koloru czarnego. Wówczas, z powodu nieparzystej liczby wierszy i kolumn, pozostałe narożne pola też muszą być czarne. Określmy położenie każdego pola szachownicy dwiema liczbami (współrzędnymi): numerem wiersza (1,…,n) i numerem kolumny (1,…,m). Położenie wszystkich czarnych pól szachownicy określone jest albo dwiema parzystymi, albo dwiema nieparzystymi liczbami. Każda położona na szachownicy kostka domina przykrywa jedno czarne i jedno białe pole.
Wszystkie ułożone na szachownicy kostki domina da się podzielić na dwa rozłączne podzbiory, z których jeden zawiera kostki o obu nieparzystych współrzędnych czarnego pola (oznaczmy go literą N). Zaś drugi składa się z kostek o obu parzystych współrzędnych czarnego pola (oznaczmy go literą P). Dziura – jak to dziura – ma kolor czarny. Każde przesunięcie kostki domina wzdłuż dłuższego jej boku powoduje przegonienie dziury o dwa pola wzdłuż wiersza albo kolumny, zatem dziura dalej pozostanie czarna. Natomiast przesuwać daje się tylko kostki należące do podzbioru N i każde przesunięcie pozostawia je w tym podzbiorze.
Z powyższego można wywnioskować, że w czasie przeganiania dziury nigdy nie będzie przesuwana kostka domina z podzbioru P. Najważniejsze jest to, że wszystkie kostki z podzbioru N poprzez swoje sąsiedztwo tworzą spójny graf będący zarazem drzewem, a co za tym idzie dziurę można przegonić na dowolne czarne pole o nieparzystych współrzędnych. Czyli można ją także przegonić do dowolnego narożnika.

Przedstawiony powyżej wywód nie jest dowodem w pełnym tego słowa znaczeniu. Jest jedynie szkicem. Należałoby bowiem uzasadnić fragment dotyczący spójności grafu. Nie jest to trudne. Wymaga tylko wykazania, że kostki z podzbioru P nie są w stanie podzielić drzewa utworzonego z kostek podzbioru N na kilka rozłącznych części.
Może ktoś przedstawi inne ciekawsze uzasadnienie. Chętnie się z nim zapoznam.
Z pozdrowieniami,
Jazz_off

[Jazz_on]

PS
W moim poprzednim wpisie, nie wiem dlaczego, 3 kropki zostały zamienione na znak zapytania.
jz

Poprawiłem. To kaprys programu (co gorsza ostatnio usunął wszystkie obrazki; mam nadzieję, że niebawem je przywróci). mp

[marek]

Jazz_onie, szkic dowodu jest prawie OK. Prawie, bo poza udowodnieniem spójności grafu N wypadałoby udowodnić jeszcze jedną jego cechę, a ściślej brak pewnej cechy.
mp

[johny-max]

A ja sie nie zgodze…