Для n дисков в Ханойской башне наименьшее число ходов, за которое можно перенести башню на другой стержень, равно 2ⁿ − 1. Это число получается, если перемножить n двоек и вычесть 1.

Число дисковМинимум ходов
11
23
37
415
531
663
7127
8255
9511

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

Смотрим на самый большой диск

Пусть башню из n дисков нужно перенести слева направо. Самый большой диск лежит под остальными, поэтому сразу его не сдвинуть. Чтобы перенести его вправо, в этот момент должно выполняться следующее.

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

Значит, остальные n − 1 дисков должны лежать башней на среднем стержне.

Делим ходы на три части

Отсюда перенос n дисков делится на три части.

  1. Перенести верхние n − 1 дисков с левого стержня на средний.
  2. Одним ходом переместить самый большой диск с левого стержня на правый.
  3. Перенести n − 1 дисков со среднего стержня на большой диск.

Части 1 и 3 — это та же самая задача «перенести башню из n − 1 дисков». Если обозначить наименьшее число ходов для n дисков через T(n), то

T(n) = T(n − 1) + 1 + T(n − 1) = 2 × T(n − 1) + 1.

Для одного диска нужен 1 ход, поэтому T(1) = 1. Отсюда по порядку получаются 3, 7, 15, 31…

Почему получается 2ⁿ − 1

Если прибавить 1 к обеим частям этого соотношения, получится

T(n) + 1 = 2 × (T(n − 1) + 1).

Значит, «число ходов плюс 1» с каждым новым диском увеличивается ровно вдвое. Для одного диска T(1) + 1 = 2, поэтому для n дисков получается 2 в n-й степени, то есть 2ⁿ. Вычтем 1 — и T(n) = 2ⁿ − 1.

Почему короче нельзя

Мы увидели, что по такому порядку можно перенести башню за 2ⁿ − 1 ходов. А нет ли способа перенести её за меньшее число ходов?

Как мы выяснили, в тот момент, когда самый большой диск двигают в первый раз, все остальные n − 1 дисков должны лежать на одном другом стержне. До этого момента нужно сделать не меньше ходов, чем требуется для переноса башни из n − 1 дисков. Так же и после того, как большой диск в последний раз положили вправо, чтобы собрать остальные n − 1 дисков на нём, нужно сделать не меньше ходов, чем для переноса башни из n − 1 дисков. Сам большой диск тоже нужно сдвинуть как минимум один раз.

При любом порядке ходов эти три части обязательно потребуются. Поэтому меньше, чем 2 × T(n − 1) + 1 ходов, не получится. Известно также, что кратчайшее решение на самом деле только одно.

В режиме «Классика» приложения — 127 ходов

В режиме «Классика» приложения «Ханойская башня» 7 дисков, поэтому наименьшее число ходов — 2⁷ − 1 = 127. Если у вас получилось 127 ходов, вы решили задачу кратчайшим путём. Если двигать маленький диск всё время в одну сторону по кругу, как рассказано в статье о правилах и игре, башня будет собрана ровно за 127 ходов.