Zbieranie kamieni, czyli ścieżką Hamiltona inaczej
Moda na diagramowe łamigłówki logiczne przyszła z Japonii. Jej apogeum wiąże się, oczywiście, z sudoku, które podbiło świat w roku 2005 i z czasem weszło na stałe, podobnie jak krzyżówka, do repertuaru rozrywek umysłowych. Później pojawiło się mnóstwo innych łamigłówek z japońskim rodowodem. Niektóre mają spore grono miłośników i goszczą na licznych stronach internetowych lub w specjalistycznych wydawnictwach. Wiele z nich uchodzi za bardzo pomysłowe, zwykle ciekawsze niż sudoku, mimo to popularnością żadna nawet w małej części nie dorównała przebojowi sprzed kilkunastu lat.
Dla osób, które interesują się historią i kulturą Japonii, zwłaszcza w kontekście życia codziennego, fakt, że kraj ten stanowi swojego rodzaju kolebkę łamigłówek, nie jest niczym osobliwym. Gry umysłowe, przede wszystkim go i shõgi (odmiana szachów), były od wieków popularne w ojczyźnie ikebany i origami. Już w XVIII wieku w prasie pojawiły się poświęcone im stałe rubryki, których uzupełnienie często stanowiły różnego rodzaju zadania logiczne i matematyczne. Jeden z tych rodzajów przetrwał próbę czasu i wciąż gości nie tylko w japońskich publikacjach. Wiąże się z grą w go, ale tylko formalnie, tzn. w wersji praktycznej korzysta z planszy i kamieni do tej gry (małych krążków przypominających pchełki), przez której amatorów został wymyślony. Natomiast na papierze lub na ekranie komputera pojawia się diagram, który jest fragmentem planszy, czyli siatki kwadratowej, a na niektórych skrzyżowaniach linii umieszczone są kółka, czyli kamienie. Zwykle jest ich kilkanaście, choć w prostych zadaniach może być kilka, a w trudniejszych nawet powyżej 30.
Cel zabawy jasno określa jej nazwa – goishi hiroi (zbieranie kamieni) lub hiroimono (zbieranie przedmiotów). Jak z tego wynika, jest to łamigłówka wielochodowa, czyli coś w rodzaju logicznego pasjansa, a więc jakby gra dla jednej osoby. Była rozrywką popularną w okresie dziejów Japonii zwanym Edo, czyli od początków XVII wieku, ale najstarsze znane zadania pochodzą z książki poświęconej matematyce rekreacyjnej wydanej w roku 1727. W książce jest ich pięć; pierwsza z tych wiekowych łamigłówek posłuży do objaśnienia zasad zabawy i podstawowych sposobów rozwiązywania.
Rozmieszczenie kamieni na siatce diagramu przedstawia rys. 1. Wszystkie trzeba zebrać w ściśle określony sposób – wędrując wzdłuż linii siatki. Zaczynamy od zabrania jakiegoś kamienia (dowolnego, choć z punktu widzenia strategii – właściwego) i od skrzyżowania, z którego został zabrany, kierujemy się wzdłuż linii ku następnemu, który zabieramy i ruszamy po linii do kolejnego, który też usuwamy itd. Poruszając się w ten sposób, powinniśmy zebrać wszystkie kamienie, czyli w tym przypadku 14. Na trasie trzeba jednak przestrzegać dwu „zasad ruchu”:
1. po dojściu do kamienia trzeba go zabrać;
2. zmienić kierunek ruchu można tylko na skrzyżowaniu z kamieniem, tylko natychmiast po zabraniu go i tylko o 90 stopni; zatem bezpośrednio po usunięciu kamienia dozwolony jest skręt w prawo lub w lewo, ale zabroniony zwrot o 180 stopni, czyli cofanie się.
Uzupełniając zasadę 2: po powtórnym dotarciu do skrzyżowania, z którego został usunięty kamień, skręt na tym skrzyżowaniu nie jest już możliwy.
W klasycznych zadaniach hiroimono, a więc takich, jak to na rys. 1, układ kamieni jest symetryczny lub prawie symetryczny i niemal zawsze bywa spójny, czyli każde dwa kamienie połączone są ścieżką wiodącą wyłącznie przez skrzyżowania z innymi kamieniami. Ponadto z reguły nie ma znaczenia, ile jest rozwiązań. Cel (usunięcie kamieni) uznaje się za ważniejszy niż istnienie jednej drogi do celu. Jeśli, jak na rys. 1, układ jest symetryczny, takie drogi są przynajmniej dwie, a zwykle jest ich więcej. Z reguły na klasycznych diagramach są też widoczne dwa skrajne kamienie trasy – od jednego z nich należy zacząć wędrówkę, a na drugim skończyć. Są to oczywiście te kamienie, od/do których można dotrzeć tylko do/od jednego z pozostałych kamieni, a więc na rys. 1 A i M.
Zacznijmy od A. Możemy pójść prosto do E (A-B-C-D-E) lub skręcić wcześniej w B albo C. Nie możemy natomiast skręcić w D, bo wówczas kamień E pozostałby jako trzeci skrajny. To podstawowa zasada rozwiązywania: nie wybieraj trasy, która powoduje pojawienie się nadliczbowego (w tym przypadku trzeciego) skrajnego kamienia, bo – co oczywiste – każdy kij ma dwa końce, więc obecność trzech skrajnych kamieni czyni zadanie nierozwiązywalnym. Jeśli skręcimy w E, to dalsza droga – E-G-F-H-… – będzie wymuszona powtarzającym się zagrożeniem trzecim skrajnym kamieniem, a w kolejnym ruchu (H-I lub H-J) tego zagrożenia nie da się już uniknąć. Pozostaje więc rozpatrzyć dwa debiuty: A-B-C-K-… i A-B-F-… Kontynuacją pierwszego może być wymuszona trasa (a): K-L-D-E-G-F-H-… i koniec, bo teraz niezależnie od wyboru ruchu (H-I lub H-J) trzeci skrajny kamień musi się pojawić, albo trasa (b): K-J-H-F-G-… i już widać, że droga okrężna po pozostałych kamieniach (rys. 2; różowy kamień jest właśnie zabierany) zgodnie z ruchem wskazówek zegara prowadzi do celu: G-I-Ł-L-D-E-M.
Pozostaje jeszcze sprawdzić skuteczność drugiego debiutu – A-B-F-…. W pierwszej chwili może się wydawać, że prowadzi on do podobnej sytuacji, jak po debiucie A-B-C-… Oba układy różnią się jednak położeniem kamienia M i nietrudno sprawdzić, że z tego powodu układ po drugim debiucie (rys. 3) jest nierozwiązywalny przy startowym kamieniu G lub H. Byłby rozwiązywalny, gdyby kamień M leżał na prawo od Ł (G-E-D-C-K-L-Ł-I-H-J-M).
Rozwiązanie zapisuje się, numerując kolejno odwiedzane kamienie. W przypadku omawianego zadania rozwiązanie graficzne wygląda więc tak, jak na rys. 4, a tekstowe ma postać ciągu liczb spisanych z diagramu rzędami poziomymi od góry do dołu, czyli: 1-2-3-12-13/7-8/6-9/5-4-11-10/14. Ze względu na symetrię układu jest jeszcze drugie rozwiązanie, zaczynające się od M, choć często oba takie rozwiązania, jako bliźniacze, uznaje się za tożsame.
Wśród klasycznych spójnych układów hiroimono można wyodrębnić kilka rodzin. Wspólną cechą tych, które należą do jednej rodziny, jest kształt układów, natomiast różnią się one wielkością. Typowymi przykładami są schody (rys. 5a) i most (rys. 5b; nazwa nawiązuje do tzw. mostu yatsuhashi – elementu japońskich ogrodów). Z „rodzinnymi” hiroimono wiąże się problem matematyczny: dla jakich wielkości układ ma rozwiązanie? W przypadku schodów chodzi o wartość v, określającą zarówno wysokość, jak i szerokość układu; dla mostu istotne są wartości s (szerokość) i d (długość), które mogą się różnić. Nietrudno udowodnić, że schody nie mają rozwiązania tylko dla v=3. Dowód przez indukcję przedstawiony jest na rys. 6. Zielona linia oznacza rozwiązanie dla v=4, czerwona – dla v=5; niebieska stanowi schemat przejścia od rozwiązania dla v=k do rozwiązania dla v=k+2. W ten sposób wychodząc od rozwiązania zielonego, otrzymamy wszystkie rozwiązania dla v parzystych, zaś wychodząc od czerwonego – dla v nieparzystych. Z mostem sprawa jest bardziej skomplikowana i wyjaśniona tylko częściowo, tzn. udowodniono, że rozwiązanie istnieje dla każdego d, jeśli s=4.
W przeciwieństwie do klasycznych, współczesne układy kamieni bardzo rzadko są symetryczne. Można podzielić je na trzy grupy. Do pierwszej należą takie, jak te z rys. 1, 5 i 6, czyli z widocznymi dwoma skrajnymi kamieniami. W jednym z nich trzeba zacząć wędrówkę, a w drugim skończyć – wystarczy więc próbować na dwa sposoby. Druga grupa obejmuje układy z ujawnionym tylko jednym skrajnym kamieniem (przykład na rys. 7 kamień skrajny jest żółty). Tu możliwości jest więcej. Jeśli wędrówka od skrajnego kamienia zawiedzie, pozostaje szukanie startu od któregoś z pozostałych. Tak właśnie jest na rys. 7, ale w tym przypadku jedyny startowy kamień łatwo znaleźć (który nim jest?) i rozwiązanie – oczywiście z metą na żółtym kamieniu – także jest tylko jedno. Trzecią grupę tworzą układy bez widocznych skrajnych kamieni (rys. 8). Teraz trafienie na właściwą drogę wydaje się najtrudniejsze, choć przy założeniu, że rozwiązań może być kilka, błądzenie nie jest zbyt mozolne, a nawet przyjemne – wystarczy w trakcie wędrówki jak najdłużej unikać pojawienia się skrajnego kamienia, pamiętając, że wyklucie się dwóch takich kamieni przed dotarciem do ostatniego oznacza przedwczesne zakończenie trasy, czyli porażkę. Sposobem na ograniczenie błądzenia i jedno rozwiązanie jest wskazanie kamienia startowego. Na ogół tak właśnie bywa, zwłaszcza gdy zadania hiroimono pojawiają się w konkursach lub na turniejach. Na rys. 8 należy zacząć od kamienia G, ale czy to jedyne możliwe miejsce startu? Szukanie innych jest tematem pierwszego zadania konkursowego.
Hiroimono wiąże się z teorią grafów, a konkretnie z tzw. ścieżką Hamiltona. Graf jest zbiorem punktów (wierzchołków) i łączących je linii (krawędzi). Z reguły określenie to dotyczy tzw. grafu prostego, czyli takiego, w którym żadne dwa punkty nie są połączone dwiema krawędziami i żaden punkt nie jest połączony krawędzią z samym sobą (pętla). Jeśli idąc krawędziami, można obejść wszystkie wierzchołki grafu, goszcząc w każdym dokładnie raz, to taka trasa obejścia zwana jest ścieżką Hamiltona. Ścieżkę hiroimono, czyli rozwiązanie każdego zadania tego rodzaju można uznać za jej odmianę znamienną tym, że graf wpisany jest w siatkę kwadratową, a ścieżka spełnia dwa dodatkowe warunki:
– przez wierzchołki można przechodzić więcej niż raz,
– zmieniać kierunek ruchu wolno tylko przy pierwszym przejściu przez wierzchołek.
Wspólną cechą obu ścieżek jest też to, że ich szukanie w grafie należy w teorii obliczeń do tzw. problemów klasy NP (ściślej NP-zupełnych), czyli – nieco upraszczając – takich, których stopień trudności rośnie znacznie szybciej niż liczba danych wejściowych. Na przykład, gdy liczba wierzchołków i krawędzi grafu zwiększy się n-krotnie, to liczba operacji, które należy wykonać, aby znaleźć w nim ścieżkę Hamiltona lub ścieżkę hiroimono może wzrosnąć 3n razy. Efektem tej zależności jest brak algorytmu, umożliwiającego znajdywanie obu rodzajów ścieżek w każdym grafie w tzw. czasie wielomianowym, czyli praktycznie akceptowalnym. Inaczej mówiąc, dla wszystkich dostatecznie dużych grafów szukanie w nich ścieżek za pomocą znanych algorytmów traci sens, bo musiałoby trwać tysiąc lat. Oczywiście, w przypadku względnie małych grafów, a więc takich, jak w łamigłówkach, można uporać się z tym problemem w miarę szybko i „na piechotę”.
Na rys. 9 znajduje się graf odpowiadający układowi kamieni z rys. 1. Jak wiadomo (rys. 4), wyznaczenie w nim ścieżki hiroimono jest możliwe. Czy ścieżkę Hamiltona również uda się w nim narysować? Łatwo udowodnić, że nie. Wystarczy zauważyć, że czerwone i czarne wierzchołki na ścieżce będą występować na przemian, więc przy parzystej liczbie wierzchołków (14) kolory początkowego i końcowego powinny być różne, a są jednakowe (czarne). Właściwie dowód nie jest konieczny, bo z podanych wyżej dodatkowych warunków, różniących ścieżki Hamiltona i hiroimono, wynika, że ta druga jest znaczniej mniej „wymagająca”. W rezultacie każda pierwsza jest drugą, zaś w grafie zadaniowym, w którym rozwiązaniem jest ta druga, nigdy nie uda się poprowadzić pierwszej.
Zadania
W zadaniach 2 i 3 rozwiązanie można podać w postaci zapisu liczbowego – takiego, jak zapis w tekście artykułu, stanowiący rozwiązanie układu na rys. 4.
1. Proszę znaleźć wszystkie rozwiązania dla układu na rys. 8, czyli:
– wskazać wszystkie kamienie, od których można rozpocząć drogę „zbieracza”;
– podać przynajmniej jedno rozwiązanie dla każdego kamienia startowego (w postaci ciągów liter, odpowiadających kolejno zbieranym kamieniom).
2. W układzie na rys. 10 wystarczy wyznaczyć jedną ścieżkę hiroimono, czyli trasę zbierania 31 kamieni.
3. Wprowadzenie kamieni w dwóch kolorach jest, podobnie jak ujawnianie kamienia startowego, sposobem na jednoznaczność rozwiązania. Na rys. 11 należy poprowadzić ścieżkę hiroimono, na której zbierane kamienie będą tworzyły przeplatankę, czyli po każdym białym powinien być zielony, a po każdym zielonym biały (oczywiście poza ostatnim).
Rozwiązania prosimy nadsyłać do 30 czerwca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 06/18, lub listownie: Świat Nauki, ul. Gintrowskiego 28, 02-697 Warszawa. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Vitusa B. DrÖschera Reguła przetrwania ufundowaną przez wydawnictwo Prószyński Media.
***
Rozwiązania zadań z numeru kwietniowego
1. Najmniejszą liczbą mającą dokładnie 28 dzielników, podzielną przez 28 i kończącą się liczbą 28 jest 4928.
2. Największą liczbą N, która jest potęgą – taką, że nie ma liczby mniejszej od N, która ma więcej dzielników niż N – jest 36.
3. Najmniejszą liczbą, która ma liczbę dzielników równą liczbie oznaczającej pewien miniony rok XXI wieku jest 139 675 536 000; liczba dzielników – 2016.
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę To, czego się nie dowiemy. Badanie granic nauki Marcusa de Sautoy, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Marcin Florkowski z Bydgoszczy, Łukasz Jach z Czeladzi, Krzysztof Lemieszka z Otwocka, Waldemar Walczak z Krakowa, Rafał Zorychta z Kończyc Wielkich.
***
Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.