Układanka piętnastka i ukryta w niej matematyka

Piętnastka jest układanką o bardzo prostych regułach. Trzeba przesuwać klocki w taki sposób, aby otrzymać pożądaną pozycję. Mimo swej prostoty jest źródłem ciekawych problemów, które można rozwiązać przy pomocy matematyki.

Układanka ta została wynaleziona w XIX wieku. Jej autorstwo przypisywał sobie niejaki Sam Loyd – znany amerykański autor różnego rodzaju zagadek. Jednak najprawdopodobniej to nie on był jej twórcą. Mimo wszystko w znacznym stopniu przyczynił się do jej popularyzacji.

Zasady są bardzo proste. Jest 15 kwadratowych klocków oraz jedno puste miejsce (nazwijmy je klockiem pustym), które znajdują się w kwadratowej planszy o wymiarach 4×4 jak poniżej:

Nazwijmy tę pozycję wyjściową oraz oznaczmy ją przez \(P_0\). Klocki możemy jedynie przesuwać, tj. w puste miejsce możemy przesunąć sąsiadujący z nim klocek. Nazwijmy to ruchem podstawowym. Dlatego układanki tego typu nazywa się również przesuwankami. W pozycji z rysunku powyżej możemy jedynie wykonać dwa ruchy podstawowe, tj. w puste miejsce przesunąć klocek 15 albo 12. Można również za jednym zamachem przesunąć więcej klocków np. całą kolumnę, 4, 8, 12 w dół. Jest to jednak to samo co trzy ruchy podstawowe. Zatem wystarczy się w naszych rozważaniach ograniczyć jedynie do ruchów podstawowych. Nie możemy wyjmować klocków i w ten sposób zamieniać ich miejscami. Zabawa polega na tym aby wykonując jedynie dozwolone ruchy, ułożyć klocki w konkretny sposób.

Swego czasu popularnym stał się problem następujący. Jak z pozycji \(P_0\) otrzymać poniższą (oznaczmy ją \(Q\))

powstałą przez zamianę miejscami klocków o numerach 15 oraz 14.

Problem stał się na tyle popularny, że wspomniany Sam Loyd zaoferował za jego rozwiązanie aż 1000 dolarów. Było to ponad sto lat temu, więc owa kwota była warta wtedy więcej niż obecne 1000 dolarów. Nie byłoby tej nagrody, gdyby nie to, że problem wydawał się niezwykle trudny, bo nikomu nie udało się znaleźć rozwiązania.

I nic dziwnego! Jak się okazuje trudy każdego śmiałka były daremne. Niemożliwe jest, wykonując tylko podstawowe przesunięcia klocków, otrzymanie pozycji \(Q\) wychodząc od pozycji \(P_0\). Swoją drogą jeżeli z pewnej pozycji \(P_1\) da się, poprzez serię ruchów podstawowych, przejść do pozycji \(P_2\), to będziemy mówić, że \(P_2\) jest osiągalna z \(P_1\). To jak się mogli czuć ci, którym naprawdę zależało na znalezieniu rozwiązania dobrze przedstawia poniższy rysunek z książki Sama Loyda Cyclopedia of Puzzles na stronie 235.

Choć bardzo możliwe, że Sam Loyd zaoferował tak sowitą nagrodę bo był świadom tego, że nikt nigdy nie będzie w stanie tej nagrody wygrać. Cały zaś zabieg z nagrodą był sprytnym chwytem marketingowym.

W tym wpisie najpierw pokażemy, używając prostego acz sprytnego argumentu, że istotnie nie da się wspomnianego problemu rozwiązać. Naturalnym uogólnieniem, o które aż się prosi, jest opis wszystkich pozycji, do których można dojść wychodząc od dowolnego ułożenia \(P\). W drugiej części wpisu, wykorzystując jedynie podstawy algebry abstrakcyjnej, przedstawimy rozwiązanie ogólniejszego problemu. Wspomnimy również o dalszych uogólnieniach.

