Змейка с кольцами

Головоломка не простая — даже в самом коротком решении десятки действий, — так что в уме ее вряд ли можно решить. Попробуйте сделать модель, причем начать лучше с меньшего числа колец.

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

Выясним, какие манипуляции с челноком можно делать в этой головоломке. Понятно, что челнок можно передвигать вдоль проволочной основы на участке, ограниченном кольцами. Кольца также можно передвигать вдоль проволочной петли, но тоже в ограниченной зоне. Эти действия само собой разумеющиеся. Кроме этого можно: а) вставлять конец челнока в одно или несколько колец, но без сквозного продевания; б) обводить челнок вокруг конца или петли змейки.

Покажем на серии фотографий, как снять челнок со змейки с двумя кольцами (рис. 2)

Рис. 2.

Этого можно добиться за 7 шагов из исходного состояния, показанного на первом фото:
1) вставить челнок в верхнее кольцо и обвести челнок вокруг петли змейки;
2) вставить челнок в левое кольцо и обвести челнок вокруг конца змейки;
3) извлечь челнок из левого кольца;
4) извлечь челнок из верхнего кольца;
5) вставить челнок в левое кольцо;
6) обвести челнок вокруг конца змейки;
7) извлечь челнок из змейки параллельным движением челнока вверх.

Рис. 3.

Для записи ходов удобно отметить цифрами от 1 до 7 зоны змейки, ограниченные прямыми углами (в житейском понимании угла). В начальном положении носовая часть челнока (в дальнейшем просто челнок) находится в угле №7 (рис. 3). Конечная цель — расположить челнок в угле №1 так, чтобы кольца не мешали извлечь челнок параллельным переносом вверх.

Ход — это перемещение челнока из одной зоны в другую, промежуточные движения не учитываются. Например, в рассмотренном решении для змейки с двумя кольцами сделаны три таких хода. Они показаны на рис. 4 и соответствуют фото 2, 5 и 7 с рис. 2: после этих ходов челнок оказывается в зонах 1, 2 и 1, соответственно. Научитесь делать эти движения, не обращая внимания на другие промежуточные движения челнока и записывая только порядок посещения челноком указанных зон около вершин прямых углов.

Рис. 4.

На рис. 5 показано самое короткое решение в 63 хода. Для каждого хода указан номер зоны, в которую нужно перевести челнок. Номера этих зон указаны в левом нижнем углу соответствующей схемы состояния змейки, на которой также показано положение челнока и всех колец.

Рис. 5.

Как же найти это, достаточно длинное, решение в 63 хода? И почему оно самое короткое?

Скажу честно, мне сходу не удалось снять челнок, хотя наша головоломка имеет внешние сходства с известной головоломкой «Меледа» (или «Китайские кольца»), алгоритм решения которой общеизвестен. Пришлось заняться исследованием этой головоломки досконально.

Из мягкой проволоки я сделал несколько более простых версий этой головоломки — с меньшим числом колец. На рис. 6 схематично изображена основная головоломка (правая схема) и все упрощенные варианты. Челнок на всех схемах укорочен.

Рис. 6.

Заметим, что «номер» головоломки (то есть ее положение в ряду на рисунке) совпадает с количеством колец в ней. Наша «Змейка» является шестым представителем бесконечного множества головоломок такой конструкции.

В исходном состоянии челнок каждого варианта головоломки находится в последнем уголке с наибольшим номером. Следуя тем же рассуждениям, что и в решении, будем называть ходом перемещение челнока из одного уголка в другой, при котором осуществляется переброс одного из колец через челнок. Для удобства дальнейшего изложения участки каждой «Змейки» занумеруем натуральными числами и назовем их уголками.

Понятно, что «Змейка-1» решается совсем легко, как говорится в одно движение. Как освободить челнок в «Змейке-2» подробно показано на рис. 2 и 4:
1) первым ходом нужно перевести челнок в уголок №1 и перебросить кольцо через челнок;
2) вторым ходом нужно перевести челнок в уголок №2 и перебросить кольцо через челнок;
3) третьим ходом нужно перевести челнок снова в уголок №1 и перебросить кольцо через челнок и освободить его от основы.

