Головоломки: ханойская башня

Слет научных обществ учащихся образовательных организаций общего и

Дополнительного образования детей города Нижневартовска

В 2014 - 2015 учебном году

СЕКЦИЯ №5: Прикладная математика

Головоломки. Ханойская башня

Автор:

Разуваев Данил Леонидович

Муниципальное бюджетное

общеобразовательное учреждение «Средняя

школа №15» 5Б класс

Руководитель:

Павлова Ирина Сергеевна

Учитель математики

Муниципальное бюджетное

общеобразовательное учреждение «Средняя

школа №15»

г. Нижневартовск 2015 год

Головоломки. Ханойская башня.

Разуваев Данил Леонидович

Ханты-Мансийский автономный округ-Югра (Тюменская область)

город Нижневартовск

Муниципальное бюджетное общеобразовательное учреждение

«Средняя Школа №15»

5-Б класс

АННОТАЦИЯ

Головоломки всего мира уникальны тем, что тренируют память на цифры и увеличиваю математические способности. Когда мы размышляем над головоломкой, подбираем варианты решений, вспоминаем, активизируем логические мыслительные процессы, которые работают все быстрее и быстрее, тем самым мы увеличиваем наши мыслительные возможности.

Головоломки развивают пространственное, ассоциативное и аналитическое мышление. Прикольные тесты развивают смекалку, внимание, тренируют память и быстроту восприятия.

Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

В данной работе представлен алгоритм игры "Ханойская башня", следуя которому можно решить головоломку даже школьнику. Результатом данного исследования является формула для нахождения минимального количества ходов для произвольного набора колец и модель игры для кабинета математики. Подтверждением достоверности выведенной формулы является видеоролик, на котором представлен алгоритм ходов игры для 9 колец.

Головоломки. Ханойская башня.

Разуваев Данил Леонидович

Ханты-Мансийский автономный округ-Югра (Тюменская область)

город Нижневартовск

Муниципальное бюджетное общеобразовательное учреждение

«Средняя Школа №15»

5-Б класс

ПЛАН ИССЛЕДОВАНИЯ

Головоломка - загадка, задача, требующая для своего решения догадливости и сообразительности. Разгадывать их очень интересно и познавательно. Различные виды задач и головоломок привлекают нас своей логикой и таинственностью. Поэтому я захотел сделать работу по этой теме. Решение головоломок - отличный способ проведения досуга, особенно семейного времяпровождения, ведь они развивают интеллект, сообразительность и креативность мышления. Правильно найденный ответ на заковыристое задание поднимает уровень самооценки, вселяет уверенность в собственных умственных способностях и просто повышает настроение. Поэтому разгадывание различных головоломок очень актуально в современном мире, т.к. в процессе работы над головоломкой развивается смекалка и умение мыслить неординарно. Все больше и больше требуется именно нестандартное мышление особенно в современном информационно-компьютеризированном мире. Разгадывая разные головоломки у меня возник вопрос: "Сколько ребят из нашего класса умеют разгадывать головоломки и знают ли они о такой игре как "Ханойская башня"? Заинтересовавшись данной проблемой, я решил узнать, а умеют ли разгадывать головоломки ребята нашего класса. Для этого я составил анкету, состоящую из 3 вопросов, и предложил ответить на них моим одноклассникам. (Приложение 1). По результатам проведенного опроса оказалось, что большинство ребят любят отгадывать головоломки, однако занимаются этим очень редко (Приложение 2, Диаграмма 1 -2). Также все ребята знают, что головоломки очень полезны и регулярное отгадывание их помогает развивать логику. Лишь 10 % ребят моего класса знают о такой игре, как "Ханойская башня" (Приложение 2. Диаграмма 3.) и абсолютно все хотели бы научиться в неё играть. (Приложение 2. Диаграмма 4.) Проанализировав полученные результаты моего анкетирования, я решил провести исследование на тему: «Головоломки. Ханойская башня.» и ответить на следующие вопросы:

- Кто и когда придумал первые головоломки?

- Для чего они нужны?

- Как и когда появилась логическая игра "Ханойская башня" и получиться ли у меня научиться в неё играть?

- Есть ли какая - то закономерность ходов в игре "Ханойская башня"?

Поэтому гипотеза моего исследования заключается в следующем: " В игре "Ханойская башня" существует алгоритм ходов, по которому можно играть в неё с любым количеством колец."

Цель моего исследования: смастерить модель игры - головоломки "Ханойская башня" для кабинета математики, научиться играть в игру - головоломку "Ханойская башня" и попытаться вывести формулу для расчета ходов для произвольного количества колец.

Задачи исследования:

1. Изучить литературу и интернет-источники по теме;

2. Определить что такое головоломка и для чего она нужна.

3. Когда появились первые головоломки и какие.

4. Познакомиться с игрой "Ханойская башня" и научиться в неё играть.