Każdy ruch podstawowy sprowadza się do zamiany pustego klocka z jego sąsiadem w poziomie lub w pionie. Gdyby plansza była pomalowana w szachownicę, to każdy ruch podstawowy zmieniałby kolor pola, na którym znajduje się pusty klocek. Wobec tego aby z pozycji \(P_0\) przejść, poprzez serię ruchów podstawowych, do innej pozycji z pustym klockiem w tym samym miejscu, należy wykonać parzystą liczbę ruchów. A pozycja \(Q\) ma pusty klocek w dokładnie tym samy miejscu co \(P_0\).

Ci którym nie obce jest pojęcie parzystości permutacji wiedzą, że tyle wystarczy aby dowieść, że takie przejście, poprzez ruchy podstawowe, od \(P_0\) do \(Q\) jest niemożliwe. My jednak udowodnimy to tak aby i ci, którzy tego pojęcia nie znają byli zadowoleni.

W tym celu wprowadzimy pojęcie nieporządku. Każda para klocków mających numer (tzn. klocek pusty pomijamy!) gdzie ten o numerze wyższym znajduje się wcześniej tworzy nieporządek. Np. jeżeli klocek o numerze 8 znajduje się na polu wcześniejszym niż klocek o numerze 5, to para ta tworzy nieporządek. Wymaga to wprowadzenia pewnej kolejności pól na planszy. Wybieramy tę, która sama się narzuca.

Na powyższym rysunku para klocków 10 oraz 9 tworzy jeden z nieporządków bo klocek 10 znajduje się na polu wcześniejszym niż klocek 9. Dokładniej, klocek 10 jest na polui nr 1, zaś klocek 9 znajduje się na polu nr 10. Z kolei pusty klocek znajduje się na polu nr 11, a na polu nr 16 mamy klocek z liczbą 11.

Teraz sprawdzimy w jaki sposób ruchy podstawowe wpływają na liczbę nieporządków. Mamy dwa rodzaje ruchów podstawowych: w poziomie oraz w pionie. Od razu zauważamy, że każdy ruch w poziomie nie zmienia liczby nieporządków.

Inaczej sytuacja się ma w przypadku ruchów w pionie. W tym przypadku jeden z klocków zmienia o 1 nr wiersza, w którym się znajduje. Łatwo zauważyć, że między miejscem klocka przed wykonaniem ruchu a jego miejscem po ruchu zawsze znajdują się trzy inne klocki, gdy mówimy o ruchu w pionie. I to bez względu na to, w której kolumnie ruch się odbywa. Na rysunku niżej zaznaczone je ciemniejszym kolorem.

Mamy na rysunku dwie przykładowe sytuacje po wykonanym ruchu. Po lewej ruszono klockiem 5 w górę, a po prawej klockiem 7 w dół. Jeżeli ruszamy klockiem X w górę, to spośród stosownych trzech klocków część (lub wszystkie) będą miały numery większe od X, a część (lub wszystkie) numery mniejsze. Ponieważ jest tych klocków 3, to rozkład numerów tych klocków na mniejsze-większe może być równy 3-0, 0-3, 2-1 lub 1-2.

Przyjrzyjmy się sytuacji z prawej strony. Przed wykonaniem ruchu klocki 8, 1, 9 znajdowały się za klockiem o numerze 7. Po wykonanym ruchu znajdują się przed nim. Ponieważ 8 oraz 9 są większe niż 7, to otrzymaliśmy dwa nowe nieporządki. Ponadto, klocek 1 znalazł się po ruchu przez klockiem 7. Zatem jeden nieporządek nam ubył. Teraz zauważmy, że klocek 7 był jedynym, który zmienił swoje miejsce. Stąd jeśli para klocków \((a,b)\), gdzie \(a,b\neq 7\), była nieporządkiem, to pozostaje nim nadal. Podobnie jeśli nie była, to nadal nie jest nieporządkiem. Oznacza to, że liczba nieporządków zmieniła się o +2-1=+1.

