Ханойская башня — частый материал для рекуррентных соотношений и метода математической индукции в учебниках и вступительных задачах (в Японии это старшие классы школы, курс «Математика B»). В этой статье мы потренируем рассуждения на примерах. Диски нумеруются от самого маленького: 1, 2, 3…, а наименьшее число ходов для переноса башни из n дисков обозначается aₙ.
Пример 1. Составляем рекуррентное соотношение
Задача: есть три стержня A, B и C. На A лежат n дисков разного размера, от большого к маленькому. Диски двигают по одному за раз и не кладут большой диск на маленький, чтобы перенести все диски на C. Если наименьшее число ходов равно aₙ, выразите aₙ₊₁ через aₙ.
Решение: обратим внимание на самый большой диск (номер n + 1). Чтобы перенести его на C, в этот момент верхние n дисков должны лежать на B башней.
- Перенести верхние n дисков с A на B — минимум aₙ ходов.
- Переместить диск n + 1 с A на C — 1 ход.
- Перенести 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.
Решение:
- При n = 1 один диск переносится за 1 ход, и меньше нельзя, поэтому наименьшее число ходов равно 1 = 2¹ − 1, и утверждение верно.
- Предположим, что при n = k наименьшее число ходов равно 2ᵏ − 1. При n = k + 1 по рассуждению из примера 1 наименьшее число ходов равно 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, то есть утверждение верно и при n = k + 1.
- Из пунктов 1 и 2 следует, что утверждение верно для всех натуральных n.
Главное — что «≤ и ≥ одновременно» из примера 1 используется на втором шаге индукции.
Пример 4. Когда можно двигать только на соседний стержень
Задача: стержни A, B и C стоят в ряд, и диски можно двигать только между A и B и между B и C (напрямую с A на C двигать нельзя). Найдите наименьшее число ходов bₙ для переноса n дисков с A на C.
Решение: самый большой диск n нужно двинуть дважды: A → B → C.
- Перенести верхние n − 1 дисков с A на C — bₙ₋₁ ходов (чтобы двинуть диск n на B, нужно освободить B).
- Диск n с A на B — 1 ход.
- Перенести n − 1 дисков с C на A — bₙ₋₁ ходов (чтобы двинуть диск n на C, нужно освободить C).
- Диск n с B на C — 1 ход.
- Перенести 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. Задачи для тренировки
Напоследок решите сами. Ответы ниже.
- Найдите наименьшее число ходов для 10 дисков.
- При каком числе дисков наименьшее число ходов превышает 1000?
- Сколько раз двигается самый маленький диск, когда n дисков переносят кратчайшим путём?
Ответы: 1. 2¹⁰ − 1 = 1023 хода. 2. Из 2ⁿ − 1 > 1000 получаем 2ⁿ > 1001; 2⁹ = 512, 2¹⁰ = 1024, поэтому при 10 дисках и больше. 3. 2ⁿ⁻¹ раз (причина — в разделе «Сколько раз двигается каждый диск» в статье о закономерностях).
