Магнитная башня Ханоя - Magnetic Tower of Hanoi

Загадка Магнитная башня Ханоя (MToH)

В Магнитная башня Ханоя (MToH) пазл - это вариация классической Ханойская башня головоломка (ToH), где у каждого диска есть две разные стороны, например, с разными цветами «красный» и «синий». Правила головоломки MToH такие же, как правила исходной головоломки, с добавленными ограничениями, что каждый диск переворачивается при перемещении, и что два диска не могут быть помещены один на другой, если их соприкасающиеся стороны имеют одинаковый цвет. . Каждый диск имеет северный и южный полюса, при этом одинаковые полюса отталкиваются друг от друга, а противоположные полюса притягиваются друг к другу. Магниты внутри каждого диска физически предотвращают незаконные перемещения.^[1]

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

Одной из ярких особенностей классической головоломки ToH является ее связь с основанием 2: минимальное количество ходов, необходимых для решения головоломки, равно 2.^п - 1 (где п количество дисков), а минимальное количество ходов, совершаемых диском k 2^k − 1 (диски пронумерованы снизу вверх, чтобы k = 1 - самый большой диск, и k = п будучи самым маленьким). Ниже будет показано, что так же, как исходная головоломка ToH связана с основанием 2, так и MToH связана с основанием 3, хотя и более сложным образом.^[2]

Источник

Математически эквивалентные головоломки для определенных вариаций MToH известны в течение некоторого времени. Например, головоломка, эквивалентная одной из цветные вариации MToH появляется в Конкретная математика.^[3] В этой головоломке движения разрешены только между определенными сообщениями, что эквивалентно присвоению постоянных цветов сообщениям (например, если двум сообщениям назначен один и тот же постоянный цвет, то прямые перемещения между двумя сообщениями не разрешены).

Бесплатная (неокрашенная) MToH впервые появилась публично в Интернете.^[4] около 2000 года (хотя и под названием «Domino Hanoi») как часть подробного обзора математиком Фредом Ланноном различных вариаций оригинальной загадки Ханойской башни.

MToH был независимо изобретен физиком Ури Леви летом 1984 года, который также придумал название и аналогию с магнетизмом.^{[требуется разъяснение ][5]} Позже доктор Леви опубликовал серию статей. ^[1][6][7] имея дело с математическими аспектами MToH.

Описание головоломки

Исходное положение головоломки

Головоломка MToH состоит из трех постов, помеченных как источник (S), место назначения (D) и промежуточное звено (I), а также стопка п диски разного размера, причем каждая сторона диска имеет разный цвет: красный или синий. В начале головоломки диски укладываются на стойку S в порядке уменьшения размера (т. Е. Самый большой диск находится внизу) и так, чтобы все диски были обращены красной стороной вверх. Задача головоломки (в ее «базовой» версии) - переместить весь стек, по одному диску за раз, к стойке D, поддерживая порядок от самого большого диска к самому маленькому, но с синими сторонами вверх.

Конечная позиция головоломки

Правила, регулирующие движение дисков, следующие:

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

Решение головоломки для п = 2 и п = 3

Чтобы проиллюстрировать правила MToH, а также показать путь к более общему решению, полезно проработать примеры для п = 2 и п = 3. В случае п = 2, требуется четыре шага, как показано на прилагаемом рисунке, по сравнению с тремя шагами в п = 2 случай оригинального ToH. Дополнительный шаг необходим, потому что после второго шага маленький диск нельзя переместить непосредственно из сообщения I в сообщение D, так как это будет означать, что его синяя сторона будет обращена вниз. Таким образом, требуется дополнительный шаг, чтобы перевернуть цвет маленького диска, чтобы затем его можно было поместить на стойку D синей стороной вверх.

Решение п = 2 головоломки

Для п = 3, решение включает следующие шаги:

• Пронумеруя диски с 1 по 3 от наибольшего к наименьшему, сначала перемещают диски 2 и 3 из стойки S в столб I (четыре хода).

Этот первый этап похож на п = 2, описанная выше, которая также требует четырех ходов, где стойки D и I меняются местами. Однако он не идентичен п = 2 загадка из-за наличия большого диска на столбике S, который «окрашивает» его в красный цвет. Это означает, что диск можно ставить на эту стойку только красной стороной вверх.

• Переместите диск 1 из S в D (один ход)