Analogicznie można pokazać, że bez względu na rozkład stosownych 3 klocków na mniejsze-większe, liczba nieporządków zmieni się o liczbę nieparzystą. Do tego, każdy podstawowy ruch w pionie sprawia, że numer wiersza, w którym znajduje się puste pole zmienia się o 1. Jeżeli przez \(N\) oznaczymy liczbę nieporządków, a przez \(w\) numer wiersza (licząc od górnego), w którym znajduje się puste pole, to przy każdym pionowym ruchu \(N+w\) zmienia się o liczbę parzystą. Tak samo jest w przypadku ruchu poziomego. Tu \(N+w\) się nie zmienia. Teraz wystarczy zauważyć jeszcze dwie rzeczy. W przypadku pozycji wyjściowej liczba nieporządków jest równa 0, zaś puste pole znajduje się w wierszu 4, tj. \(N+w=4\). Natomiast w przypadku pozycji z zamienionymi miejscami klockami 14 oraz 15 mamy jeden nieporządek oraz puste pole w 4 wierszu, tj. \(N+w=5\). Jest to liczba nieparzysta, zatem nie da się tej pozycji otrzymać z pozycji wyjściowej wykonując jedynie legalne ruchy!!

Wynik ten mimo iż pokazuje, że problem z zamienionymi miejscami 14 oraz 15 nie jest rozwiązywalny, to jest zbyt oszałamiający. Nie pozwala na rozwiązanie narzucającego się zagadnienia, które pozycje można otrzymać z pozycji wyjściowej wykonując jedynie ruchy podstawowe oraz czy mając daną pozycję \(P\) można opisać zbiór wszystkich pozycji, które można z niej otrzymać wykonując jedynie legalne ruchy? Teraz zajmiemy się tym zagadnieniem. Poniższe rozumowanie pochodzi z (zacytowanej na końcu) pracy Archera.

Wprowadźmy teraz nieco inny porządek pól na planszy, naśladujący wężyka i przedstawiony poniżej. Przykładowo klocek o numerze 13 znajduje się na polu 16. Zaś klocek pusty w polu o numerze 13. Ponadto, wprowadźmy pojęcie rozmieszczenia, którym będziemy nazywać dowolną bijekcję ze zbioru klocków (razem z pustym) do zbioru numerów pól na kwadratowej planszy.

Ważną obserwacją jest to, że przesuwając pusty klocek wzdłuż wężyka (tj. zgodnie z nowym porządkiem), nie zmieniamy kolejności niepustych klocków, tj. tych mających numer. Wobec tego, możemy określić relację równoważności, przyjmując rozmieszczenia za równoważne, gdy jedno z drugiego możemy otrzymać przesuwając jedynie pusty klocek wzdłuż wężyka. Klasę abstrakcji tej relacji nazywamy konfiguracją. W każdym rozmieszczeniu z danej, konkretnej konfiguracji, kolejność niepustych klocków jest taka sama. Zaś numery pól, które klocki zajmują w danej konfiguracji nazywamy slotami. Jeżeli klocek zajmuje np. pole 5 na planszy oraz puste miejsce jest za nim, to klocek ten ma slot nr 5. Jeśli natomiast klocek piąty znajduje się w polu np. 3, to klocek ma slot 4.

Na rysunku klocek 9 znajduje się w polu o numerze 15, ale ponieważ pusty klocek znajduje się przed polem 15, to klocek 9 jest w slocie 14.
Ogólnie, powyższe rozmieszczenie odpowiada konfiguracji \([1,2,3,4,8,7,6,5,14,12,13,10,15,11,9]\).

Każdy ruch podstawowy wpływa (lub nie) na ułożenie slotów w konfiguracji, tzn. prowadzi do pewnej ich permutacji. Oznaczmy przez \(\sigma_{i,j}\) permutację slotów, do której prowadzi przesunięcie pustego klocka z \(i\)-tego pola na planszy do pola \(j\). Ponieważ przesuwając pusty klocek wzdłuż wężyka nie zmieniamy kolejności slotów, to permutacja \(\sigma_{i,i+1}\) jest identycznością na slotach. Ponadto, \(\sigma_{i,j}=\sigma_{j,i}^{-1}\).

W tym miejscu uwidacznia się pewna zaleta przyjęcia wężykowego porządku pól na planszy. Dzięki temu do rozważenia są jedynie ruchy prowadzące do nietrywialnych permutacji \[\sigma_{1,8}, \sigma_{2,7}, \sigma_{3,6}, \sigma_{5,12}, \sigma_{6,11}, \sigma_{7,10}, \sigma_{9,16}, \sigma_{10,15}, \sigma_{11,14}.\] Dla przykładu zobaczmy jaką permutacją jest \(\sigma_{1,8}\), tzn. ta powodowana przez przesunięcie pustego klocka z pola 1 do pola 8.

