Магнитная башня Ханоя

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решения

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

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

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

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

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

Для БББ(n):

Переместите n - 1 наименьших дисков из S в I, используя алгоритм RBB ( n - 1).
Переместите диск 1 из S в D.
Переместите n - 1 дисков из I в S, используя алгоритм RRB( n - 1).
Переместите n - 1 дисков из S в D, используя алгоритм RBB( n - 1).

Для RRB(n):

Переместите n - 1 наименьших дисков из S в D, используя алгоритм RRB( n - 1).
Переместите n - 1 дисков из D в I, используя алгоритм RBB( n - 1).
Переместите диск 1 из S в D.
Переместите n - 1 дисков из I в D, используя алгоритм RRB( n - 1).

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

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

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

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

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

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

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

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

Пара РБН и НРБ
Пара РНБ и БНР
Пара RNN и NNB

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

с коэффициентами s , p, указанными в следующей таблице:

Варианты головоломок	с	п
РРБ / РББ	1/2	1
РБН/НРБ	5/11	10/11
РНБ	4/11	8/11
РНН/ННБ	7/22	14/22
ННН	10/33	20/33

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

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

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

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

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

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

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

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

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

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

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

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

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

{\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}}

Затем

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

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

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

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

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}}

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

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

Характеристический полином $M$ дается

(K-3)(K^{3}-K-2)(K-1)^{2}K^{2},

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

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

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

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

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

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

так что

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

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

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

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

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

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

Вариант головоломки	с
ННН	20/66
РНН	21/66
ННР	39/66
НБР	42/66
РНБ	24/66
РБН	30/66
РРБ	33/66

Ссылки

^ Jump up to: ^а ^б Леви, Ури (2010). «Магнитная башня Ханоя». arXiv : 1003.0225 [ math.CO ].
^ «Ханойская башня, трудный путь» . Это еще один вариант ToH, относящийся к основанию 3 .
^ Р.Л. Грэм; Д. Е. Кнут и О. Паташник (1989). Конкретная математика . Аддиссон Уэсли. п. 17.
^ Jump up to: ^а ^б Ланнон, Фред. «Ханойская башня и вариации» . Архивировано из оригинала 5 сентября 2013 г. Проверено 25 января 2013 г.
^ Кутрофелло, Том (2010). «Ханойская башня и другие рекурсивные головоломки». Игры (ноябрь 2010 г.).
^ Леви, Ури (2010). «Магнитная башня Ханоя». Журнал развлекательной математики . 35 (3): 173.
^ Jump up to: ^а ^б ^с ^д Леви, Ури (2010). «Магнитные башни Ханоя и их оптимальные решения». arXiv : 1011.3843 [ math.CO ].
^ «Онлайн-энциклопедия целочисленных последовательностей (ОЭИС)» .

[Levy2-1] Jump up to: ^а ^б Леви, Ури (2010). «Магнитная башня Ханоя». arXiv : 1003.0225 [ math.CO ].

[2] «Ханойская башня, трудный путь» . Это еще один вариант ToH, относящийся к основанию 3 .

[3] Р.Л. Грэм; Д. Е. Кнут и О. Паташник (1989). Конкретная математика . Аддиссон Уэсли. п. 17.

[Lunnon-4] Jump up to: ^а ^б Ланнон, Фред. «Ханойская башня и вариации» . Архивировано из оригинала 5 сентября 2013 г. Проверено 25 января 2013 г.

[5] Кутрофелло, Том (2010). «Ханойская башня и другие рекурсивные головоломки». Игры (ноябрь 2010 г.).

[Levy1-6] Леви, Ури (2010). «Магнитная башня Ханоя». Журнал развлекательной математики . 35 (3): 173.

[Levy3-7] Jump up to: ^а ^б ^с ^д Леви, Ури (2010). «Магнитные башни Ханоя и их оптимальные решения». arXiv : 1011.3843 [ math.CO ].

[OEIS-8] «Онлайн-энциклопедия целочисленных последовательностей (ОЭИС)» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]