На этом этапе может возникнуть соблазн снова использовать п = 2, и попробуйте переместить диски 2 и 3 из I в D за 4 хода. Однако и здесь требуется осторожность. Из-за наличия диска 1 на D, D теперь "окрашен" в синий цвет, то есть другой диск может быть помещен на него, только если его синяя сторона обращена вверх. Кроме того, с п = 2 загадка: диски имеют красную сторону вверх в исходном положении, тогда как здесь их синие стороны обращены вверх. Таким образом, эта промежуточная конфигурация не эквивалентна п = 2 MToH. Вместо этого мы действуем следующим образом:

• Переместите диск 3 из I в D через S (2 хода)
• Переместите диск 2 из I в S (1 ход)
• Переместите диск 3 из D в I (1 ход)
• Переместите диск 2 из S в D (1 ход)
• Переместите диск 3 из I в D (1 ход)

Таким образом, всего решение требует 11 шагов. Как только что было показано, естественно попытаться использовать п = 2 решение для решения частей п = 3 пазла в рекурсивный способ, который обычно используется для решения классической головоломки ToH. Однако, в отличие от классического ToH, здесь п = 2 нельзя наносить вслепую из-за окраски столбов и дисков. Этот момент показывает, что для достижения более общего решения для п-дисковая головоломка MToH, необходимо рассмотреть варианты головоломки, в которой столбики предварительно окрашены (синий или красный). Рассматривая эти варианты, можно разработать полные рекурсивные отношения для загадки MToH и, таким образом, найти общее решение.

Цветные вариации головоломки MToH

Цветные вариации «сестринских головоломок» MToH

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

Возможны и другие варианты головоломки MToH, когда сами стойки окрашиваются, как показано на прилагаемом рисунке. Если сообщение предварительно окрашено в красный / синий цвет, то на этот предварительно окрашенный столб можно помещать только диски красной / синей стороной вверх. Различные варианты MToH могут быть названы с использованием трехбуквенной метки «SID», где S, ID относятся к цвету исходных, промежуточных и целевых сообщений соответственно, и могут принимать значения R (красный), B (синий). , или N (нейтральный - без цвета). Таким образом, загадка «NNN» относится к бесплатному MToH, тогда как загадка «RBB» относится к варианту, в котором столб S предварительно окрашен в красный цвет, а столбики I и D предварительно окрашены в синий цвет.

Хотя вариации MToH сами по себе являются головоломками, они также играют ключевую роль в решении бесплатного MToH. Как видно выше, промежуточные состояния бесплатного MToH можно рассматривать как цветные варианты, поскольку сообщение с уже установленным на нем диском принимает соответствующий цвет диска (это означает, что на столб может быть помещен только диск того же цвета, обращенный вверх. ).

Например, в бесплатном п = 3 MToH, описанная выше, после 5 ходов достигается промежуточное состояние, когда большой диск находится на стойке D. С этого момента столб D считается синим, и головоломка становится эквивалентной головоломке «NNB». Если решение известно для п = 2 "NNB", ее можно сразу применить для завершения п = 3 бесплатных головоломки.

Соотношения симметрии

Не все варианты разного цвета представляют собой разные головоломки, поскольку симметрия означает, что некоторые предварительно раскрашенные варианты головоломки идентичны другим. Например, если мы решаем загадку RBB в обратном направлении, то это то же самое, что решать загадку RRB в обычном прямом направлении (примечание: синий и красный цвета поменялись местами, чтобы сохранить правило, что в начале головоломки все диски должны быть на исходном посте красной стороной вверх). Таким образом, головоломки RBB и RRB образуют симметрия обращения времени пара. Это означает, что они имеют одинаковые характеристики в отношении количества требуемых оптимальных ходов, даже несмотря на то, что каждая головоломка требует отдельного алгоритма для ее решения. Фактически, ниже будет показано, что головоломки, образующие пару симметрии обращения времени, взаимозависимы друг от друга в том смысле, что алгоритм решения одной использует алгоритм решения другой.

Решения

Как и в случае с классической головоломкой ToH, одним из самых простых и поучительных методов решения MToH является использование рекурсивные алгоритмы. Такие алгоритмы представлены ниже для выбранных вариантов головоломки и доказана оптимальность решений. Используя эти алгоритмы, можно получить рекурсивные соотношения и впоследствии выражения в замкнутой форме для общего количества ходов, необходимых для решения головоломки, и количества ходов, которые каждый диск делает во время решения.

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

Рекурсивные алгоритмы решения и доказательство их оптимальности

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