5. Сконструировать из подручных материалов модель игры "Ханойская башня".

6. Обобщить полученные результаты исследований, сделать выводы.

Методы исследования:

1. сбор информации;

2. анкетирование;

3. анализ собранной информации;

4. опытно - поисковые;

5. обработка опытных данных.

СОДЕРЖАНИЕ

Введение............................................................................................................................ 6

1. Теоретическая часть.....................................................................................................7

1.1. Головоломки - гимнастика ума........................................................................7

1.2. История создания игры «Ханойская башня»..................................................8

2. Практическая часть......................................................................................................9

2.1 Правила игры "Ханойская башня"...................................................................9

2.2. Выведение формулы для расчета ходов.........................................................9

Заключение.......................................................................................................................14

Список литературы..........................................................................................................15

Приложение......................................................................................................................16

Головоломки. Ханойская башня.

Разуваев Данил Леонидович

Ханты-Мансийский автономный округ-Югра (Тюменская область)

город Нижневартовск

Муниципальное бюджетное общеобразовательное учреждение

«Средняя Школа №15»

5- Б класс

ВВЕДЕНИЕ

Величие человека - в его способности мыслить.

Б. Паскаль

В наше рациональное время многие искренне полагают, что кроссворды, пасьянсы, шашки и прочие игры - всего лишь эффективное средство «убить» время, и больше от них толку никакого. Но последние исследования учёных опровергают это. Оказывается, «бесполезные игрушки» способны защитить от болезни Альцгеймера. Результаты исследования, представленные в Копенгагене на международной конференции Ассоциации Альцгеймера, свидетельствуют, что игры, стимулирующие мозговую деятельность, могут способствовать сохранности уязвимых структур мозга и когнитивных функций. Люди, которые коротают время с помощью игр, стимулирующих мыслительные процессы, показывают лучшие результаты в тестах на память, способность к обучению и восприятию информации - утверждают исследователи.

Игра "Ханойская башня" - это очень интересная и красивая головоломка. Кажется, что существует она тысячи лет. Но на самом деле она была придумана в 1883 году. Суть головоломки и алгоритм ее сборки и составляют предмет данной работы.

1. Теоретическая часть.

1.1. Головоломки - гимнастика ума.

Математические головоломки, это различные, запутанные задания с подвохом. Как правило на логику и смекалку, с определенными условиями решения, к примеру: " Нужно соединить нарисованные девять точек четырьмя прямыми линиями не отрывая ручки от листа бумаги." (Рис. I.)

Рис.I.

Первые головоломки - разгадывание игры слов, собирание замысловатых конструкций - появились ещё в III веке до нашей эры. Большей частью они основывались на умозаключениях и математических расчётах. То же касалось и настольных игр для двух и более участников, в которых уже был задействован дух соревнования. Эти занятия обучали, развивали интуицию и логическое мышление, учили терпению и последовательности. Сегодня предметы «гимнастики для ума» становятся широко востребованными в деловой сфере и просто в повседневной жизни. Первые головоломки были громоздки и небезопасны в использовании, особенно, если это игра для детей. Их даже отказывались экспортировать на Запад, что явилось одной из причин запоздалой популярности головоломки.

Самая знаменитая головоломка мира была изобретена в 1974 году венгерским скульптором и профессором архитектуры Эрно Рубиком. По одной из версий кубик Рубика изначально создавался как учебное пособие. При помощи него Рубик пытался втолковать воспитанникам основы математической теории групп. В начале изобретение представляло собой набор из 27 деревянных кубиков с разноцветными гранями (всего 27 х 6=156 цветных граней). В современном виде кубик Рубика появился лишь в 1980 году. Тогда же кубик сменил прозвище с «магического куба» на «кубик Рубика» . Новое прозвище прижилось, и только в Венгрии, Португалии и Германии головоломку по-прежнему называют «магический куб» . Выделились и китайцы, отвергнувшие оба варианта названия. У них игра называется «венгерский куб» . Только за два дебютных года по всему миру было реализовано более 100 млн. фирменных кубиков. И еще в полтора раза больше подделок. Первые головоломки Puzzle появились еще в XVIII столетии, когда некий изобретатель наклеил географическую карту на деревянную доску и разрезал ее.

Принято считать, что логические и прочие интеллектуальные игры "не дают мозгу засохнуть". Пожилым людям рекомендуют разгадывать ребусы и решать кроссворды, чтобы сохранить хорошую память. Детей заставляют учить наизусть стихи, а молодые люди на досуге проходят логические квесты, чтобы развиваться умственно. Никто не спорит, что необходимо развивать интеллект и поддерживать активность мозга. Но не все, что мы считаем полезным для умственных способностей, действительно является таковым.

