|
Название задачи: Ханойская башня I. |
 |
Условие
а) Головоломка "Ханойская башня" представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трёх колышков. Требуется переместить всю башню на другой колышек, перенося каждый раз только один диск и не помещая больший диск на меньший. Докажите, что головоломка имеет решение. Какой способ будет оптимальным (по числу перекладываний дисков)?
б) Занумеруем колышки числами 1, 2, 3. Требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й и с 3-го на 1-й запрещено (каждое перекладывание должно производиться через 2-й колышек)?
в) Сколько понадобится перекладываний, если в условии пункта а) добавить дополнительное требование: первый (самый маленький) диск нельзя класть на 2-й колышек?
Решение
а) Пусть минимальное число шагов для перемещения башни из n дисков равно Kn. Выразим Kn+1 через Kn.
Рассмотрим башню из n + 1 диска. Разобьём всю процедуру на три этапа.
Этап 1 – от начала до первого перемещения нижнего диска. В конце этого этапа стоящая на нижнем диске башня из n дисков должна переместиться на один из свободных колышков (колышек, на который следующим шагом должен переместиться нижний диск, должен быть свободен). Нижний диск в этих перемещениях не участвует, следовательно, для этого необходимо (и достаточно) Kn шагов.
Этап 2 – от первого до последнего перемещения нижнего диска. Одного шага достаточно: после первого перемещения нижний диск можно больше не трогать.
Этап 3 – после последнего перемещения нижнего диска. В начале этого этапа колышек, с которого перед этим был снят нижний диск, свободен. Значит, на третьем колышке стоит башня из n дисков, и ее надо переместить на нижний диск. Для такого перемещения также нужно Kn шагов.
Итак, Kn+1 = Kn + 1 + Kn = 2Kn + 1 (выше показано, что меньшим числом шагов обойтись нельзя, а такого количества достаточно).
Поскольку K1 = 1, мы можем последовательно вычислить K2, K3, ..., K8.
Нетрудно вывести и общую формулу: записав полученное соотношение в виде Kn+1 + 1 = 2(Kn + 1), имеем Kn + 1 = 2n–1(K1 + 1) = 2n.
Замечание. "Угадав" ответ, можно его доказать по индукции.
б) Рассуждаем аналогично. Заметим, что здесь K1 = 2.
Сначала придется переместить башню из n дисков с 1-го колышка на 3-й (Kn шагов). Теперь можно переместить нижний диск на 2-й колышек. Затем придется вернуть остальные диски на 1-й колышек, и тогда можно переложить нижний диск на 3-й колышек. Останется снова переместить остальные диски с 1-го колышка на 3-й. Поэтому в нашей ситуации Kn+1 = Kn + 1 + Kn + 1 + Kn = 3Kn + 2.
Записав его в виде Kn+1 + 1 = 3(Kn + 1), получим Kn + 1 = 3n–1(K1 + 1) = 3n.
в) Из-за того, что все башни, содержащие первый диск, приходится собирать на 3-м или 1-м колышках, отличие от рассуждений п. б) только в том, что K1 = 1. Поэтому из того же соотношения Kn + 1 = 3n–1(K1 + 1) получаем Kn = 2·3n–1 – 1.
Ответ
а) Самый короткий способ содержит 28 – 1 = 255 перекладываний.
б) 38 – 1 = 6560 перекладываний; в) 2·37 – 1 = 4373 перекладывания.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 1 |
| Название | Метод математической индукции |
| Тема | Индукция |
| параграф | |
| Номер | 3 |
| Название | Индукция в геометрии и комбинаторике |
| Тема | Индукция (прочее) |
| задача | |
| Номер | 1.42, 1.43, 1.44 |