Напротив, решения для полуцветных вариантов (где один или несколько постов нейтральны) и полностью свободного варианта решаются с помощью более сложных рекурсивных соотношений. Головоломки RBB (n) и RRB (n) могут быть решены с помощью следующей пары оптимальных алгоритмов:

Для RBB (n):

• Переместите п - 1 наименьший диск от S до I с использованием RBB (п - 1) алгоритм
• Переместите диск 1 из S в D
• Двигаться п - 1 диск от I до S с использованием RRB (п - 1) алгоритм
• Двигаться п - 1 диск от S до D с использованием RBB (п - 1) алгоритм

Для RRB (n):

• Переместите п - 1 наименьший диск от S до D с использованием RRB (п - 1) алгоритм
• Двигаться п - 1 диск из D в I с использованием RBB (п - 1) алгоритм
• Переместите диск 1 из S в D
• Двигаться п - 1 диск от I до D с использованием RRB (п - 1) алгоритм

Оптимальность этой пары алгоритмов доказана с помощью индукция, следующим образом (это доказательство также является подробным объяснением алгоритмов):

За п = 1 очевидно, что алгоритмы оптимальны, так как ход всего один. Далее предполагается, что алгоритмы оптимальны для п - 1, и с использованием этого предположения показано, что они оптимальны дляп.

Начиная с RBB (п), ясно, что перед тем, как диск 1 можно будет разместить на посте D, он должен сначала быть на посте S (который является единственным постом, окрашенным в красный цвет), а остальные диски должны быть на посте I. Таким образом, решение должно пройти через это промежуточное состояние, и, по предположению, оптимальным способом достижения этого промежуточного состояния является использование RBB (п - 1) алгоритм с постами D и I поменялся местами.

Затем диск 1 нужно переместить из S в D, поскольку он должен быть перемещен хотя бы один раз.

Далее показано, что из этого состояния окончательное решение может быть достигнуто только через промежуточное состояние, в котором все п - На посту S стоит 1 диск. Чтобы диск 2 был размещен на столбике D, он должен сначала быть на столбике S (единственный красный столбец), а другой п - На I посте должно быть 2 диска. Однако, прежде чем диск 3 можно будет разместить в столбце I, он должен сначала оказаться на столбце S наверху диска 2. Это рассуждение может пройти по всем дискам, каждый из которых должен сначала быть на столбце S, прежде чем переходить к Я публикую, таким образом показывая, что решение должно пройти через промежуточное состояние, в котором все п - 1 диск стоит на посту S.

Для достижения этого промежуточного состояния необходимо использовать оптимальный алгоритм, который передает п - 1 диск из сообщения Blue I в сообщение Red S через сообщение Blue D, т.е. оптимальный BBR (п - 1) алгоритм, который эквивалентен RRB (п - 1) алгоритм (цвета просто меняются местами).

Наконец, необходимо перенести п - 1 наименьший диск из поста S в пост D через пост I. Это, конечно, просто БОР (п - 1) алгоритм.

Аналогичные рассуждения можно применить, чтобы показать, что алгоритм RRB (n), описанный выше, является оптимальным. Также можно написать алгоритмы решения и доказать их оптимальность для других пар задач с обращением времени, а именно:

• Пара RBN и NRB
• Пара РНБ и БНР
• Пара RNN и NNB

Эти алгоритмы, как правило, более сложные и используют полностью окрашенные алгоритмы RBB и RRB, описанные выше. Полную информацию об этих алгоритмах и доказательства их оптимальности можно найти в.^[7]

В заключение этого раздела приводится алгоритм решения полностью бесплатной головоломки NNN. Доказательство оптимальности также можно найти в.^[7]

• Переместите самое маленькое п - 1 диск от S к I через D, используя RNN (п - 1) алгоритм
• Переместите диск 1 из S в D.
• Переместите самое маленькое п - 2 диска от I до S через D, используя RRB (п - 2) алгоритм (который эквивалентен алгоритму BBR (n-2))
• Переместите самое маленькое п - 2 диска от S к D через I, используя RBB (п - 2) алгоритм
• Переместите диск 2 из I в S
• Переместите самое маленькое п - 2 диска с D на I через S, используя RBN (п - 2) алгоритм (эквивалентный BRN (п - 2) алгоритм)
• Переместите диск 2 из S в D
• Переместите самое маленькое п - 2 диска от I до D через S, используя алгоритм NNB

Отношения рекуррентности и их решения

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