В этом случае головоломка решается в три хода. Запишем это, последовательно указывая номера уголков, в которых побывал челнок: 121. Мы обсуждаем решение «Змейки-2» так подробно, потому что оно лежит в основе решения «Змейки-3», которое состоит из 7 ходов и выглядит так: 1213121.

Отметим, что запись последовательности ходов в решении всех «Змеек» симметрична, а значит, снимать и надевать челнок можно по одному правилу.

Важным моментом в исследовании головоломки оказался следующий факт: каждая «Змейка», начиная со второй, содержит в себе предыдущую. Поэтому вырисовывается следующий «рекурсивный» алгоритм. Чтобы освободить челнок в «Змейке-4», его сначала переместим в четвертый уголок. Это равносильно исходному положению челнока в «Змейке-3», то есть после этого необходимо выполнить ходы 1213121. Затем перекинем кольцо через челнок в уголке №4 — и снова получим «Змейку-3», которая решается выполнением такой же серии ходов: 1213121. Таким образом, запись последовательности ходов решения «Змейки-4» содержит 15 ходов и выглядит так: 121312141213121.

Учитывая найденные закономерности, сформулируем общее правило для записи решения «Змейки» с n кольцами: запишем последовательность ходов для решения «Змейки» с (n − 1) кольцом, справа припишем число n, и опять повторим последовательность ходов для решения «Змейки» с (n − 1) кольцом.

Число ходов a_n в решении «Змейки-n» при этом определяется следующей рекуррентной формулой a_n = 2a_n−1 + 1, a₁ = 1. Методом математической индукции докажем, что a_n = 2ⁿ − 1. В самом деле, база индукции выполняется: a₁ = 1 = 2¹ − 1. Покажем что a_n+1 = 2ⁿ⁺¹ − 1. Используя рекуррентную формулу для a_n, получим, что a_n+1 = 2a_n + 1 = 2(2ⁿ − 1) + 1 = 2ⁿ⁺¹ − 2 + 1 = 2ⁿ⁺¹ − 1. Формула доказана.

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

Можно поставить точку: головоломка решена, разработан алгоритм для решения «Змеек» с любым числом колец. Но с головоломкой не хочется расставаться потому, что у нее много любопытных свойств. Например:

1) Последовательность ходов решения можно задать с помощью двоичных чисел. Действительно, если номер каждого хода представить в двоичном виде, и указать номер первой справа единицы, то получим как раз запись очередности ходов решения головоломки. Проиллюстрируем это на примере «Змейки-4», которая решается в пятнадцать ходов:

В последнем столбце этой таблицы появилась последовательность ходов для решения «Змейки-4».

2. Совершенно очевидно, что можно конструировать и решать «Змейки» с большим количеством колец, но надо помнить при этом, что число ходов от добавления одного кольца практически удваивается. Поэтому существует номер N, начиная с которого время, необходимое для на решения «Змейки-N», будет уже за всеми разумными пределами.

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

3. Еще одно свойство покажем на примере «Змейки-6»: очевидно, что переброс кольца через челнок чаще происходит в уголке №1, реже — в уголке №2, еще реже — в уголке №3 и т. д. В уголке №6 это происходит лишь однажды. Если посчитать количество операций для каждого уголка, то получим последовательность 2⁵, 2⁴, 2³, 2², 2¹, 2⁰. Поэтому общее количество ходов можно найти по-другому — как сумму шести членов этой геометрической прогрессии. Убедитесь, что она равна 63. Ясно, что это свойство можно обобщить для «Змейки» с любым числом колец.

Любители и знатоки головоломок, безусловно, обнаружат связь «Змейки» с широко известной, овеянной легендами головоломкой французского математика Эдуарда Люка Ханойская башня.

Рис. 7 Хайноская башня с 8 дисками. Фото с сайта ru.wikipedia.org

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