Minimum barier

5 lutego 2010
Marek Penszko

Temat podsunął Antyp, nawiązując w komentarzu do jednego z zadań zamieszczonych w bieżącym numerze „Wiedzy i Życia”. Zadanie wygląda tak:

Między polami ustawiono 7 blokad. Należy obejść planszę 6×6 ruchem wieży, goszcząc tylko raz w każdej kratce i kończąc wędrówkę na polu startowym. Inaczej mówiąc, chodzi o narysowanie cyklu wieżowego, a ściślej unikalnego cyklu wieżowego (UCW), bo rozwiązanie jest jedno. Ze szkoły, ale raczej wyższej (nie mam pewności, czy w średniej pojawiają się grafy), wiadomo, że UCW to cykl Hamiltona.

Zadanie jest proste. Znacznie trudniej uporać się z problemem: ile co najmniej blokad wystarczy ulokować na diagramie 6×6, aby ich układ wyznaczał UCW?
Bliźniacze zagadnienie, w którym blokowane są całe pola, a nie tylko przejścia między nimi, zostało już dogłębnie przeanalizowane – przed wielu laty w angielskich czasopismach szachowych, a przed kilku w matematycznych (np. R.K.Guy, M.M.Paulus, Unique Rook Circuits, Mathematics Magazine, grudzień 2002). Wniosek dla formatu 6×6 jest taki, że minimum stanowią 4 zablokowane pola.

Blokad w postaci barier matematycy dotąd nie brali pod lupę. Być może dlatego, że trudniej ustalić reguły rządzące rozmieszczeniem barier w kontekście ustalania minimów. Tak podejrzewam, bo próbowałem i doszedłem do mglistych wniosków, zaś to, co udało mi się ustalić, jest w dużym stopniu dziełem przypadku.

Autor artykułu w „WiŻ” prosił czytelników o informację, jeśli komuś uda się umieścić na planszy 6×6 sześć barier wyznaczających UCW. Zapewne sam przedtem słabo się starał, bowiem okazało się, że nie jest to takie trudne, a różnych ustawień jest sporo. Za karę przysiadł więc wreszcie fałdów, próbując znaleźć układ z pięcioma barierami i udało się:

Byłem prawie pewien, że mniej się nie da, dopóki nie pojawił się komentarz Michała z informacją o przełamaniu rzekomej bariery. Cytuję za przeglądarką arcydziełko Michała z czterema barierami.

Teraz Michał jest prawie pewien, że 3 bariery nie wystarczą, tylko jak udowodnić, że 4 to minimum wyznaczające UCW?

Na koniec „normalne” zadanie, ale niełatwe:

Na diagramie umieszczono jedną blokadę. Proszę dostawić jeszcze dwie tak, aby od A do B można było dotrzeć, goszcząc na każdym polu dokładnie raz i aby droga była tylko jedna (unikalna ścieżka hamiltonowska).
Dla dociekliwych: zadanie ma więcej niż jedno rozwiązanie.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3 dni.