Обозначив общее количество ходов, сделанных оптимальными алгоритмами головоломок RBB и RRB как ${\displaystyle S_{RBB}(n)}$ и ${\displaystyle S_{RRB}(n)}$, то обращаясь к алгоритму решения, указанному выше, легко показать, что выполняется следующее рекуррентное соотношение:

${\displaystyle S_{RBB}(n+1)=2S_{RBB}(n)+S_{RRB}(n)+1=3S_{RBB}(n)+1}$

где использовался тот факт, что загадки RBB и RRB образуют пару симметрии обращения времени, и, таким образом, ${\displaystyle S_{RBB}(n)=S_{RRB}(n)}$.

Также можно указать рекурсивное соотношение для общего числа ходов, сделанных диском k, которое мы обозначим через ${\displaystyle P_{RBB}(k)}$ и ${\displaystyle P_{RRB}(k)}$ для алгоритмов RBB и RRB соответственно (обратите внимание, что ${\displaystyle P(k)}$ не зависит от общего количества дисков п в головоломке). Снова прорабатывая алгоритмы и используя равенство ${\displaystyle P_{RBB}(k)=P_{RRB}(k)}$, несложно показать, что

${\displaystyle P_{RBB}(k+1)=2P_{RBB}(k)+P_{RRB}(k)=3P_{RBB}(k)}$

Из этих рекурсивных соотношений довольно просто вывести выражения в замкнутой форме для ${\displaystyle S_{RBB}(n)}$ и ${\displaystyle P_{RBB}(k)}$, которые даются

${\displaystyle S_{RBB}(n)=S_{RRB}(n)={\tfrac {1}{2}}3^{n}-{\tfrac {1}{2}}}$

${\displaystyle P_{RBB}(k)=P_{RRB}(k)=3^{k-1}}$

Как видно, эти величины масштабируются как 3^п, в отличие от классической головоломки ToH, которая масштабируется как 2^п. Фактически, как показано на^[7] все варианты загадки MToH удовлетворяют асимптотическим соотношениям

${\displaystyle \lim _{n\to \infty }S(n)=s3^{n}}$

${\displaystyle \lim _{k\to \infty }P(k)=p3^{k-1}}$

с факторами s, п приведено в следующей таблице:

Варианты пазлов	s	п
RRB / RBB	1/2	1
РБН / НРБ	5/11	10/11
РНБ	4/11	8/11
РНН / ННБ	7/22	14/22
NNN	10/33	20/33

Наконец, пока целочисленные последовательности генерируется выражением для ${\displaystyle S_{RRB}(n)}$ и ${\displaystyle P_{RRB}(k)}$ хорошо известны и перечислены в онлайн-энциклопедии целочисленных последовательностей (OEIS),^[8] Целочисленные последовательности, генерируемые другими вариантами головоломки, гораздо менее тривиальны и не были обнаружены в OEIS до анализа MToH. Все эти новые последовательности, всего 15, теперь перечислены.

Решение марковского типа

Мощный метод анализа головоломки MToH (и других подобных головоломок), предложенный Фредом Ланноном и представленный в его обзоре вариантов головоломок Tower,^[4] матричный метод.

В этом методе не делается попыток разделить различные головоломки на независимые группы, алгоритмы решения которых зависят только друг от друга. Вместо этого алгоритмы решения написаны самым прямым образом, так что алгоритмы всех вариантов головоломки взаимозависимы. Как только это будет сделано, общее количество ходов ${\displaystyle S_{SID}(n)}$ (S, I, D равны R, B, N) для каждого варианта головоломки можно записать следующим образом:

${\displaystyle S_{NNN(n)}=S_{RNN(n-1)}+1+S_{NNR(n-1)}}$

${\displaystyle S_{RNN(n)}=S_{RNN(n-1)}+1+S_{NBR(n-1)}}$

${\displaystyle S_{NNR(n)}=2\cdot S_{RRB(n-1)}+1+S_{RBN(n-1)}+1+S_{RNN(n-1)}}$

${\displaystyle S_{NBR(n)}=2\cdot S_{RRB(n-1)}+1+S_{RBN(n-1)}+1+S_{RBN(n-1)}}$

${\displaystyle S_{RNB(n)}=S_{RBN(n-1)}+1+S_{NBR(n-1)}}$

${\displaystyle S_{RBN(n)}=S_{RNB(n-1)}+2\cdot S_{RRB(n-1)}+1}$

