Wieża Hanoi: rozwiązanie, wzór 2^n - 1 i matematyka łamigłówki
W skrócie: wieża Hanoi z n krążkami i trzema słupkami wymaga co najmniej 2n − 1 ruchów: 7 dla 3 krążków, 15 dla 4, 31 dla 5, 127 dla 7. Żeby ją rozwiązać, przenieś górne n − 1 krążków na wolny słupek, największy krążek na słupek docelowy, a potem n − 1 krążków na niego, czyli tę samą łamigłówkę, tylko mniejszą. Szybka reguła: najmniejszy krążek przesuwaj co drugi ruch, zawsze w tym samym kierunku, a pomiędzy wykonuj jedyny inny dozwolony ruch. Łamigłówkę wymyślił Édouard Lucas w 1883 roku.
Wieża Hanoi wygląda jak zabawka: trzy słupki i stos krążków zwężający się ku górze. Trzeba przenieść cały stos na inny słupek, po jednym krążku, nigdy nie kładąc większego na mniejszym. Z 3 krążkami zajmuje to minutę. Z 7 wymaga skupienia. Z 64 trwałoby dłużej, niż będzie świecić Słońce. Za tą prostą łamigłówką kryje się jeden z najczystszych przykładów rekurencji w matematyce, ukryty licznik binarny i fraktal. Najpierw rozwiązanie, potem matematyka.
Zasady
- Są trzy słupki. Na początku wszystkie krążki leżą na jednym, największy na dole.
- Przenosisz jeden krążek naraz: górny krążek z dowolnego słupka na inny słupek.
- Nie wolno położyć krążka na mniejszym.
- Łamigłówka jest rozwiązana, gdy cała wieża stoi w tym samym porządku na słupku docelowym.
W naszej grze Wieża Hanoi wieża zaczyna na lewym słupku i ma skończyć na prawym. Poziom łatwy ma 3 krążki, średni 5, a trudny 7. Nie ma limitu czasu, a gra pokazuje obok twojej liczby ruchów najmniejszą możliwą.
Rozwiązanie dla 3 krążków, ruch po ruchu
Nazwijmy słupki A (start, lewy), B (środkowy) i C (cel, prawy), a krążki 1 (mały), 2 (średni) i 3 (duży). Najkrótsze rozwiązanie ma 7 ruchów:
| Ruch | Krążek | Skąd → dokąd | Po ruchu (A | B | C) |
|---|---|---|---|
| 1 | 1 | A → C | 3 2 | – | 1 |
| 2 | 2 | A → B | 3 | 2 | 1 |
| 3 | 1 | C → B | 3 | 2 1 | – |
| 4 | 3 | A → C | – | 2 1 | 3 |
| 5 | 1 | B → A | 1 | 2 | 3 |
| 6 | 2 | B → C | 1 | – | 3 2 |
| 7 | 1 | A → C | – | – | 3 2 1 |
Spójrz na strukturę. Ruchy 1-3 przenoszą wieżę z dwóch krążków z A na B. Ruch 4 przenosi duży krążek. Ruchy 5-7 przenoszą dwukrążkową wieżę z B na niego. W tym tkwi cały sekret.
Dwa sposoby na dowolną wieżę
1. Metoda rekurencyjna (myśl wieżami)
Żeby przenieść wieżę z n krążków ze słupka startowego na docelowy:
- Przenieś górne n − 1 krążków ze startu na wolny słupek (słupek docelowy służy za pomocniczy).
- Przenieś największy krążek ze startu na cel.
- Przenieś n − 1 krążków z wolnego słupka na cel (start służy za pomocniczy).
Kroki 1 i 3 to ta sama łamigłówka z jednym krążkiem mniej, więc stosujesz do nich te same trzy kroki, i tak dalej, aż zostanie jeden krążek, który po prostu przenosisz. Dlatego wieża Hanoi jest pierwszym przykładem rekurencji na kursach programowania: funkcji, która rozwiązuje problem, wywołując samą siebie dla mniejszej wersji. To też najlepszy sposób, by zrozumieć dowolną pozycję: zapytaj, który największy krążek nie jest jeszcze na miejscu; wszystko nad nim musi trafić na trzeci słupek.
2. Metoda iteracyjna (bez planowania)
- W każdym nieparzystym ruchu (1., 3., 5....) przesuń najmniejszy krążek o jeden słupek, zawsze w tym samym kierunku. Przy nieparzystej liczbie krążków kierunek to A → C → B → A (start, cel, środek), przy parzystej A → B → C → A.
- W każdym parzystym ruchu wykonaj jedyny dozwolony ruch, który nie dotyczy najmniejszego krążka. Zawsze jest dokładnie jeden.
Trzymając się tych dwóch reguł, skończysz w minimalnej liczbie ruchów bez myślenia naprzód. Tak większość ludzi rozwiązuje 7 krążków. Metoda rekurencyjna uczy, dlaczego to działa.
Dlaczego minimum to 2n − 1
Niech T(n) oznacza najmniejszą liczbę ruchów dla n krążków. Największy krążek musi się ruszyć co najmniej raz. W chwili ruchu musi być sam na swoim słupku, a słupek docelowy musi być pusty, więc pozostałe n − 1 krążków musi leżeć na trzecim słupku: to zajęło co najmniej T(n − 1) ruchów. Potem te krążki muszą jeszcze trafić na niego: znowu co najmniej T(n − 1) ruchów. Zatem
T(n) = 2 × T(n − 1) + 1, przy T(1) = 1.
Daje to 1, 3, 7, 15, 31, 63, 127... i każda liczba jest o jeden mniejsza od potęgi dwójki: T(n) = 2n − 1. Metoda rekurencyjna osiąga dokładnie tę liczbę, więc jest optymalna, a najkrótsze rozwiązanie jest jedyne: istnieje tylko jeden sposób, by zrobić to w 2n − 1 ruchach.
Jak szybko to rośnie
| Krążki | Najmniej ruchów | Przy jednym ruchu na sekundę |
|---|---|---|
| 3 | 7 | 7 sekund |
| 4 | 15 | 15 sekund |
| 5 | 31 | około pół minuty |
| 6 | 63 | około minuty |
| 7 | 127 | około 2 minut |
| 8 | 255 | około 4 minut |
| 10 | 1023 | około 17 minut |
| 20 | 1 048 575 | około 12 dni |
| 32 | 4 294 967 295 | około 136 lat |
| 64 | 18 446 744 073 709 551 615 | około 585 miliardów lat |
Każdy dodatkowy krążek podwaja pracę. Tak wygląda wzrost wykładniczy i dlatego łamigłówka służy do jego wyjaśniania.
Ukryte wzory
Który krążek się rusza: licznik binarny
W najkrótszym rozwiązaniu krążek k (licząc od najmniejszego) rusza się dokładnie 2n−k razy. Najmniejszy wykonuje połowę wszystkich ruchów (w zaokrągleniu w górę), największy rusza się raz, dokładnie w połowie: po 3 ruchach przy 3 krążkach, po 15 przy 5, po 63 przy 7.
Jest jeszcze zgrabniejsza reguła. Zapisz numer ruchu w systemie dwójkowym i policz zera na końcu: ruch 1 to 1 (brak zer, krążek 1), ruch 2 to 10 (jedno zero, krążek 2), ruch 3 to 11 (krążek 1), ruch 4 to 100 (dwa zera, krążek 3). Rusza się zawsze krążek o numerze o jeden większym niż liczba końcowych zer. Rozwiązanie to więc dosłownie licznik binarny od 0 do 2n − 1, a z samego numeru ruchu wiadomo, który krążek przesunąć. Ten sam ciąg (1, 2, 1, 3, 1, 2, 1...) to kolejność zmian bitów w kodzie Graya, sposobie liczenia binarnie, w którym w każdym kroku zmienia się tylko jeden bit.
Fraktal: trójkąt Sierpińskiego
Każdy krążek może leżeć na dowolnym z trzech słupków, a kolejność na słupku jest wymuszona (największy na dole), więc dozwolonych pozycji jest dokładnie 3n: 27 dla 3 krążków, 2187 dla 7. Narysuj każdą pozycję jako punkt i połącz dwa punkty, gdy jeden dozwolony ruch prowadzi od jednej pozycji do drugiej. Powstanie trójkąt złożony z trzech mniejszych trójkątów, z których każdy składa się z trzech jeszcze mniejszych: odmiana trójkąta Sierpińskiego, nazwanego od polskiego matematyka Wacława Sierpińskiego. Trzy wierzchołki to pozycje z całą wieżą na jednym słupku, a najkrótsze rozwiązanie biegnie prosto wzdłuż jednego boku.
Nasze trzy poziomy to liczby pierwsze
Liczby postaci 2n − 1 nazywa się liczbami Mersenne'a. Niektóre z nich są pierwsze, i takie są minimalne liczby ruchów na wszystkich naszych poziomach: 7, 31 i 127. Ta ostatnia łączy się z twórcą łamigłówki: w 1876 roku Édouard Lucas udowodnił, że 2127 − 1, liczba 39-cyfrowa, jest pierwsza. Pozostała największą znaną liczbą pierwszą przez 75 lat, do 1951 roku, a test Lucasa-Lehmera, oparty na jego metodzie, do dziś służy do szukania rekordowych liczb pierwszych.
Cztery słupki: znacznie trudniejszy problem
Z czwartym słupkiem wieżę da się przenieść dużo szybciej, bo jest więcej miejsc do odkładania krążków. Wersję z czterema słupkami opublikował Henry Dudeney w The Canterbury Puzzles (1907) jako „The Reve's Puzzle”. W 1941 roku J. S. Frame i B. M. Stewart niezależnie podali metodę: przenieś część górnych krążków na jeden wolny słupek, korzystając z czterech słupków, resztę przenieś trzema pozostałymi, a potem pierwszą grupę z powrotem na wierzch. Najlepszy podział daje takie liczby ruchów:
| Krążki | 3 słupki | 4 słupki (Frame-Stewart) |
|---|---|---|
| 3 | 7 | 5 |
| 4 | 15 | 9 |
| 5 | 31 | 13 |
| 6 | 63 | 17 |
| 7 | 127 | 25 |
| 8 | 255 | 33 |
| 10 | 1023 | 49 |
Przez ponad 70 lat nikt nie umiał udowodnić, że to najlepsza możliwa metoda dla czterech słupków. Udowodnił to dopiero Thierry Bousch w 2014 roku. Dla pięciu i więcej słupków pytanie wciąż pozostaje otwarte, co jest zdumiewające jak na łamigłówkę sprzedawaną w 1883 roku jako zabawka.
Historia: Lucas, pseudonim i legenda
Łamigłówka ukazała się w Paryżu w 1883 roku jako dzieło „profesora N. Clausa de Siam” z „kolegium Li-Sou-Stian”. Oba to anagramy: N. Claus de Siam to Lucas d'Amiens, a Li-Sou-Stian to Saint Louis, czyli Liceum Saint-Louis, w którym Édouard Lucas uczył matematyki. Lucas (1842-1891) jest znany także z liczb Lucasa, kuzynek ciągu Fibonacciego, i z czterotomowego zbioru matematycznych rozrywek.
Do łamigłówki dołączona była legenda: w wielkiej świątyni kapłani przenoszą wieżę z 64 złotych krążków między trzema diamentowymi iglicami według tych samych dwóch zasad, a gdy skończą, nastąpi koniec świata. Jak pokazuje tabela wyżej, nawet przy jednym ruchu na sekundę i bez błędów potrzebowaliby około 585 miliardów lat, ponad 40 razy więcej niż wiek Wszechświata. Legenda, podobnie jak nazwa Hanoi, była częścią egzotycznego opakowania Lucasa, a nie starożytną tradycją.
Gdzie dziś używa się wieży Hanoi
- Nauka programowania. To klasyczne ćwiczenie z rekurencji; opisana wyżej metoda w trzech krokach to funkcja na kilka linijek.
- Nauka matematyki. Równania rekurencyjne, indukcja matematyczna, wzrost wykładniczy i system dwójkowy w jednej łamigłówce.
- Psychologia. Zadania z wieżami służą do badania planowania i rozwiązywania problemów: na ile ruchów naprzód ktoś myśli. Odmiana zwana wieżą Londynu, zaproponowana przez Tima Shallice'a w 1982 roku, jest używana w badaniach neuropsychologicznych.
- Kopie zapasowe. Schemat rotacji taśm „wieża Hanoi” korzysta z tego samego wzoru 1, 2, 1, 3, 1, 2, 1, żeby zdecydować, którą taśmę nadpisać, dzięki czemu kopie gęsto pokrywają ostatnie dni i coraz rzadziej starsze okresy.
Wskazówki do naszej gry
- Zacznij od poziomu łatwego i rozwiązuj 3 krążki metodą iteracyjną, aż wejdzie w nawyk, potem przejdź na metodę rekurencyjną przy 5 krążkach.
- Przy nieparzystej liczbie krążków (wszystkie nasze poziomy: 3, 5, 7) pierwszy ruch to najmniejszy krążek na prawy słupek.
- Sprawdź półmetek: gdy rusza się największy krążek, wszystkie pozostałe muszą leżeć na środkowym słupku.
- Nigdy nie przesuwaj najmniejszego krążka dwa razy z rzędu; to zawsze zmarnowany ruch.
- Wynik to 1000 × najmniejsza liczba ruchów ÷ twoja liczba ruchów, razy 1, 2 albo 4 zależnie od poziomu, więc idealne 7 krążków daje 4000 punktów. Cofnięcie ruchu liczy się jako ruch.
Jeśli lubisz łamigłówki, w których opłaca się planować kilka ruchów naprzód, spróbuj też Przesuwania skrzyń (odmiana Sokobana) i Przesuwanki.
Najczęściej zadawane pytania
Ile ruchów potrzeba do rozwiązania wieży Hanoi?
Przy n krążkach i trzech słupkach minimum to 2 do potęgi n minus 1: 7 ruchów dla 3 krążków, 15 dla 4, 31 dla 5, 63 dla 6 i 127 dla 7. Każdy kolejny krążek podwaja liczbę ruchów i dodaje jeden.
Jak rozwiązać wieżę Hanoi z 3 krążkami?
Ze słupkami A (start), B (środek) i C (cel): mały krążek z A na C, średni z A na B, mały z C na B, duży z A na C, mały z B na A, średni z B na C i mały z A na C. To 7 ruchów, czyli minimum.
Jaki jest trik na wieżę Hanoi?
W każdym nieparzystym ruchu przesuń najmniejszy krążek o jeden słupek, zawsze w tym samym kierunku (najpierw w stronę słupka docelowego przy nieparzystej liczbie krążków, w stronę środkowego przy parzystej). W każdym parzystym ruchu wykonaj jedyny dozwolony ruch, który nie dotyczy najmniejszego krążka.
Ile trwałoby przeniesienie 64 krążków?
2 do potęgi 64 minus 1, czyli 18 446 744 073 709 551 615 ruchów. Przy jednym ruchu na sekundę i bez żadnego błędu to około 585 miliardów lat, mniej więcej 40 razy więcej niż obecny wiek Wszechświata.
Kto wymyślił wieżę Hanoi?
Francuski matematyk Édouard Lucas, który w 1883 roku wydał ją pod pseudonimem N. Claus de Siam, będącym anagramem Lucas d'Amiens. Dołączył do niej legendę o kapłanach przenoszących 64 złote krążki, po czym miał nastąpić koniec świata.
