К Ханойской башне прилагается такая легенда. В одном индийском храме стоит башня из 64 золотых дисков, и монахи, не нарушая правил, переносят диски с места на место. Когда они закончат, наступит конец света.

Сколько же времени на самом деле нужно, чтобы перенести 64 диска?

Минимум 2⁶⁴ − 1 ходов

Для n дисков минимальное число ходов равно 2ⁿ − 1. (Почему, объясняется в статье о минимальном числе ходов.) Для 64 дисков получаем

2⁶⁴ − 1 = 18 446 744 073 709 551 615 ходов.

По-японски это примерно «1845 кэй» (кэй — это 10¹⁶, десять тысяч триллионов), то есть около 18,4 квинтиллиона. Это в 18,45 миллиона раз больше одного триллиона.

Если делать один ход в секунду

Представим, что монах двигает диски без отдыха, по одному ходу в секунду, и ни разу не ошибается. Примем год за 31 557 600 секунд (365,25 суток) и разделим:

18 446 744 073 709 551 615 с ÷ 31 557 600 с ≈ 585 млрд лет.

Что с чем сравниваемСколько лет
Перенос 64 дисков, один ход в секундуоколо 585 млрд лет
С момента рождения Вселеннойоколо 13,8 млрд лет
С момента рождения Землиоколо 4,6 млрд лет

Это примерно в 42 раза больше возраста Вселенной. Даже если легенда правдива, бояться конца света не стоит.

А если считать компьютером

Допустим, ходы просчитывает не человек, а компьютер, который делает миллиард ходов в секунду. Всё равно понадобится

18 446 744 073 709 551 615 ÷ 1 000 000 000 ≈ 18,4 млрд секунд ≈ около 585 лет.

Правило для каждого хода очень простое, но с ростом числа дисков число ходов удваивается снова и снова. Это наглядный пример того, что значит «расти экспоненциально».

Сколько дисков можно пройти руками?

При одном ходе в секунду даже минимальное число ходов занимает вот сколько времени.

Число дисковМинимум ходовПри одном ходе в секунду
7127около 2 минут
101023около 17 минут
1532 767около 9 часов
201 048 575около 12 суток

Чтобы сыграть в перерыве, лучше всего подходит примерно 7 дисков. Именно поэтому в режиме «Классика» приложения «Ханойская башня» их 7.