${\displaystyle S_{RRB(n)}=2\cdot S_{RRB(n-1)}+1+S_{RRB(n-1)}}$

Обратите внимание, что в отличие от других вариантов и общего правила, варианты MToH NNR и NBR заканчиваются красными сторонами дисков вверх. Это естественное следствие того, что пункт назначения окрашен в красный цвет.

Если мы теперь определим вектор

${\displaystyle {\vec {S}}(n)={\begin{bmatrix}S_{NNN}(n)\\S_{RNN}(n)\\S_{NNR}(n)\\S_{NBR}(n)\\S_{RNB}(n)\\S_{RBN}(n)\\S_{RRB}(n)\\1\end{bmatrix}}}$

потом

${\displaystyle {\vec {S}}(1)={\begin{bmatrix}1\\1\\2\\2\\1\\1\\1\\1\end{bmatrix}},}$

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

${\displaystyle {\vec {S}}(n)=M{\vec {S}}(n-1),}$

где матрица Маркова ${\displaystyle M}$ определяется

Количество ходов, необходимое для оптимального решения различных вариантов головоломки MToH.

${\displaystyle M\equiv {\begin{bmatrix}0&1&1&0&0&0&0&1\\0&1&0&1&0&0&0&1\\0&1&0&0&0&1&2&2\\0&0&0&0&0&2&2&2\\0&0&0&1&0&1&0&1\\0&0&0&0&1&0&2&1\\0&0&0&0&0&0&3&1\\0&0&0&0&0&0&0&1\end{bmatrix}}}$

Уравнение для ${\displaystyle {\vec {S}}(n)}$ теперь можно записать как

${\displaystyle {\vec {S}}(n)=M^{n-1}{\vec {S}}(1).}$

В характеристический многочлен из ${\displaystyle M}$ дан кем-то

${\displaystyle (K-3)(K^{3}-K-2)(K-1)^{2}K^{2},}$

имеющий следующие восемь корней

${\displaystyle {K_{1},\dots ,K_{8}}={3,1.52183,-0.7607+0.8579i,-0.7607-0.8579i,1,1,0,0},}$

и восемь собственных векторов ${\displaystyle {\vec {\xi }}_{j}}$ такой, что

${\displaystyle M{\vec {\xi }}_{j}=K_{j}{\vec {\xi }}_{j}.}$

Теперь мы можем выразить ${\displaystyle {\vec {S}}(1)}$ используя восемь собственных векторов

${\displaystyle {\vec {S}}(1)=\sum _{j=1}^{8}b_{j}K_{j}{\vec {\xi }}_{j},}$

так что

${\displaystyle {\vec {S}}(n)=\sum _{j=1}^{8}b_{j}K_{j}^{n}{\vec {\xi }}_{j}.}$

Теперь, поскольку ${\displaystyle |K_{1}|>|K_{j}|}$ для всех ${\displaystyle j>1}$, ясно, что

${\displaystyle \lim _{n\to \infty }{\vec {S}}(n)=b_{1}K_{1}^{n}{\vec {\xi }}_{1}=b_{1}3^{n}{\vec {\xi }}_{1}.}$

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

${\displaystyle \lim _{n\to \infty }S_{SID}(n)=s3^{n}}$

с фактором s приведено в следующей таблице:

Вариация головоломки	s
NNN	20/66
RNN	21/66
NNR	39/66
NBR	42/66
РНБ	24/66
RBN	30/66
РРК	33/66

Рекомендации

1. Леви, Ури (2010). "Магнитная башня Ханоя". arXiv:1003.0225 [math.CO ].
2. "Ханойская башня, трудный путь". Это еще один вариант ToH, который относится к основанию 3..
3. Р.Л. Грэм; D.E. Кнут и О. Паташник (1989). Конкретная математика. Аддиссон Уэсли. п. 17.
4. Ланнон, Фред. «Ханойская башня и вариации». Архивировано из оригинал на 2013-09-05. Получено 2013-01-25.
5. Кутрофелло, Том (2010). «Ханойская башня и другие рекурсивные головоломки». Игры (Ноябрь 2010 г.).
6. Леви, Ури (2010). "Магнитная башня Ханоя". Журнал развлекательной математики. 35 (3): 173.
7. Леви, Ури (2010). «Магнитные башни Ханоя и их оптимальные решения». arXiv:1011.3843 [math.CO ].
8. "Он-лайн энциклопедия целочисленных последовательностей (OEIS)".