Przed takim ruchem, pusty klocek znajduje się w polu 1, tj. pierwszy slot znajduje się w polu 2. Wykonawszy wspomniany ruch, sprawiamy, że wszystkie sloty od 1 do 6 zwiększają swój numer o 1 bo w polu nr 1 pojawił się niepusty klocek. A ponieważ klocek ten przed ruchem znajdował się w siódmym z kolei niepustym polu, to po ruchu znajduje się w slocie o numerze 1. Natomiast sloty o numerach większych niż 7 pozostają bez zmian. Ostatecznie \[\sigma_{1,8}=(1,2,3,4,5,6,7).\] W analogiczny sposób można zauważyć, że
\[\begin{array}{lll}\sigma_{2,7} & = & (2,3,4,5,6)\\ \sigma_{3,6} & = & (3,4,5)\\ \sigma_{5,12} & = & (5,6,7,8,9,10,11)\\ \sigma_{6,11} & = & (6,7,8,9,10)\\ \sigma_{7,10} & = & (7,8,9)\\ \sigma_{9,16} & = & (9,10,11,12,13,14,15)\\ \sigma_{10,15} & = & (10,11,12,13,14)\\ \sigma_{11,14} & = & (11,12,13) \end{array}\]

Teraz pokażemy, że zbiór \(A\) wyżej wymienionych permutacji oraz ich odwrotności generuje grupę alternującą \(A_{15}\). Stąd od razu wynika, że prawdziwe jest następujące twierdzenie:

Twierdzenie 1
Niech \(P_1\) oraz \(P_2\) będą rozmieszczeniami należącymi odpowiednio do konfiguracji \(K_1\) oraz \(K_2\). Wówczas \(P_2\) można otrzymać z \(P_1\) poprzez serię ruchów podstawowych wtedy i tylko wtedy, gdy \(K_2\) jest parzystą permutacją \(K_1\).

Możemy je również sformułować w języku rozmieszczeń. Jeżeli rozmieszczenia \(P_1\) oraz \(P_2\) mają pusty klocek w tym samym polu, to \(P_2\) jest osiągalne z \(P_1\) wtedy i tylko wtedy, gdy \(P_2\) jest parzystą permutacją \(P_1\). Każdy ruch podstawowy jest pewną transpozycją. Wobec tego jeżeli \(P_1\) oraz \(P_2\) mają pusty klocek w różnych polach, to możemy w ogólności sformułować następujące twierdzenie:

Niech rozmieszczenie \(P_1\) ma pusty klocek w polu o numerze \(a_1\) zaś \(P_2\) w polu \(a_2\) oraz niech \(n\) będzie liczbą ruchów podstawowych jaką należy wykonać aby przejść od pola \(a_1\) do pola \(a_2\). Wówczas rozmieszczenie \(P_2\) jest osiągalne z \(P_1\) wtedy i tylko wtedy, gdy \(P_2\) jest permutacją \(P_1\) tej samej parzystości co liczba \(n\).

Rozmieszczenia \(P_0\) oraz \(Q\) mają pusty klocek w tym samym polu, tj. \(n=0\) w tym przypadku. Więc \(Q\) się nie da, jak już wiemy, otrzymać z \(P_0\) bo \(Q\) jest nieparzystą permutacją \(P_0\). Ale przejdźmy do dowodu.

Zacznijmy od przytoczenia (bez dowodu) znanego, standardowego lematu

Lemat 1
Jeżeli \(n\geqslant 3\), to cykle długości 3 generują \(A_n\).

Okazuje się, że można zbiór wszystkich 3-cykli zredukować.

Lemat 2
Jeżeli \(n\geqslant 3\), to cykle \(X_n=\{(1,2,3), (2,3,4),\ldots, (n-2, n-1,n)\}\) generują \(A_n\).

