Piętnastka

Nie ma chyba bardziej ponadczasowej łamigłówki logicznej typu samotnik niż popularna "piętnastka" zwana też "przesuwanką" lub z francuskiego "taquin" [czytaj: tak'ę]. Znana była już pod koniec XIX wieku. Jej twórcą jest Noyes Palmer Chapman - pracownik pocztowy z Nowego Jorku (projekt pochodzi z 1874 roku, nigdy nie został opatentowany). Produkcja łamigłówki ruszyła w 1879 roku w Hartford (w stanie Connecticut) w miejscowej szkole dla głuchoniemych. Piętnastkę spopularyzował amerykański twórca zagadek logicznych Samuel Loyd.  Jej budowa i zasady układania są bardzo proste. W kwadratowej ramce umieszczonych jest 15 kwadratowych płytek i jedno miejsce puste, dzięki czemu płytki można w obrębie ramki przesuwać. W oryginalnej wersji płytki ponumerowane są liczbami od 1 do 15, ale są też warianty obrazkowe lub literowe (wtedy należy ułożyć określone hasło). Istnieją analogiczne łamigłówki w ramkach o wymiarach n×n dla n≠4 lub n×m dla różnych wartości n i m, a także wersje przestrzenne w ramce sześciennej. Ciekawym wynalazkiem są obrazkowe wersje piętnastki z możliwością jednoczesnego obracania narożnych płytek (np. w łamigłówce Twisting Rings).

Przed rozpoczęciem zabawy płytki przesuwamy losowo, a zadaniem rozwiązującego łamigłówkę jest przywrócenie ich pierwotnego układu. Oczywiście rozwiązanie w każdym przypadku istnieje, wystarczy bowiem wykonywać ruchy przeciwne do ruchów tasującego płytki. Problem polega na tym, że zazwyczaj nie wiemy, jakie ruchy on wykonał.

Na początek proponujemy rozegranie kilku partii.

A oto kilka przykładowych wariantów piętnastki w wersji obrazkowej. Zawierają one 16 płytek i dodatkowe 17 miejsce puste (zaznaczone białym kółkiem).

W latach 70. XIX wieku Samuel Loyd ogłosił konkurs z niebagatelną jak na owe czasy (a i dzisiejsze także) nagrodą 1000 dolarów dla tego, kto pierwszy znajdzie sekwencję ruchów zamieniającą miejscami płytki z numerami 14 i 15, przy czym pozostałe kwadraciki muszą być na swoich początkowych miejscach, a pole w prawym dolnym rogu ma być puste. Amerykę opanowało istne szaleństwo, a gazety publikowały satyryczne rysunki przedstawiające księży na ambonie, chirurgów w czasie operacji lub maszynistów prowadzących pociąg i próbujących jednocześnie rozwiązywać "piętnastkę". Oferta Loyda była tyleż szczodra, co bezpieczna dla jego finansów, gdyż opisanego układu płytek nie da się otrzymać. Matematyczny dowód tego faktu opublikowali w 1879 roku na łamach "American Journal of Mathematics" Woosley Johnson i William Story. Spróbujmy uzasadnić, dlaczego zagadka Loyda jest nierozwiązywalna.

Nazwijmy wolne miejsce w ramce numerem 16. Każdy układ płytek (czytany wierszami od lewej) jest pewnym ustawieniem liczb 1, 2, 3, ..., 15, 16 (w matematyce nazywamy takie ustawienie permutacją). Teoretycznie dla 16 płytek możliwych ustawień jest 16! = 20 922 789 888 000 (czyli prawie 21 bilionów), ale powstaje pytanie, czy wszystkie są osiągalne zgodnie z regułami przesuwanki.

Wersja ciągowa

Ustawmy liczby od 1 do 16 w ciąg. Przyjmijmy, że w tym ciągu możemy zamieniać miejscami dwie sąsiednie liczby. Jest oczywiste, że wykonując odpowiednie sekwencje takich ruchów, można przejść od ustawienia naturalnego do dowolnego innego ustawienia. Są wśród nich takie ustawienia, do których można dojść, wykonując parzystą liczbę ruchów, np. 3, 1, 2, 4, 5, ..., 15, 16, a do innych potrzeba nieparzystej liczby ruchów, np. 2, 1, 3, 4, 5, ..., 15, 16.

Fakt. Nie ma ustawień, do których od ustawienia naturalnego prowadziłyby dwie drogi, jedna z parzystą, a druga z nieparzystą liczbą ruchów.

Uzasadnienie. Załóżmy, że dla danego układu istnieją dwie drogi od ustawienia naturalnego o różnej parzystości liczby ruchów. Przechodzimy najpierw pierwszą drogę, a potem wracamy do ustawienia naturalnego, wykonując w odwrotnym porządku ruchy przeciwne do ruchów z drugiej drogi. Zatem łącznie wykonamy nieparzystą liczbę ruchów i wrócimy do ustawienia naturalnego. To jest niemożliwe. Z żadnego ustawienia nie da się powrócić do niego samego za pomocą nieparzystej liczby ruchów.
Oznaczmy przez (3, 7) sekwencję ruchów zamieniających miejscami liczby 3 i 7, tzn. przechodzącą od układu 1, 2, 3, 4, 5, 6, 7, ..., 15, 16 do 1, 2, 7, 4, 5, 6, 3, ..., 15, 16. Widzimy, że trójka była początkowo na lewo od siódemki, a po wykonaniu tej sekwencji ruchów znalazła się na prawo. Jeśli chcemy wrócić do początkowego ustawienia, trójka musi przeskoczyć przez siódemką z powrotem. Dotyczy to wszystkich par liczb. Zatem liczba ruchów, w jakich uczestniczy każda para liczb, musi być parzysta, a więc także ogólna liczba ruchów przy powrocie do zadanego ustawienia musi być parzysta.

Wniosek 1. Wszystkie możliwe ustawienia (permutacje układu liczb 1, 2, 3, ..., 15, 16) możemy podzielić na dwa rozłączne typy: parzyste - czyli takie, do których można dojść w parzystej liczbie ruchów, oraz nieparzyste -  czyli takie, do których można dojść w nieparzystej liczbie ruchów.

Wniosek 2. Ustawienie piętnastki z zagadki Sama Loyda jest permutacją nieparzystą (wymaga wykonania jednego ruchu - zamiany sąsiednich liczb 14 i 15).

Wersja ramkowa

W oryginalnej łamigłówce ruchy to pojedyncze przesunięcia płytek w pionie lub w poziomie. Każdy ruch w poziomie przestawia w ustawieniu ciągowym liczbę 16 z liczbą sąsiednią (co jest to zgodne z definicją ruchu w wersji ciągowej), natomiast ruch w pionie przestawia liczbę 16 z liczbą, która w ustawieniu ciągowym jest odległa o 4 (co wymaga 7 ruchów w wersji ciągowej - dlaczego?).  

Fakt. Od ustawienia naturalnego można dojść tylko do ustawień parzystych.

Uzasadnienie.Niech dane będzie pewne rozwiązywalne ustawienie piętnastki (tzn. otrzymane w wyniku wcześniejszego tasowania płytek zgodnie z regułami) z polem 16 znajdującym się w prawym dolnym rogu. Od tego ustawienia chcemy powrócić do ustawienia naturalnego. Aby doprowadzić płytkę 16z powrotem na swoje miejsce musimy ją przesunąć tyle samo razy w lewo, co w prawo oraz tyle samo razy w górę, co w dół. Otrzymamy w ten sposób parzystą liczbę ruchów poziomych (2x) i parzystą liczbę ruchów pionowych (2y). W modelu ciągowym odpowiada to liczbie ruchów równej 2x+7·2y, co jest liczbą parzystą. Ustawienie naturalne jest typu parzystego (potrzebnych jest 0 ruchów), a parzysta liczba ruchów może prowadzić tylko do innego ustawienia parzystego. Zatem ustawienia nieparzyste są w piętnastce nieosiągalne i są nierozwiązywalne.  

Wniosek 1. Zagadka Loyda nie ma rozwiązania, bo jest ustawieniem nieparzystym.

Fakt. Każde ustawienie parzyste jest rozwiązywalne.

Uzasadnienie. Można je przeprowadzić w kilku krokach, zaczynając od trywialnej wersji 1×1, a w kolejnym kroku dodając nowy wiersz i nową kolumnę. Rozumowanie jest dość żmudne i wymaga za każdym razem rozważenia kilku możliwych przypadków.  

Wniosek 2. W piętnastce istnieje tylko 16!/2 = 10 461 394 944 000 różnych osiągalnych i rozwiązywalnych ustawień.

Radykalnie prostsze warianty piętnastki, które pozwalają zrozumieć złożoność oryginału, wraz z zestawami ćwiczeń znajdziecie na Portalu w artykule Piętnastka - rozgrzewka.

Obliczono, że z każdego z rozwiązywalnych ustawień można wrócić do ustawienia naturalnego, wykonując co najwyżej 80 ruchów (jest to tzw. boska liczba - czyli najmniejsza liczba ruchów wystarczająca do rozwiązania łamigłówki z dowolnego ustawienia). Średnia liczba wykonywanych w rozgrywce ruchów wynosi 52,6. Dla 17 (spośród ponad 10 bilionów) ustawień wykonanie 80 ruchów jest konieczne. Oto jedna z takich sytuacji. Spróbuj ją rozwiązać. Powodzenia!

Wirtualny symulator łamigłówki przygotował Krzysztof Omiljanowski.  

Zadania konkursowe
1. Ile wynosi boska liczba dla przesuwanki w ramce 2×2?
2. Czy boska liczba dla przesuwanki w ramce 3×3 przekracza 20?
3. Ile ruchów potrzeba wykonać, aby odwrócić porządek liczb dla tych przesuwanek?