O przechadzce po posadzce

24 marca 2011
Marek Penszko

Nie ma książki z rozrywkami umysłowymi bez błędów. W każdym razie ja takiej nie znam. W mojej ostatniej (Łamigłówki. Podróże w krainę matematyki rekreacyjnej) sam znalazłem kilka, a wnikliwi czytelnicy jeszcze parę dorzucili. Oczywiście, kaliber błędów bywa różny, choć czasem niewinna literówka lub obrócenie rysunku może spowodować spore zamieszanie. Najprzyjemniejsze do znajdywania są błędy polegające na ujawnianiu lepszych rozwiązań, niż autorskie.

W klasycznej, kilkakrotnie wznawianej książce Waltera Shepherda o łamigłówkach labiryntowych (Mazes and Labyrinths), jest zadanie o czyszczeniu posadzki w katedrze. Posadzkę tworzy 96 dużych kwadratowych płyt. Na jednej płycie leży szczotka (S), na drugiej stoi wiadro z wodą (W).

Czyściciel zaczyna pracę na sucho, czyli zamierza najpierw wyszczotkować wszystkie płytki – bez przechodzenia dwukrotnie przez tę samą – zaczynając od S, a kończąc na W, po czym skorzysta z wody, zmywając, co zeskrobał. Jeśli pominąć fabułkę, zadanie sprowadza się do obejścia hetmanem szachowym planszy 8×12 od S do W w taki sposób, aby:
– przez każde pole przejść tylko raz,
– łamana droga składała się z minimalnej liczby odcinków prostych.

Autor informuje, że prostych odcinków może być tylko 23 i proponuje narysowanie trasy czyściciela-hetmana.
Sprytne i eleganckie, bo symetryczne rozwiązanie autorskie wygląda tak:

Dodałem współrzędne przy brzegach, gdyby ktoś miał ochotę pokazać autorowi, że to nie jest najlepsze rozwiązanie, a nie miał ochoty lub możliwości rysować drogi i umieszczać np. w pokazywarce.
Czy trudno jest znaleźć trasę złożoną z mniej niż 23 odcinków? Moim zdaniem nie. A jaka może być najkrótsza? To jest dopiero twardy orzech, dotąd nie rozgryziony.

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