Dowód:
Na mocy lematu 1, wystarczy pokazać, że \(X_n\) generuje wszystkie 3-cykle.
Ponieważ \(A_3=\{\textrm{id},(1,2,3),(1,3,2)\}\) jest generowana przez \((1,2,3)\), to dla \(n=3\) lemat jest prawdziwy. Załóżmy, że jest prawdziwy dla pewnego \(n\geqslant 3\). Zauważmy, że włożenie \[\{1,2,3,\ldots,n\}\to \{1,2,3,\ldots,n,n+1\}\] prowadzi do włożenia \[\alpha: A_n\to A_{n+1},\] gdzie \(\alpha(\sigma)(i)=\sigma(i)\) dla \(i\neq n+1\) oraz \(\alpha(\sigma)(n+1)=n+1\). Stąd wynika, że \(\alpha(X_n)\), a więc w szczególności \(X_{n+1}\) generuje 3-cykle niezawierające n+1.
Analogicznie, funkcja \[\{1,2,3,\ldots,n\}\to \{1,2,3,\ldots,n,n+1\},\ i\mapsto i+1\] prowadzi do włożenia \[\beta: A_n\to A_{n+1},\] gdzie \(\beta(\sigma)(i)=\sigma(i+1)\) dla \(i\neq 1\) oraz \(\beta(\sigma)(1)=1\). Stąd wynika, że \(X_{n+1}\) generuje wszystkie 3-cykle niezawierające jednocześnie 1 oraz n+1. Na koniec wystarczy zauważyć, że dla \(y\in \{1,2,\ldots, n+1\}\setminus \{1,x,n+1\}\) zachodzi \[(1,x,n+1)=(y,x,n+1)(1,x,y)\] oraz \[(1,n+1,x)=(1,x,n+1)(1,x,n+1).\]

Teraz możemy udowodnić następujące twierdzenie:

Twierdzenie
Zbiór \(A\) wymienionych wcześniej permutacji generuje \(A_{15}\).

Dowód:
Ponieważ wszystkie permutacje z \(A\) są parzyste, to \(A\) generuje pewną podgrupę \(A_{15}\). Pokażemy, że generuje on wszystkie permutacje z \(X_{15}\), tym samym dowodząc, na mocy lematu 2, że zbiór \(A\) generuje \(A_{15}\). Istotnie, zauważmy na początek, że dla dowolnej permutacji \(\sigma\) zachodzi \[\sigma (a_1,a_2,\ldots,a_n)\sigma^{-1}=(a_1\sigma, a_2\sigma,\ldots,a_n\sigma).\] Podstawiając kolejno \(n=-2,-1,0,1,2\), złożenia \[\sigma_{1,8}^{-n}\sigma_{3,6}\sigma_{1,8}^n\] prowadzą do cykli \((1,2,3),\ldots,(5,6,7)\). Podobnie, \[\sigma_{5,12}^{-n}\sigma_{7,10}\sigma_{5,12}^n\] prowadzą do \((5,6,7),\ldots, (9,10,11)\). Zaś złożenia \[\sigma_{9,16}^{-n}\sigma_{11,14}\sigma_{9,16}^n\] dają cykle \((9,10,11),\ldots,(13,14,15)\). Otrzymaliśmy więc wszystkie cykle z \(X_{15}\) co kończy dowód.

Z powyższego twierdzenia wynika w szczególności, że relacja równoważności \(\sim\), gdzie \(P_1\sim P_2\) o ile, rozmieszczenie \(P_1\) można otrzymać z \(P_2\) poprzez serię ruchów podstawowych (i vice versa) ma dwie klasy abstrakcji.

Naturalnym pytaniem jest to jak się sprawy mają w przypadku w przypadku plansz o innych wymiarach czy nawet innych kształtach. Czy Twierdzenie 1 pozostałoby prawdziwe gdyby plansza miała inne wymiary niż 4×4? Czy może w takiej sytuacji relacja \(\sim\) miałaby inną liczbę klas abstrakcji? Omówimy teraz, z grubsza, sytuację znacznie ogólniejszą.

Cała zabawa w piętnastkę polega w zasadzie na przemieszczaniu pustego klocka w pole z nim sąsiadujące. Prowadzi to do pomysłu aby rozważać takie przesuwanie nie po prostokątnej planszy lecz między wierzchołkami grafu. Każdy wierzchołek to pole. Klocki możemy przesuwać jedynie między polami sąsiednimi czyli połączonymi krawędzią. Pomysł ten był rozważany w, cytowanej na końcu, pracy Wilsona.

