Ханойские башни: маленькая задача внутри большой

Сначала план для четырёх дисков

Посмотрим на самый большой диск. Чтобы перенести его с левого стержня сразу на правый, нужно освободить и сам диск, и правый стержень. Значит, три меньших диска сначала собираем на среднем.

Затем переносим большой диск направо, а меньшую башню — со среднего поверх него. Получились три части: маленькая башня → один большой диск → маленькая башня.

Для одного диска нужен $1$ ход. Для двух по этому плану: $1+1+1=3$. Для трёх: $3+1+3=7$. Поэтому четыре диска можно перенести за $7+1+7=15$ ходов.

Почему быстрее нельзя

Обозначим $T(n)$ — наименьшее число ходов для переноса башни из $n$ дисков. Одинаковые стержни можно менять ролями: от выбора начала и цели минимум не зависит. Для одного диска $T(1)=1$.

Возьмём любой успешный маршрут, даже если в нём самый большой диск двигается несколько раз. Перед его первым ходом стержень-источник и стержень назначения должны быть свободны от меньших дисков. Значит, вся меньшая башня уже перенесена с начала на оставшийся стержень — это не менее $T(n-1)$ ходов.

Сразу после последнего хода большого диска на цель все меньшие снова стоят башней на другом стержне. Теперь их нужно перенести на цель поверх большого — ещё не менее $T(n-1)$ ходов. Между этими двумя частями есть хотя бы один ход большим диском.

Итак, любой маршрут требует не менее $2T(n-1)+1$ ходов. План из трёх частей ровно столько и тратит. Поэтому $T(n)=2T(n-1)+1$. В частности, для четырёх дисков минимум — $15$.

Откуда берётся степень двойки

Посчитаем несколько минимумов по правилу «удвоить предыдущий и прибавить один».

Последний столбец каждый раз удваивается. Это не случайное совпадение: из полученного правила следует $T(n)+1=2(T(n-1)+1)$.

Для одного диска величина $T(1)+1$ равна $2$. До башни из $n$ дисков остаётся $n-1$ удвоений, значит $T(n)+1=2^n$. Убираем добавленную единицу: $T(n)=2^n-1$.

Башня, которую не закончить за жизнь

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

По нашей формуле требуется $2^{64}-1$ ходов — примерно $1{,}8447\cdot10^{19}$. Даже если делать один ход в секунду без остановок, получим около $585$ миллиардов лет. Для оценки делим число ходов на $60\cdot60\cdot24\cdot365{,}25$ секунд в году. Добавить один диск легко; перенос башни после этого требует примерно вдвое больше ходов.