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

Сколько раз двигается каждый диск — степень двойки

В кратчайшем решении число ходов каждого диска определено. При n дисках диск с номером k двигается 2ⁿ⁻ᵏ раз.

Диск (при 4 дисках)Сколько раз двигается
18
24
32
41
Всего15

Самый большой диск двигается 1 раз, следующий — 2 раза, следующий — 4 раза, и так далее: с уменьшением диска число ходов удваивается. В сумме 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1, то есть ровно наименьшее число ходов.

Причину можно понять так же, как в статье о формуле минимального числа ходов. Чтобы перенести n дисков, башню из n − 1 дисков переносят дважды. Поэтому диски меньше n двигаются вдвое больше раз, чем при переносе n − 1 дисков.

Какой диск двигается на каком ходу

Если выписать по порядку номера дисков, которые двигаются в кратчайшем решении для 4 дисков, получится следующее.

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Диск 1 встречается через ход, между ними через один встречается 2, между ними — 3, и так далее. Эта последовательность устроена так же, как длина делений на линейке (короткое, среднее, короткое, длинное…).

Её легко получить, если записать номер хода в двоичной системе.

ХодДвоичная записьЧисло нулей в концеКакой диск двигается
1101
21012
31101
410023
510101
611012
711101
8100034

На ходу m двигается диск с номером «число нулей в конце двоичной записи m, плюс 1». У нечётных ходов двоичная запись оканчивается на 1, поэтому всегда двигается диск 1. Именно поэтому в статье о том, как решать головоломку на ходах с нечётным номером двигают диск 1.

Кроме того, стержни, с которого и на который двигают, тоже можно найти одними двоичными вычислениями (статья об алгоритме).

Связь с кодом Грея

Когда двоичные числа считают подряд от 0, при каждом увеличении на 1 меняется разное число разрядов (от 0111 к 1000 меняются 4 разряда). Способ записи чисел, при котором на каждом шаге меняется только один разряд, называется «кодом Грея».

НомерКод ГреяКакой разряд меняется (справа)
0000―
10011
20112
30101
41103
51111
61012
71001

Последовательность меняющихся разрядов «1 2 1 3 1 2 1» точно такая же, как последовательность дисков, которые двигаются в Ханойской башне. Если считать каждый диск одним двоичным разрядом, а «разряд меняется» — «диск двигается», то кратчайшее решение Ханойской башни — то же самое, что последовательный проход по коду Грея.

В какую сторону вращается каждый диск

В статье о том, как решать головоломку говорилось, что диск 1 всегда вращается в одну сторону. На самом деле то же правило верно и для других дисков.

  • Диски с нечётными номерами (1, 3, 5…) вращаются в ту же сторону, что и диск 1.
  • Диски с чётными номерами (2, 4, 6…) вращаются в сторону, противоположную диску 1.

Когда башню переносят слева направо, при нечётном числе дисков диск 1 идёт по кругу «левый → правый → средний», а при чётном — «левый → средний → правый». Ни один диск до конца ни разу не меняет направление.

Есть и ещё одно правило, о котором рассказано в статье про 10 дисков: в кратчайшем решении диск с нечётным номером никогда не кладут прямо на нечётный, а с чётным — на чётный.

Всего 3ⁿ расположений

Сколько всего есть расположений дисков, не нарушающих правил? Каждый диск лежит на одном из трёх стержней, а порядок дисков на одном стержне определён (от большого к маленькому), поэтому расположений 3ⁿ.

Число дисковРасположений
327
5243
72187
919 683

Более того, из любого расположения в любое можно перейти, не нарушая правил. Известно и то, что если обозначить каждое расположение точкой и соединить линиями точки, между которыми можно перейти за один ход, получится фигура, очень похожая на «треугольник Серпинского», где в большой треугольник вложены маленькие.

В режиме «Задачи» приложения «Ханойская башня» задачи, где нужно привести расположение к форме образца, составляются из всех этих расположений. Даже для 9 дисков на ★5 перед выдачей задачи кратчайшее число ходов проверено для всех 19 683 расположений.