Przykładowo, jeżeli pola na planszy do piętnastki uznamy za wierzchołki grafu, które są połączone krawędzią, gdy ze sobą sąsiadują, to graf ten będzie wyglądał następująco:

Co oczywiste, ograniczymy się jedynie do grafów spójnych. Może się wydawać, że w przypadku grafów, twierdzenie analogiczne do Twierdzenia 1 jest trudne do sformułowania w tak zgrabny i przystępny sposób. Okazuje się jednak, że w takiej znacznie ogólniejszej sytuacji, opis klas abstrakcji relacji \(\sim\) jest nadzwyczaj prosty.

Ideę, którą zastosowaliśmy do klasycznej piętnastki, można z powodzeniem zastosować do plansz będących grafami mającymi drogę Hamiltona, tj. przechodzącą przez wszystkie wierzchołki tylko raz. Porządek wężykowy jaki przyjęliśmy na planszy do piętnastki jest przykładem takiej drogi. Przechodzi ona przez wszystkie pola (wierzchołki) tylko raz. Gdybyśmy zamiast wężykowego, przyjęli porządek spiralny, to w również dałoby się udowodnić Twierdzenie 1.

Spójrzmy na inny graf. Dobrym przykładem jest słynny graf Petersena. Jest to graf mający drogę Hamiltona.

Można pokazać, że permutacje \[\sigma_{1,9}, \sigma_{1,5}, \sigma_{2,7}, \sigma_{3,10},\sigma_{4,8}\textrm{ oraz } \sigma_{6,10}\] generują całe \(S_9\). W tym przypadku każde rozmieszczenie można otrzymać z każdego.

Zupełnie inaczej sytuacja wygląda z grafami cyklicznymi. W ich przypadku żaden ruch podstawowy nie zmienia konfiguracji niepustych klocków!

W dalszej części rozważać będziemy grafy proste – tj. bez krawędzi wielokrotnych oraz bez pętli. Do tego zakładamy, że graf jest dwuspójny czyli nie zawiera wierzchołków, które go rozspajają. W takiej sytuacji nie da się żadnego niepustego klocka przesunąć przez taki wierzchołek i problem rozpada się do analogicznego zagadnienia w każdej składowej spójności powstałej po usunięciu takiego wierzchołka.

Dla grafu \(G\) możemy, analogicznie jak w przypadku piętnastki, wprowadzić pojęcie rozmieszczenia. Polami będą wierzchołki grafu. Oznaczmy przez \(p(G)\) zbiór wszystkich rozmieszczeń. Zbiór \(p(G)\) możemy utożsamiać z wierzchołkami nowego grafu, które są połączone krawędzią tylko gdy rozmieszczenie \(P_2\) można otrzymać z \(P_1\) poprzez ruch podstawowy.

W takiej interpretacji, problem czy rozmieszczenie \(P_2\) jest osiągalne z \(P_1\) sprowadza się do tego tego czy \(P_1\) oraz \(P_2\) leżą w tej samej składowej spójności grafu \(p(G)\). Okazuje się, że prawdziwe jest następujące twierdzenie:

Twierdzenie (Wilson)
Jeżeli \(G\) jest prostym grafem dwuspójnym niebędącym ani grafem cyklicznym ani grafem dwudzielnym ani poniższym grafem \(\theta\) to graf \(p(G)\) jest spójny. Jeżeli \(G\) jest grafem dwudzielnym, to \(p(G)\) ma dwie składowe spójności, zaś \(p(\theta)\) ma sześć składowych spójności.

Graf \(G\) odpowiadający planszy do klasycznej piętnastki jest grafem dwudzielnym, więc \(p(G)\) ma dwie składowe spójności (co już wiemy).

Literatura

A.F. Archer, A Modern Treatment of the 15 Puzzle, Amer. Math. Monthly 106 (1999), s. 793-799
R.M. Wilson, Graph Puzzles, Homotopy and the Alternating Group, J. Combin. Theory Ser. B 16 (1974), s. 86-96