«Лягушачье кольцо»

Однажды на Рождество аббат пообещал награду тому, кто придумает лучшую загадку. На сей раз в этом соревновании умов победил брат Бенджамин, который, как это ни странно, ни прежде, ни потом не предлагал ничего такого, что не вызвало бы насмешек у всей братии. Головоломка была названа «лягушачьим кольцом».
На полу в коридоре начертили мелом кольцо, разделенное на тринадцать частей, которое вы видите на рисунке. На каждую часть, кроме одной, положили двенадцать кружков, которые назвали «лягушками». Кружки с номерами от 1 до 6 были черными, а с номерами от 7 до 12 — белыми. Головоломка состояла в том, чтобы все черные и все белые кружки поменять местами. «Белые лягушки» движутся все в одном направлении, а «черные» — в противоположном.


Они могут двигаться в любом порядке по одному шагу за раз или перепрыгивать через лягушку противоположного цвета и опускаться непосредственно за ней. Единственное дополнительное условие заключается в том, что, когда лягушки поменяются местами, номер 1 должен расположиться на месте номера 12, и наоборот. Выполнить все это следует за наименьшее число шагов. Сколько необходимо шагов?
Я хочу закончить словами летописи: «Вот некоторые из загадок, каковые монахи Ридлуэла придумывали и задавали друг другу в славные времена доброго аббата Дэвида».

Ответ

Наименьшее число шагов равно 118. Я приведу решение полностью. Белые кружки двигаются по часовой стрелке, а черные — в противоположном направлении. Ниже приведены номера кружков, которые следует перемещать в указанном порядке. Сдвигаете ли вы просто кружок на соседнее место или перепрыгиваете через другой кружок, станет ясно из расположения кружков, ибо альтернативы не будет. Ходы, указанные в скобках, следует совершать пять раз подряд: 6, 7, 8, 6, 5, 4, 7, 8, 9, 10, 6, 5, 4, 3, 2, 7, 8, 9, 10, И (6, 5, 4, 3, 2, 1), 6, 5, 4, 3, 2, 12 (7, 8, 9, 10, И, 12), 7, 8, 9, 10, 11, 1, 6, 5, 4, 3, 2, 12, 7, 8, 9, 10, И, 6, 5, 4, 3, 2, 8, 9, 10, И, 4, 3, 2, 10, 11. 2. Таким образом, пои заданных условиях мы сделали 118 ходов; черные лягушки поменялись с белыми местами, причем номера 1 и 12 также поменялись местами .
В общем случае потребуется Зn2 + 2n — 2 ходов, где n равно числу лягушек каждого цвета. Закон, управляющий последовательностью ходов, легко обнаружить, рассматривая наиболее простые случаи, где n = 2, З и 4.
Если вместо кружков с номерами 1 и 12 должны поменяться местами кружки с номерами 6 и 7, то потребуется n2 + 4n + 2 ходов. Если мы придадим n значение 6, как в нашем случае, то получится 62 хода.