Легенда о «Ханойской башне». Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брамы. В нем установлены три алмазных стержня. На один из стержней нанизаны 64 золотых диска разных размеров, каждый диск меньшего диаметра лежит на большем. Монахи получили задание переместить эти диски с одного стержня на другой в такой же последовательности. И с тех пор они только тем и заняты, что меняют диски местами.
По подсчетам, если на перемещение одного кольца необходима 1 секунда, то монахам для выполнения задания потребуется 500 миллиардов лет.
Покажем решение этой задачи для двух колец.
1 Перенести маленькое кольцо
с 1-го стержня на 2-й.
2Перенести большое кольцо
с 1-го стержня на 3-й.