В статье описывается старинная головоломка, русский вариант которой известен под названием «меледá». Решение этой головоломки тесно связано с информатикой. Здесь и первое в истории практическое использование двоичной системы счисления, рекурсивные алгоритмы, рекуррентные соотношения и др.

Головоломка, в России называемая старинным словом «меледá», состоит из замкнутой проволочной «вилки» («челнока»), имеющей вид длинной шпильки для волос и воткнутой обоими свободными концами в рукоятку, и нескольких колец, связанных между собой довольно сложным образом (см. рис. 1). Задача состоит в том, чтобы снять всю систему колец с вилки или надеть её обратно. 

 Рис. 1

 Французское название головоломки – baguenaudier, что означает «узел колец», немецкое – das magische Ringspiel, или «магическая игра с кольцами», описанная ещё в 1789 году Иоганном Николаусом Мартиусом (см. [1]). Свои варианты этой головоломки есть и у других народов.

Основная версия происхождения головоломки связана с Древним Китаем. В настоящее время там она называется Jiǔ liánhuán (九连环), что можно перевести как «девять связанных колец».

Китайские легенды рассказывают о герое, который, уезжая на войну, передал головоломку своей жене с очевидным мотивом «развлечь» её во время своего отсутствия (Стюарт Кулин в своей этнологической работе по восточным играм и головоломкам [2] пишет о том, что этим заботливым мужем был реальный человек по имени Хун Мин [2, с. 3]).

Вместе с тем исследователи не исключают и европейское происхождение головоломки. Самое раннее известное упоминание о ней в Европе связано с книгой Луки Пачоли «О способностях чисел» [3, с. 290–292], изданной около 1500 г., в которой описывается предмет с кольцами и методика установки колец на «вилку». Пачоли использует при этом фразу «тяжёлый случай».

Приведу правила, которые необходимо соблюдать при решении головоломки. Первое (на рис. 2 – крайнее правое) кольцо можно всегда снять или надеть на вилку. Любое другое кольцо можно снять или надеть только тогда, когда кольцо непосредственно справа от него надето, а все остальные справа – сняты.

Рис. 2

 Приведённое на рис. 2 изображение головоломки было представлено в книге [4] французского математика Эдуарда Люкá (1842–1891). Учёный сообщает, что в 1872 году неизвестный автор опубликовал в Лионе (Франция) 16-страничную брошюру «Théorie du baguenaudier, par un clerc de notaire lyonnais» (напомним, что baguenaudier – это французский аналог меледы), но далее отмечает: «Нам недавно удалось узнать, что это был Луи Гро, советник лионского апелляционного суда» [5, с. 169].

Луи Гро в своей работе [6], среди прочего, приводит таблицу, начальный фрагмент которой показан на рис. 3.

Рис. 3

Анализ показывает, что в данной таблице:

1) схемы с линией и точками выше и ниже её иллюстрируют текущую ситуацию на головоломке, когда стоит задача надеть на «вилку» некоторое количество колец (в заключительной части таблицы представлены ситуации при снятии всех колец). Точки соответствуют кольцам: расположенные над линией – надетым, находящиеся ниже линии – снятым;

2) десятичные числа слева – порядковые номера манипуляций с кольцами (ходов);

3) числа под схемами – двоичный эквивалент номера хода.

Приведённая таблица позволяет определить (что, собственно, и сделал Гро) общее число ходов, требующихся для решения головоломки при том или ином количестве колец. Ключевыми при этом являются ситуации, при которых все кольца надеты (то есть все точки на схеме расположены над линией). Они соответствуют номерам ходов 5, 10 (см. рис. 3), 21, 42, 85 и т. д. Зависимость количества ходов от числа колец будет следующей:

Найденные количества ходов позволили Гро определить примерное время, требующееся для решения головоломки при том или ином числе колец. Он пишет: «64 перемещения можно без труда сделать за минуту, а если постараться, то и 80. Но примем 64 как среднее число, тогда для снятия пяти колец (требуется 21 перемещение) понадобится 20 секунд…» и указывает время, требующееся для решения головоломки:

– при семи кольцах – 1 мин 20 сек;

– при девяти кольцах 5 мин 20 сек;

– при 11 кольцах – 21 мин 20 сек;

– при 13 кольцах – 1 час 25 мин 20 сек.

Для решения же головоломки с 25 кольцами при ежедневной десятичасовой работе потребуется … более 582 дней! Недаром название «меледа» в словаре В. И. Даля толкуется как мешкотное дело, длительная, однообразная забава.

 Эдуард Люка в уже упоминавшей книге [4] развил идею Луи Гро по использованию связи ситуации на схеме головоломки с двоичным номером соответствующего хода для определения количества ходов, необходимых при переходе от некоторого состояния головоломки к любому другому. Это количество равно разности десятичных эквивалентов двоичных номеров двух состояний. Исследуя данную проблему, учёный преобразовал таблицу из работы Гро к виду (см. рис. 4), облегчающему её анализ. 

Рис. 4

Кроме того, Люка пишет, что «игра … наглядно объясняет процесс образования сочетаний без повторений из n предметов, а также указывает порядок, в каком эти сочетания следуют одни за другими» [4, с. 148]. Действительно, в ходе решения головоломки, например, с четырьмя кольцами (при их снятии – см. ниже), на головоломке будут представлены все состояния, схемы которых соответствуют двоичным числам от 1111 (все кольца надеты) до 0001 (надето только крайнее правое кольцо). А двоичные числа:

1000, 0100, 0010, 0001,

1100, 1010, 1001, 0110, 0101, 0011,

1110, 1101, 1011, 0111,

1111

соответствуют всем возможным сочетаниям из четырёх предметов a, b, c, d:

a, b, c, d,

ab, ac, ad, bc, bd, cd,

abc, abd, acd, bcd,

abcd.

Таким образом можно считать, что выводы, полученные Луи Гро и Эдуардом Люка, представляют собой, так сказать, «первое в истории практическое использование двоичной системы счисления».

Обсудим теперь решение головоломки для общего случая. Начнём с простых вариантов. Когда нужно снять или надеть два кольца, алгоритмы решения задач (назовём их, соответственно, Надеть(2) и Снять(2)) очевидны:

Несложными являются и аналогичные задачи для трёх колец. Для их снятия сначала следует как-то снять третье кольцо. Это можно сделать, только предварительно сняв первое (крайнее справа) кольцо. Чтобы снять и оставшееся второе кольцо, нужно надеть первое кольцо – после этого возникнет задача снятия двух колец, решение которой уже известно:

Алгоритм же надевания трёх колец будет следующим:

 В общем случае при n кольцах алгоритмы действий такие:

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

Отметим ещё две интересные закономерности. Если смоделировать меледу с четырьмя кольцами в виде четырёхзначного числа, в котором 1 соответствует надетому кольцу, а 0 – снятому, то пошаговому выполнению алгоритма Надеть(4) будет отвечать следующие изменения модели:

0000

0001

0011

0010

0110

0111

0101

0100

1100

1101

1111

В полученной последовательности неповторяющихся четырёхзначных чисел все «соседние» числа отличаются только одной цифрой. Если рассматривать состояния модели как двоичные числа, то полученная последовательность будет представлять собой так называемый «код Грея» (по имени его изобретателя, американского инженера Фрэнка Грея, предложившего данный код в 1952 году).

Если при решении головоломки для рассматриваемого случая (4 кольца) выписывать номера снимаемых или надеваемых колец, то можно получить такую последовательность номеров: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2. При надевании пяти колец соответствующая последовательность будет иметь вид

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1.

Можно увидеть, что началом этой последовательности является приведённая чуть выше последовательность для надевания четырёх колец.

Аналогично при надевании шести колец начало соответствующей последовательности будет представлять из себя последнюю последовательность (убедитесь в этом!).

В общем случае при надевании n колец последовательность будет начинаться с соответствующей последовательности для n – 1 колец.

Графически значения первых 256 членов этой последовательности при надевании девяти колец представлены на рис. 5 [7].

Рис. 5

Приведённое на рис. 5 изображение напоминает изображение на измерительных линейках, где линии, соответствующие целым миллиметрам, 5 миллиметрам и сантиметрам, имеют разную длину. Поэтому такую графическую зависимость называют «функцией линейки» (ruler function), а саму описанную последовательность чисел нередко называют, отдавая дань автору брошюры [5], «последовательностью Гро».

Оказывается, значение любого члена N_k последовательности Гро можно определить по его порядковому номеру k. Зависимость будет следующей:

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

Последовательность Гро (связанная со старинной головоломкой!)  и сегодня широко используется в математике и информатике. Свойства последовательностей данного типа активно применяются для исследования вопросов, связанных с дискретной математикой, в частности, в теории автоматов, в решении некоторых задач геометрии (см., напр., [6]), в теории вероятностей и др.

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

1) перемещать диски можно только по одному;

2) нельзя диск большего диаметра класть на диск меньшего размера;

3) снятый диск нельзя отложить в сторону — его нужно сразу надеть на один из других стержней.

 Например, при трёх дисках, пронумерованных сверху вниз, последовательность номеров перемещаемых при решении дисков такая:

1, 2, 1, 3, 1, 2, 1,

при четырёх:

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

и т. п.

При решении головоломки «Ханойские башни», как и при решении меледы, многократно выполняют аналогичные действия, но с меньшим количеством дисков. Всё это дает мне основания предположить, что идея головоломки «Ханойские башни» возникла у её изобретателя (а им, как известно, является упоминавшийся Эдуард Люка [7]) после знакомства с «французской меледой» и её анализа.

Желаюшие попробовать решить меледу - см. https://infojournal.ru/wp-content/uploads/2021/01/meleda.html

 Литература

1. Martius, Johann Nikolaus. Unterricht in der natürlichen Magie, oder zu allerhand belustigen den und nützlichen Kunststücken. – Berlin, 1789.    http://chesswanks.com/txt/meleda/DasMagischeRingspiel(1789).pdf   

2. Culin, Stewart. Korean games with notes on the corresponding games in China and Japan. – University of Pennsylvania, Philadelphia PA, 1895.

3. Pacioli, Luca. De Viribus Quantitatis, Raccolta Vinciana. – Milano, 1997.

4. Lucas, Edouard. Récréations mathématiques. – Paris. 1892. https://archive.org/stream/rcrationsmathma00lucagoog#page/n26/mode/1up

5. Théorie du baguenaudier par un clerc de notaire lyonnais.  https://books.google.ru/books/about/Th%C3%A9orie_du_baguenaudier_par_un_clerc_de.html?id=EcoBJRekd-sC&redir_esc=y

6. Nuño, Juan Carlos; Muñoz, Francisco J. On the ubiquity of the ruler sequence. https://arxiv.org/abs/2009.14629

7. История одной известной головоломки. https://habr.com/ru/articles/931274/