Przenieś wieżę

Francuski matematyk Édouard Lucas urodził się w Amiens w 1842 roku; zmarł w Paryżu 49 lat później. Jest autorem czterotomowego dzieła Recréations Mathématiques zaliczanego do klasyki rozrywek matematycznych. W 1883 roku pod pseudonimem „N. Claus de Siam” (anagram „Lucas d’Amiens”) wydał grę pasjansową, czyli właściwie łamigłówkę, którą nazwał Wieżą Hanoi.

Lucas opisał grę jako uproszczoną wersję legendarnej Wieży Brahmy zbudowanej z 64 złotych dysków, które mnisi jakoby przemieszczali w wielkiej świątyni. Zanim jednak wykonali powierzone im zadanie, świątynia rozsypała się w pył i nastąpił koniec świata.

Wieża Hanoi składa się z małej planszy z trzema słupkami. Na lewym słupku znajduje się pięć krążków różnej średnicy, mających otwór pośrodku – umieszczonych w kolejności od największego na dole do najmniejszego na górze. Celem jest przeniesienie wszystkich krążków z lewego słupka na prawy w jak najmniejszej liczbie ruchów – z zachowaniem ich początkowej kolejności na lewym słupku i korzystaniem z pośrednictwa środkowego słupka. Każdy ruch polega na zabraniu krążka z jednego słupka i nałożenia go na inny, jednak większego krążka nigdy nie wolno kłaść na mniejszym. Ile i jakich ruchów potrzeba, aby uporać się z zadaniem?

Rozwiązanie na stronie 76.