2012.02.05
Wieża Hanoi, czyli: kiedy nadejdzie koniec świata?
Legenda głosi, że gdy mnisi tybetańscy (rozwiązujący w świątyni Brahmy układ wieży dla liczby 64 krążków, wykonanych ze złota) położą ostatni krążek na swoim miejscu, kończąc tym samym budowę – nastąpi koniec świata. Pocieszającym jest jednak to, że gdyby nawet układali wieżę z prędkością jeden ruch na sekundę, zajmie im to… prawie 600 miliardów lat.
Trochę historii
Wieża Hanoi, to klasyczna łamigłówka logiczna, opracowana pod koniec XIX wieku (dokładnie w roku 1883) przez Françoisa Édouarda Anatole Lucasa, profesora matematyki pracującego w Paryżu.
Model zbudowany przez Lucasa składał się z ośmiu krążków, był więc układanką dość skomplikowaną. Kiedy wieże Hanoi trafiły na rynek już jako popularne zabawki, najczęściej produkowanym modelem była wersja z pięcioma krążkami. Pierwsze zestawy, wprowadzane do sprzedaży przez Lucasa, zawierały w opisie przytoczoną na wstępie historię o tybetańskich mnichach i końcu świata. Jak widać autor był nie tylko świetnym matematykiem, ale znał się też na reklamie: ta historyjka okazała się świetnym posunięciem marketingowym.
Budujemy i eksperymentujemy
Wieże Hanoi można dziś bez problemu kupić jako gotowy model. Można też złożyć sobie taki układ, wykorzystując dostępne w sklepach z zabawkami klocki, piramidki - układanki dla Milusińskich, uzupełniając model o dodatkowe słupki i podstawę. To co możecie oglądać na fotografiach, to właśnie wykonana w ten sposób Wieża Hanoi… Jeśli komuś nie chce się kombinować z mocowaniem słupków na podstawie, do zabawy można wykorzystać płaskie talerzyki różnej średnicy i układać je na sobie, tworząc piramidki i przekładać poszczególne elementy zgodnie z zasadami gry.
Tradycyjnie najprościej będzie skorzystać z naszego modelu wirtualnego, i spróbować przełożyć piramidę z pierwszego słupka na trzeci, z zachowaniem zasad jakie rządzą wieżami Hanoi:
- w jednym ruchu wolno przełożyć tylko jeden krążek z wierzchu piramidki
- nie wolno położyć krążka większego na mniejszy
Operacje odbywają się przez wskazanie kursorem krążka przenoszonego, a następnie przeciągnięcie go na wybrany słupek. Zainstalowany po prawej stronie licznik, rejestruje ilość ruchów jakie potrzebne były do wykonania zadania. Użycie przycisku „reset”, przywraca zadanie do stanu wyjściowego, a umieszczone nad nim niebieskie prostokąty z cyframi – pozwalają na wybór ilości krążków w grze.
Uwaga! Zabawa bardzo wciąga! Ale jeśli znajdą się amatorzy tej pożytecznej łamigłówki, to kto wie? Może rozegramy kiedyś Pierwsze Mistrzostwa Twinn Science w układaniu Wież Hanoi na czas…
I co z tego?
Ta wydawałoby się prosta zabawka, jest przykładem zadania, którego złożoność obliczeniowa wzrasta niezwykle szybko w miarę zwiększania się parametru wejściowego, czyli liczby elementów wieży (w prezentowanym modelu wirtualnym może ich być maksymalnie osiem).
Mimo swojego wieku, oraz „łamigłówkowego” charakteru, Wieża Hanoi jest ciągle popularnym tematem w pracach matematyków, w ćwiczeniach równań określających ciągi geometryczne. Powstały specjalne algorytmy, pozwalające na szybkie rozwiązanie zadania (algorytm rekurencyjny i literacyjny). Wieże Hanoi stosuje się także często w psychologii, jako test na kojarzenie, oraz w ćwiczeniach służących określaniu ilorazu inteligencji, w grupie zadań logicznych rozwiązywanych na czas.
Jeśli zaś chodzi o wspomniany na początku koniec świata i mnichów układających wieżę z 64 krążków, to... zdaje się że mamy jeszcze czas... dużo czasu. Jeśli ktoś nie wierzy – proszę sobie policzyć dokładnie. Powodzenia.
TWiNN SCiENCE