Британские ученые доказали, что разгадывание кроссвордов и тому подобная активность "омолаживает" мозг. Учеными доказано, что решение логических задачек улучшает кровообращение в мозге, то есть действует подобно физическим упражнениям. Люди старше 65, регулярно сидящие за кроссвордами и ребусами, реже страдают ухудшением памяти и болезнью Альцгеймера, заявили британские нейрофизиологи.

1.2. История создания игры «Ханойская башня»

"Ханойская башня" является одной из популярных головоломок XIX века.

Эту игру придумал французский математик Эдуард Люка (Рис. II. ), в 1883 году, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус из Колледжа Ли Су Цян», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры, профессора Люка из колледжа Сен-Луи.

Рис.II.

Эдуард ЛюкаЛегенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.

Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Легенда о Храме Варанаси была придумана Люка, чтобы заинтересовать публику.

Количество перекладываний в зависимости от количества колец вычисляется по формуле .

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

А с каким количеством дисков башня считается классической? Или нет такого понятия? Я думаю, что 10. По крайней мене столько дисков было нарисовано на оригинальной коробке Лукаса. (Рис. III.)

Рис.III.

Игра "Ханойская башня"

2. Практическая часть

2.1. Правила игры "Ханойская башня".

В классической версии игра состоит из подставки с тремя стержнями, на одном из которых нанизано определённое количество дисков разного размера, от большего внизу к меньшему наверху.

Игра заключается в том, чтобы передвинуть диски с одного стержня на другой, не нарушая следующие правила:

• За один ход может быть передвинут только 1 диск;

• Нельзя перемещать диск на соседний стержень, если на него нанизан диск меньшего размера.

Когда дисков совсем немного, игра кажется лёгкой. Но с увеличением количества дисков растёт и количество шагов, которые надо предпринять, чтобы диски перенести, а вместе с этим усложняется сама игра.

Во сколько шагов решается головоломка?

2.2. Выведение формулы для расчета ходов.

Я решил узнать, как увеличивается количество ходов от количества колец. Для этого я смастерил модель игры - головоломки "Ханойская башня" из подручных материалов (в моем случае это кольца пирамиды, нанизанные на стержень). (Приложение 3. Фото.1-4.)

Исследование №1 (с одним кольцом).

Переместить его на любой из стержней можно одним движением. Всего 1 шаг.

Схема игры.

A

C

A

C

Исследование №2 ( с двумя кольцами).

Решение заключается в следующей последовательности шагов:

1. Перемещаем маленькое кольцо на стержень В;

2.Перемещаем большое кольцо на стержень С;

3.Переносим маленькое кольцо на стержень С.

Всего 3 шага.

Схема игры.

1

A

C

A

C

3

2

A

C

A

C

Исследование №3 ( с тремя кольцами).

Решение заключается в следующей последовательности шагов:

1.Перемещаем маленькое кольцо на стержень С;

2. Перемещаем среднее кольцо на стержень В;

3. Переносим маленькое кольцо на стержень В;

4. Переносим большое кольцо на стержень С;

5. Перемещаем маленькое кольцо на стержень А;

6. Перемещаем среднее кольцо на стержень С;

7. Переносим маленькое кольцо на стержень С.

Как видим количество шагов увеличится. Всего 7 шагов.

Схема игры.

1

A

C

A

C

2

3

A

C

A

C

4

5A

C

A

C

6

7

A

C

A

C

Я заметил что, процесс делится на три части. Сначала переносится башня из двух колец со стержня А на стержень В. Затем перемещается большое кольцо со стержня А на стержень С. И в итоге со стержня В на стержень С переносится башенка из двух колец. Чтобы передвинуть башню из двух колец, мне необходимо было 3 шага, а для перемещения башни из трёх колец мне потребовалось 3+1+3=7 шагов.

Чтобы перенести башню из четырех колец с первого стержня на третий, я действовал по следующему алгоритму:

1) перенести башню из трех верхних колец с первого стержня на второй (7 ходов);
2) самое большое кольцо перенести с первого стержня на третий (1 ход);
3) перенести башню из трех колец со второго стержня на третий (7 ходов).

Всего на перенос потребовалось 15 ходов. Сначала три верхних я переместил на стержень В, затем большое кольцо - с А на С, и в конце оставшиеся три кольца со стержня В на С. Здесь у меня получилось 7+1+7=15 шагов. Аналогично, я сосчитал число ходов, необходимых для переноса башни из пяти колец:
15 + 1 + 15 = 2 • 15 + 1 = 31, а потом проверил это на практике.

Для башни из 6 колец я получил 2 • 31 + 1 = 63 и т. д. И так по нарастающей. Для десяти колец необходимо как минимум 1023 шага, а для шестидесяти четырёх - 18 446 744 073 709 551 615 шагов.

