Ханойская башня — частый материал для рекуррентных соотношений и метода математической индукции в учебниках и вступительных задачах (в Японии это старшие классы школы, курс «Математика B»). В этой статье мы потренируем рассуждения на примерах. Диски нумеруются от самого маленького: 1, 2, 3…, а наименьшее число ходов для переноса башни из n дисков обозначается aₙ.

Пример 1. Составляем рекуррентное соотношение

Задача: есть три стержня A, B и C. На A лежат n дисков разного размера, от большого к маленькому. Диски двигают по одному за раз и не кладут большой диск на маленький, чтобы перенести все диски на C. Если наименьшее число ходов равно aₙ, выразите aₙ₊₁ через aₙ.

Решение: обратим внимание на самый большой диск (номер n + 1). Чтобы перенести его на C, в этот момент верхние n дисков должны лежать на B башней.

  1. Перенести верхние n дисков с A на B — минимум aₙ ходов.
  2. Переместить диск n + 1 с A на C — 1 ход.
  3. Перенести n дисков с B на C — минимум aₙ ходов.

Таким порядком n + 1 дисков переносятся, поэтому aₙ₊₁ ≤ 2aₙ + 1. И наоборот, при любом порядке ходов части 1–3 обязательно потребуются, поэтому aₙ₊₁ ≥ 2aₙ + 1. Значит,

aₙ₊₁ = 2aₙ + 1 (a₁ = 1).

На экзаменах иногда требуют показать и «≤», и «≥», чтобы утверждать равенство. Подробное объяснение есть в статье о формуле минимального числа ходов.

Пример 2. Находим общую формулу

Задача: найдите общий член последовательности, заданной условиями a₁ = 1 и aₙ₊₁ = 2aₙ + 1.

Решение: рекуррентное соотношение вида aₙ₊₁ = paₙ + q преобразуют с помощью α, удовлетворяющего уравнению α = 2α + 1. Получаем α = −1, поэтому, прибавив к обеим частям 1, имеем

aₙ₊₁ + 1 = 2(aₙ + 1).

Последовательность aₙ + 1 — геометрическая прогрессия с первым членом a₁ + 1 = 2 и знаменателем 2. Значит, aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ, и

aₙ = 2ⁿ − 1.

Для проверки убедитесь, что a₁ = 1, a₂ = 3 и a₃ = 7 согласуются с рекуррентным соотношением.

Пример 3. Доказываем методом математической индукции

Задача: докажите методом математической индукции, что наименьшее число ходов для переноса n дисков равно 2ⁿ − 1.

Решение:

  1. При n = 1 один диск переносится за 1 ход, и меньше нельзя, поэтому наименьшее число ходов равно 1 = 2¹ − 1, и утверждение верно.
  2. Предположим, что при n = k наименьшее число ходов равно 2ᵏ − 1. При n = k + 1 по рассуждению из примера 1 наименьшее число ходов равно 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, то есть утверждение верно и при n = k + 1.
  3. Из пунктов 1 и 2 следует, что утверждение верно для всех натуральных n.

Главное — что «≤ и ≥ одновременно» из примера 1 используется на втором шаге индукции.

Пример 4. Когда можно двигать только на соседний стержень

Задача: стержни A, B и C стоят в ряд, и диски можно двигать только между A и B и между B и C (напрямую с A на C двигать нельзя). Найдите наименьшее число ходов bₙ для переноса n дисков с A на C.

Решение: самый большой диск n нужно двинуть дважды: A → B → C.

  1. Перенести верхние n − 1 дисков с A на C — bₙ₋₁ ходов (чтобы двинуть диск n на B, нужно освободить B).
  2. Диск n с A на B — 1 ход.
  3. Перенести n − 1 дисков с C на A — bₙ₋₁ ходов (чтобы двинуть диск n на C, нужно освободить C).
  4. Диск n с B на C — 1 ход.
  5. Перенести n − 1 дисков с A на C — bₙ₋₁ ходов.

Значит, bₙ = 3bₙ₋₁ + 2 (b₁ = 2). Из α = 3α + 2 получаем α = −1, поэтому bₙ + 1 = 3(bₙ₋₁ + 1). Последовательность bₙ + 1 — геометрическая прогрессия с первым членом 3 и знаменателем 3, поэтому

bₙ = 3ⁿ − 1.

Для 1–6 дисков мы проверили и расчётом, перебирающим все расположения, что это число ходов наименьшее. Любопытно, что за 3ⁿ − 1 ходов проходятся по одному разу все 3ⁿ расположений (число расположений — в статье о закономерностях).

Пример 5. Задачи для тренировки

Напоследок решите сами. Ответы ниже.

  1. Найдите наименьшее число ходов для 10 дисков.
  2. При каком числе дисков наименьшее число ходов превышает 1000?
  3. Сколько раз двигается самый маленький диск, когда n дисков переносят кратчайшим путём?

Ответы: 1. 2¹⁰ − 1 = 1023 хода. 2. Из 2ⁿ − 1 > 1000 получаем 2ⁿ > 1001; 2⁹ = 512, 2¹⁰ = 1024, поэтому при 10 дисках и больше. 3. 2ⁿ⁻¹ раз (причина — в разделе «Сколько раз двигается каждый диск» в статье о закономерностях).