Ханойская башня — отличная головоломка для школьного исследовательского проекта. Если добавлять диски по одному и выяснять «наименьшее число ходов», можно увидеть удивительную закономерность в числах. Инструменты можно сделать самим, а оформить работу получится за день или несколько дней. (В Японии школьники часто делают такой «свободный исследовательский проект» на летних каникулах.)
Примеры тем
- Как меняется наименьшее число ходов, когда добавляется один диск?
- Сколько лет понадобится, чтобы перенести 64 диска?
- Сколько раз двигается самый маленький диск?
Дальше мы разберём, как вести работу, на примере первой темы.
Что подготовить
- Ханойскую башню (её можно сделать из картона или монет, как в статье о том, как её сделать. Лучше, чтобы было 6 дисков)
- Тетрадь для записей и карандаш
- Если есть, палочки на бумаге для подсчёта ходов (чёрточки по пять) или счётчик
Попробовать можно и на доске внизу этой страницы.
Как проводить опыт
- Проверьте правила: за раз двигают только один диск. Нельзя класть большой диск на маленький. Башню нужно целиком перенести с левого стержня на правый.
- Начните с одного диска: переносите 1 диск, 2 диска, 3 диска… добавляя по одному.
- Считайте ходы: каждое перемещение считается за один ход.
- Сделайте несколько попыток и запишите наименьшее число ходов: сначала можно ходить окольным путём. Повторите несколько раз и найдите число ходов, меньше которого уже не получается.
Пример таблицы записей
| Число дисков | Наименьшее число ходов | Связь с предыдущим числом |
|---|---|---|
| 1 | 1 | ― |
| 2 | 3 | 1 × 2 + 1 |
| 3 | 7 | 3 × 2 + 1 |
| 4 | 15 | 7 × 2 + 1 |
| 5 | 31 | 15 × 2 + 1 |
| 6 | ? | ? |
В таблице стоит число ходов, которое получается при правильном решении. Сначала сосчитайте сами, а потом сравните.
Ищем закономерность
Когда записи собраны, внимательно посмотрите на ряд чисел ходов: «1, 3, 7, 15, 31».
- Если предыдущее число умножить на 2 и прибавить 1, получится следующее: 3 × 2 + 1 = 7, 7 × 2 + 1 = 15.
- Если к числу ходов прибавить 1, получатся числа, которые удваиваются: 2, 4, 8, 16, 32.
Подумайте и о том, почему получается «умножить на 2 и прибавить 1». Например, чтобы перенести 4 диска, нужно:
- временно убрать верхние 3 диска на средний стержень (столько же ходов, сколько для переноса 3 дисков);
- переместить самый большой диск вправо (1 ход);
- перенести 3 диска со среднего стержня вправо (снова столько же ходов, сколько для переноса 3 дисков).
Число ходов для 3 дисков два раза и ещё один ход. Поэтому и получается «умножить на 2 и прибавить 1».
Предскажите и проверьте
Когда закономерность найдена, предскажите число ходов для 6 дисков, а потом проверьте на деле. Должно получиться 31 × 2 + 1 = 63 хода. Если предсказание сбылось, закономерность подтверждена.
Затем продолжите предсказания: 7 дисков (127 ходов), 10 дисков (1023 хода). Для 64 дисков получится огромное число. Даже при одном ходе в секунду понадобится около 585 млрд лет (Сколько лет понадобится на 64 диска?).
Пример оформления
Если вы оформляете работу на ватмане или листе плотной бумаги, понятнее всего такой порядок.
- С чего началось исследование: как вы узнали о Ханойской башне и что вас удивило.
- Правила Ханойской башни: объясните их рисунками.
- Как исследовали: до скольких дисков дошли и как считали.
- Результаты: таблица записей и график числа ходов (если отложить по горизонтали число дисков, а по вертикали число ходов, будет видно, как быстро оно растёт).
- Что выяснили: найденная закономерность и её причина.
- Впечатления и что хотелось бы исследовать дальше: легенда о 64 дисках, что будет с четырьмя стержнями и так далее.
Если добавить рассказ об истории и легенде Ханойской башни (происхождение и легенда), работу будет интереснее читать.
Попробуйте
Доска ниже начинается с 3 дисков. Меняйте число дисков и выясняйте наименьшее число ходов. Ходы она считает сама.