Таким образом я вывел алгоритм (формулу) для определения количества ходов, в зависимости от количества колец. Получилась следующая закономерность: при увеличении количества колец на 1 (n+1) количество ходов увеличивается в 2 раза +1 ход (x*2+1). Таким образом, зная количество ходов для 8 колец, можно вычислить количество ходов для 9 колец.

X(9)=255*2+1=511

Количество ходов для 9 колец я проверил опытным путём и получил такое же количество ходов как и по формуле. Сама последовательность ходов при перекладывании пирамиды из 9 колец, представлена в видеоролике, прилагающемся к работе.

Результаты, полученные опытным путём, представлены в таблице 2.1.

Таблица 2.1.

Количество колец (n)

Количество ходов (x)

1

_{= 2n - 1}

2

3

4

5

6

7

8

9

?

Но полученная формула удобна только в том случае, когда нам известно количество ходов для n колец, а найти необходимо для n+1 кольца. В других случаях её использование невозможно. Поэтому я задумался над выведением другой формулы.

Математическая формула, описывающая эту операцию, выглядит так:

2ⁿ-1, где n-количество колец.

Проверяя для 9 колец, я получил 2⁹-1=512-1=511

Для решения этой "Ханойской башни" мне потребовалось 511 шагов.
Минимальное количество шагов, которое необходимо выполнить, чтобы решить головоломку с любым количеством колец показано в таблице 2.2.

Таблица 2.2.

Количество колец (n)

Количество ходов (x)

1

2

3

4

5

6

7

8

9

Зная эту формулу, мы можем определить наименьшее количество ходов для любого количества колец. Например, для десяти колец необходимо как минимум шага, а для шестидесяти четырех колец шагов.

ЗАКЛЮЧЕНИЕ

В результате работы над проектом я смастерил из подручных материалов игру - головоломку "Ханойская башня", научился в неё играть и вывел формулы для определения количества ходов, зависящих от количества колец в данной игре. Через решение данной головоломки на практике сначала для одного кольца, потом для двух, трёх и т.д. мне удалось подтвердить выдвинутую гипотезу и установить, что

1. Игру "Ханойская башня" можно самому смастерить из подручных материалов.

2. В игру "Ханойская башню" может научиться играть любому, кому она интересна.

3. В игре существует закономерность (определенный алгоритм) с помощью которой можно сразу определить по формуле наименьшее количество ходов в зависимости от количества колец в игре.

Данное исследование может пригодиться для занятий на факультативах по математике по разгадыванию головоломок и решению логических задач, тем самым развивать у ребят усидчивость, навыки решения логических задач и настойчивость, расширит кругозор учащихся и заинтересует их к дальнейшим разгадываниям логических задач и головоломок. Модель игры "Ханойская башня", которую мне удалось создать, находится в кабинете математики и в неё можно играть всем учащимся на переменах.

Мозгу человека свойственна пытливость и тяга к самосовершенствованию. Не случайно многие проявляют интерес к разгадыванию кроссвордов, сканвордов и прочих головоломок связанных с использованием и накоплением собственно словарного запаса. Во время раздумывания над головоломкой наше серое вещество работает на полную катушку и мобилизует все силы. Это приводит к тому, что происходит оценка предыдущего опыта, анализ ошибок и выработка стратегий на будущее, как это было показано в моём исследовании при решении головоломки "Ханойская башня" в зависимости от количества колец. Я испытал великолепную тренировку ума и своих мыслительных способностей. Таким образом, логические головоломки - это способ не только приятного, а еще и полезного времяпровождения.

СПИСОК ЛИТЕРАТУРЫ

1. Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. - 3-е изд., испр. и доп. - М.: БИНОМ. Лаборатория знаний, 2005. - 208 с.: ил.

2. Занимательные головоломки, выпуск №6, 2012г., ООО «Де Агостини», Россия.

3. Интернет-ресурсы. Википедия. school.xvatit.com/index.php?titlesudokuplus.ru/Page015.htmsc125.vegaint.ru/work2011/6class

4. shkolazhizni.ru/archive/0/n-70555/

5. playlab.ru/club/history/rubiks_cube/

6. happymozg.ru/brain/reasoning-logic/hanoyskaya-bashnya/play/

Приложение 1.

Анкета

1. Любишь ли ты решать различные головоломки: логические задачи, задачи-шутки, задачи со спичками? _____________________________________________________

2. Часто или редко ты этим занимаешься? _______________________________

_______________________________________________________________________

3. Для чего нужны головоломки?______________________________________

_______________________________________________________________________

4. Знаешь ли ты такую логическую игру как "Ханойская башня"?___________

_______________________________________________________________________

5. Хочешь научиться в неё играть?______________________________________

________________________________________________________________________

Приложение 2.

Диаграмма 1.

Диаграмма 2.

Диаграмма 3.

Диаграмма 4.

Приложение 3.

(фото.2.)

(фото.4.)

(фото.3.)

(фото.1.)