Башня, кубик и доска | Наука

Ханойская башня — популярная головоломка, придуманная французским математиком. Эдвард Лукас в конце 19 века. Он состоит из трех вертикальных осей, на одной из которых уложено определенное количество перфорированных дисков уменьшающихся размеров, от большего к меньшему, начиная снизу. Задача состоит в том, чтобы переместить все диски с оси, на которой они находятся, на одну из двух других, следуя этим простым правилам:

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

Очевидно, что чем больше дисков, тем сложнее перенос (в коммерческих версиях головоломки их обычно пять-восемь). дадаист башня Ханоя тривиально, для одного диска очевидно, что одного движения достаточно, чтобы переместить этот диск на другую ось. Башня с двумя дисками тоже тривиальна: меньший переносим на одну из двух свободных осей, больший – на другую свободную ось и, наконец, меньший надеваем на больший. Рассмотрим теперь башню из трех дисков, которую мы будем называть от меньшего к большему A, B и C. Для первого движения есть только один вариант: перенести диск A на одну из двух свободных осей. Для второго движения есть только один неповторяющийся вариант: переместить диск B на свободную ось. Следующие движения не уникальны, но вполне очевидны: 3) А по В, 4) С по свободной оси, 5) А по свободной оси, 6) В по С, 7) А по В. Последовательность такая. , затем АБАКАБА.

Куб

Как мы видели на прошлой неделеГамильтон изучил в Платоновых телах маршруты, носящие его имя, состоящие из прохождения всех вершин один и только один раз. В случае куба, если мы назовем А вертикальным направлением, В — горизонтальным направлением и С — переднезадним направлением, начинающимся, например, с левой верхней вершины куба и идущим сначала вниз, затем вправо, затем вверх. , затем назад и так далее, пока не завершим простой гамильтонов путь, мы увидим, что направленная (и размерная) последовательность представляет собой ABACABA, такую ​​же, как в трехдисковой Ханойской башне. Простое совпадение? Предлагаю моим проницательным читателям проверить это, найдя последовательность переходов для башни из четырех дисков, а затем ища гамильтонов путь, проходящий через вершины гиперкуба (для тех, кто не имеет прямого доступа в четвертое измерение, трехмерная проекция, подобная той, что показана на прилагаемом рисунке). Есть ли сходство между обоими маршрутами?

Доска

Согласно известной легенде, легендарный изобретатель шахмат Он попросил у короля Индии одно пшеничное зерно для первой клетки доски, два для второй, четыре для третьей, восемь для четвертой и так далее до клетки 64, удвоив количество зерен пшеницы в каждый. пшеница предыдущей. Ну а это число (18 446 744 073 709 551 615) равно числу передач, необходимых для перемещения с одной оси на другую всех дисков ханойской башни с 64 дисками, столько, сколько клеток на шахматной доске. Еще одно совпадение?

Кстати, если 64 диска сделаны из золота, а топоры – из алмазных игл, то мы сталкиваемся с (апокрифической) легендой о башне Брахмы, согласно которой наступит конец света, когда жрецы храма Бенареса закончат движение. все диски на другую ось. Но не паникуйте: даже если бы прилежные монахи двигали один диск в секунду, не отдыхая ни минуты, апокалипсис не был бы неминуемым.

Вы можете следить МАТЕРИЯ в Фейсбук, Икс е Инстаграмнажмите здесь, чтобы получить наш еженедельный информационный бюллетень.

_