Magnetická věž v Hanoji - Magnetic Tower of Hanoi

Puzzle Magnetická věž v Hanoji (MToH)

The Magnetická věž v Hanoji (MToH) puzzle je variace klasiky Hanojská věž skládačka (ToH), kde každý disk má dvě odlišné strany, například s různými barvami „červená“ a „modrá“. Pravidla skládačky MToH jsou stejná jako pravidla původní skládačky s přidanými omezeními, že každý disk se při pohybu převrátí a že dva disky nemusí být umístěny jeden na druhý, pokud mají jejich dotykové strany stejnou barvu . Každý disk má severní a jižní pól, přičemž podobné póly se navzájem odpuzují a protilehlé póly se navzájem přitahují. Magnety uvnitř každého disku fyzicky zabraňují nelegálním pohybům.^[1]

Ilustrace magnetismu: Disky se navzájem magneticky odpuzují, pokud mají jejich dotykové strany stejnou barvu

Jednou z pozoruhodných vlastností klasické ToH hádanky je její vztah k základně 2: minimální počet celkových tahů potřebných k vyřešení hádanky je 2ⁿ - 1 (kde n je počet disků), zatímco minimální počet tahů provedených diskem k je 2^k − 1 (disky jsou očíslovány zdola nahoru, aby k = 1 je největší disk a k = n nejmenší). Níže bude ukázáno, že stejně jako původní ToH skládačka souvisí se základnou 2, tak MToH souvisí se základnou 3, i když složitěji.^[2]

Původ

Matematicky ekvivalentní hádanky k určitým variantám MToH jsou známy již nějakou dobu. Například ekvivalentní hádanka k jednomu z barevné varianty MToH se objeví v Konkrétní matematika.^[3] V tomto hlavolamu jsou tahy povoleny pouze mezi určitými příspěvky, což je ekvivalentní přiřazení stálých barev příspěvkům (např. Pokud mají dva příspěvky přiřazenou stejnou trvalou barvu, pak nejsou přímé pohyby mezi těmito dvěma příspěvky povoleny).

Bezplatný (nebarvený) MToH se poprvé veřejně objevil na internetu^[4] kolem roku 2000 (i když pod názvem „Domino Hanoi“) jako součást podrobného přehledu matematiků Freda Lunnona o různých variantách původní hádanky Tower of Hanoi.

MToH byl samostatně vynalezen fyzikem Uri Levym v létě 1984, který také vytvořil jméno a analogii k magnetismu.^{[je zapotřebí objasnění ][5]} Dr. Levy později publikoval řadu článků ^[1][6][7] zabývající se matematickými aspekty MToH.

Popis hádanky

Počáteční poloha hádanky

Puzzle MToH se skládá ze tří příspěvků označených jako zdroj (S), cíl (D) a meziprodukt (I) a hromada n disky různé velikosti, přičemž každá strana disku má jinou barvu, červenou nebo modrou. Na začátku skládačky jsou disky naskládány na sloupek S v pořadí podle zmenšující se velikosti (tj. Největší disk je dole) a tak, aby všechny disky měly svoji červenou stranu směřující nahoru. Cílem skládačky (v její „základní“ verzi) je přesunout celý stoh, jeden disk po druhém, na sloupek D, udržovat pořadí od největšího po nejmenší disk, ale s modrými stranami nahoru.

Konečná poloha skládačky

Pravidla pro pohyb disků jsou následující:

• Větší disk nelze položit na menší disk (jako v původním ToH)
• Když se disk přesune, otočí se, tj. Barva, která směřovala nahoru, nyní směřuje dolů
• Dvě strany různých disků stejné barvy se nemusí navzájem dotýkat (například disk s modrou stranou dolů nemůže být umístěn na disk, který má modrou stranu nahoru).

Logické řešení pro n = 2 a n = 3

Abychom ilustrovali pravidla MToH a také ukázali cestu k obecnějšímu řešení, je užitečné projít příklady pro n = 2 a n = 3. Pro případ n = 2, jsou vyžadovány čtyři kroky, jak je znázorněno na přiloženém obrázku, ve srovnání se třemi kroky v n = 2 případy původního ToH. Je nutný další krok, protože po druhém kroku nelze malý disk přesunout přímo ze sloupku I na sloupek D, protože by to znamenalo, že jeho modrá strana by směřovala dolů. Je tedy zapotřebí další krok k převrácení barvy malého disku, aby mohl být poté umístěn na sloupek D modrou stranou nahoru.

Řešení n = 2 puzzle

Pro n = 3 případ, řešení zahrnuje následující kroky:

• Číslování disků 1 až 3 od největších po nejmenší, jeden nejprve přesune disky 2 a 3 ze sloupku S na sloupek I (čtyři pohyby)

Tato první fáze je obdobou n = 2 výše popsaná skládačka, která také vyžaduje čtyři tahy, kde jsou zaměněny sloupky D a I. Není však totožný s n = 2 hádanka kvůli přítomnosti velkého disku na sloupku S, který jej „vybarví“ červeně. To znamená, že disk lze na tento sloupek umístit pouze jeho červenou stranou nahoru.

• Přesuňte disk 1 ze S na D (jeden tah)

V této fázi by mohlo být v pokušení znovu použít n = 2 puzzle a zkuste přesunout disky 2 a 3 z I na D ve 4 tazích. Zde je však opět potřeba péče. Vzhledem k přítomnosti disku 1 na D je nyní D „zbarveno“ modře, tzn., Že na něj lze umístit jiný disk, pouze pokud má svou modrou stranu nahoru. Dále s n = 2 puzzle disky mají ve výchozí pozici červenou stranu nahoru, zatímco zde mají modré strany nahoru. Tato přechodná konfigurace tedy není ekvivalentní s n = 2 MToH. Místo toho postupujeme následovně:

• Přesuňte disk 3 z I do D přes S (2 tahy)
• Přesunout disk 2 z I na S (1 tah)
• Přesunout disk 3 z D na I (1 tah)
• Přesunout disk 2 ze S na D (1 tah)
• Přesunout disk 3 z I na D (1 tah)

Řešení tedy vyžaduje celkem 11 kroků. Jak je právě ukázáno, je přirozené pokusit se použít n = 2 řešení řešení částí n = 3 puzzle v a rekurzivní způsobem, který se obvykle používá k řešení klasické ToH hádanky. Na rozdíl od klasického ToH zde však n = 2 řešení nelze slepě aplikovat kvůli zabarvení sloupků a disků. Tento bod ukazuje, že k dosažení obecnějšího řešení pro n-disk MToH puzzle, je nutné vzít v úvahu varianty puzzle, kde jsou sloupky předem vybarvené (buď modré nebo červené). Zvažováním těchto variant je možné vyvinout úplné rekurzivní vztahy pro skládačku MToH, a tak najít obecné řešení.

Barevné varianty skládačky MToH

Barevné varianty „sesterských hádanek“ MToH

Výše uvedený popis skládačky MToH předpokládá, že zatímco samotné disky jsou barevné, příspěvky jsou neutrální. To znamená, že prázdný příspěvek může přijmout disk s červenou nebo modrou stranou nahoru. Tato základní verze MToH se nazývá „bezplatná“ MToH.

Jsou možné i jiné varianty skládačky MToH, přičemž samotné sloupky jsou barevné, jak je znázorněno na přiloženém obrázku. Pokud je sloupek předem zbarvený červeně / modře, mohou být na tento předem zbarvený sloupek umístěny pouze disky s jejich červeno / modrou stranou nahoru. Různé varianty MToH lze pojmenovat pomocí třípísmenného štítku „SID“, kde S, ID odkazují na barvu zdrojových, mezilehlých a cílových příspěvků a mohou nabývat hodnot R (červená), B (modrá) nebo N (neutrál - žádná barva). Puzzle „NNN“ tedy odkazuje na bezplatnou MToH, zatímco puzzle „RBB“ odkazuje na variantu, kde je sloupek S předem zbarven červeně, zatímco sloupky I a D jsou vybarveny modře.

Zatímco varianty MToH jsou samy o sobě hádankami, hrají také klíčovou roli při řešení bezplatného MToH. Jak je vidět výše, přechodné stavy volného MToH lze považovat za barevné variace, protože sloupek, na kterém je již disk, předpokládá odpovídající barvu disku (což znamená, že na sloupek lze umístit pouze disk se stejnou barvou směřující nahoru. ).

Například zdarma n = 3 MToH skládačka popsaná výše, po 5 tazích je dosažen střední stav, kdy je velký disk na D sloupku. Od tohoto okamžiku je sloupek D považován za modře zbarvený a skládačka se stává rovnocennou skládačce „NNB“. Pokud je známé řešení pro n = 2 "NNB" puzzle, to by mohlo být okamžitě použito k dokončení n = 3 puzzle zdarma.

Symetrické vztahy

Ne všechny různé barevné varianty jsou odlišné hádanky, protože symetrie znamená, že některé předbarvené varianty puzzle jsou totožné s ostatními. Například pokud řešíme puzzle RBB dozadu, pak je to stejné jako řešení puzzle RRB v pravidelném směru dopředu (poznámka: modrá a červená barva byly zaměněny, aby se zachovalo pravidlo, že na začátku puzzle jsou všechny disky musí být na zdrojovém sloupku červenou stranou nahoru). Hádanky RBB a RRB tedy tvoří a symetrie obrácení času pár. To znamená, že sdílejí stejné vlastnosti, pokud jde o počet požadovaných optimálních tahů, i když každá hádanka vyžaduje k vyřešení odlišný algoritmus. Ve skutečnosti bude níže ukázáno, že hádanky, které tvoří dvojici symetrie s časovým obrácením, jsou na sobě navzájem závislé, v tom smyslu, že algoritmus řešení jednoho využívá algoritmus řešení druhého.

Řešení

Stejně jako u klasického ToH puzzle je jednou z nejjednodušších a nejvíce poučných metod řešení MToH použití rekurzivní algoritmy. Takové algoritmy jsou uvedeny níže pro vybrané varianty skládačky a je prokázána optimálnost řešení. Pomocí těchto algoritmů lze odvodit rekurzivní vztahy a následně uzavřené výrazy formuláře pro počet celkových tahů potřebných k vyřešení hádanky a počet tahů, které každý disk během řešení provede.

Rekurzivní vztahy lze také prezentovat a analyzovat pomocí a Markov analýza typu, která je také diskutována.

Rekurzivní algoritmy řešení a důkaz jejich optimality

Je poučné nejprve zvážit dvojici časově symetrických hádanek RBB a RRB. Jak se ukázalo, tyto dvě hádanky jsou nejjednodušší k řešení v tom, že jejich rekurzivní algoritmy závisí pouze na jednom, a nikoli na jiných variantách skládačky.

Naproti tomu řešení pro polobarevné varianty (kde jeden nebo více sloupků jsou neutrální) a plně volnou variantu řeší složitější rekurzivní vztahy. RBB (n) a RRB (n) hádanky lze vyřešit pomocí následující dvojice optimálních algoritmů:

Pro RBB (n):

• Přesuňte n - 1 nejmenší disk od S do I pomocí RBB (n - 1) algoritmus
• Přesuňte disk 1 ze S na D
• Hýbat se n - 1 disk z I na S pomocí RRB (n - 1) algoritmus
• Hýbat se n - 1 disk ze S na D pomocí RBB (n - 1) algoritmus

Pro RRB (n):

• Přesuňte n - 1 nejmenší disk od S do D pomocí RRB (n - 1) algoritmus
• Hýbat se n - 1 disk z D na I pomocí RBB (n - 1) algoritmus
• Přesuňte disk 1 ze S na D
• Hýbat se n - 1 disk z I na D pomocí RRB (n - 1) algoritmus

Optimalita této dvojice algoritmů je prokázána pomocí indukce, následovně (tento důkaz také tvoří podrobné vysvětlení algoritmů):

Pro n = 1 je zřejmé, že algoritmy jsou optimální, protože existuje pouze jediný tah. Dále se předpokládá, že algoritmy jsou optimální pro n - 1 a pomocí tohoto předpokladu se ukazuje, že jsou optimální pron.

Počínaje RBB (n), je jasné, že než lze disk 1 umístit na sloupek D, musí být nejprve na sloupku S (což je jediný sloupek označený červeně) a zbytek disků musí být na sloupku I. Řešení tedy musí projít tímto přechodným stavem a podle předpokladu je optimálním způsobem, jak dosáhnout tohoto přechodného stavu, použít RBB (n - 1) algoritmus s D a I příspěvky zaměněn.

Dále musí být disk 1 přesunut z S na D, protože musí být přesunut alespoň jednou.

Dále se ukazuje, že z tohoto stavu lze konečného řešení dosáhnout pouze prostřednictvím přechodného stavu, kde jsou všechny n - 1 disk je na S postu. Aby byl disk 2 umístěn na sloupek D, musí být nejprve na sloupku S (jediný červený sloupek), zatímco druhý n - Na disku I musí být 2 disky. Než však bude možné disk 3 umístit na sloupek I, musí být nejprve na sloupku S v horní části disku 2. Toto uvažování může probíhat přes všechny disky, z nichž každý musí být nejprve na sloupku S, než předá Zveřejňuji příspěvek, což ukazuje, že řešení musí projít přechodným stavem, kde všichni n - 1 disk je na S postu.

K dosažení tohoto přechodného stavu je nutné použít optimální algoritmus, který přenáší n - 1 disk z příspěvku Blue I na příspěvek Red S prostřednictvím příspěvku Blue D, tj. Optimální BBR (n - 1) algoritmus, který je ekvivalentní RRB (n - 1) algoritmus (barvy jsou pouze zaměněny).

Nakonec je nutné převést n - 1 nejmenší disk ze sloupku S na sloupek D prostřednictvím sloupku I. Toto je samozřejmě jen RBB (n - 1) algoritmus.

Podobné úvahy lze použít k prokázání, že výše uvedený algoritmus RRB (n) je optimální. Algoritmy řešení lze také zapsat a dokázat jejich optimálnost pro další dvojice časově reverzních hádanek, jmenovitě:

• Pár RBN a NRB
• Pár RNB a BNR
• Pár RNN a NNB

Tyto algoritmy jsou obecně složitější a využívají plně barevné algoritmy RBB a RRB popsané výše. Veškeré podrobnosti o těchto algoritmech a důkazy jejich optimality naleznete v.^[7]

Na závěr této části je uveden algoritmus řešení zcela zdarma NNN logické hry. Důkaz optimality lze nalézt také v.^[7]

• Přesuňte nejmenší n - 1 disk ze S na I přes D, pomocí RNN (n - 1) algoritmus
• Přesuňte disk 1 ze S do D.
• Přesuňte nejmenší n - 2 disky z I na S přes D, pomocí RRB (n - 2) algoritmus (který je ekvivalentní algoritmu BBR (n-2))
• Přesuňte nejmenší n - 2 disky ze S na D přes I, pomocí RBB (n - 2) algoritmus
• Přesuňte disk 2 z I na S
• Přesuňte nejmenší n - 2 disky z D na I přes S pomocí RBN (n - 2) algoritmus (který je ekvivalentní s BRN (n - 2) algoritmus)
• Přesuňte disk 2 ze S na D
• Přesuňte nejmenší n - 2 disky z I na D přes S pomocí algoritmu NNB

Opakovací vztahy a jejich řešení

Jakmile jsou nalezeny algoritmy řešení, lze je použít k odvození relace opakování pro celkový počet tahů provedených během provádění algoritmu a také pro počet tahů provedených každým diskem.

Označujeme celkový počet tahů provedených optimálními algoritmy hádanek RBB a RRB jako ${ displaystyle S_ {RBB} (n)}$ a ${ displaystyle S_ {RRB} (n)}$, pak s odkazem na výše uvedený algoritmus řešení je snadné ukázat, že platí následující relace opakování:

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

kde se využila skutečnost, že hádanky RBB a RRB tvoří dvojici symetrie obrácení času, a ${ displaystyle S_ {RBB} (n) = S_ {RRB} (n)}$.

Je také možné vypsat relaci rekurze pro celkový počet tahů provedených diskem k, který označujeme ${ displaystyle P_ {RBB} (k)}$ a ${ displaystyle P_ {RRB} (k)}$ pro algoritmy RBB a RRB (všimněte si, že ${ displaystyle P (k)}$ je nezávislý na celkovém počtu disků n v puzzle). Opět práce přes algoritmy a používání rovnosti ${ displaystyle P_ {RBB} (k) = P_ {RRB} (k)}$, je jednoduché to ukázat

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

Z těchto rekurzivních vztahů lze celkem snadno odvodit výrazy uzavřené formy pro ${ displaystyle S_ {RBB} (n)}$ a ${ displaystyle P_ {RBB} (k)}$, které jsou dány

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

Jak je vidět, tato veličina je stupnice 3ⁿ, na rozdíl od klasické ToH skládačky, jejíž měřítko je 2ⁿ. Ve skutečnosti, jak je uvedeno v^[7] všechny varianty skládačky MToH uspokojují asymptotické vztahy

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

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

s faktory s, p dané následující tabulkou:

Nakonec, zatímco celočíselné sekvence generováno výrazem pro ${ displaystyle S_ {RRB} (n)}$ a ${ displaystyle P_ {RRB} (k)}$ jsou dobře známé a jsou uvedeny v Online encyklopedii celočíselných sekvencí (OEIS),^[8] celočíselné sekvence generované jinými variantami logiky jsou mnohem méně triviální a nebyly nalezeny v OEIS před analýzou MToH. Tyto nové sekvence, jejichž počet je 15, jsou nyní uvedeny všechny.

Řešení typu Markov

Výkonná metoda analýzy skládačky MToH (a dalších podobných hádanek), kterou navrhl Fred Lunnon a kterou představil ve svém přehledu variant Tower Puzzles,^[4] je maticová metoda.

V této metodě není vynaloženo žádné úsilí k oddělení různých hádanek do nezávislých skupin, jejichž algoritmy řešení závisí pouze jeden na druhém. Místo toho jsou algoritmy řešení psány nejpříměji, takže algoritmy všech variant hádanek jsou vzájemně závislé. Jakmile to bylo provedeno, celkový počet tahů ${ displaystyle S_ {SID} (n)}$ (S, I, D se rovná R, B, N) pro každou variantu logiky lze zapsat takto:

${ 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)}}$

Všimněte si, že na rozdíl od ostatních variant a obecného pravidla končí varianty MToH NNR a NBR červenými stranami disků směrem nahoru. To je přirozený důsledek toho, že cílový příspěvek je zbarven červeně.

Pokud nyní definujeme vektor

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

Pak

${ displaystyle { vec {S}} (1) = { začátek {bmatrix} 1 1 2 2 1 1 1 1 konec {bmatrix}},}$

a rekurzní vztahy lze zapsat v následující maticové formě

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

kde Markovova matice ${ displaystyle M}$ je definováno

Počet tahů potřebných pro optimální řešení různých variant skládačky MToH

${ Displaystyle M ekv { 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}}}$

Rovnice pro ${ displaystyle { vec {S}} (n)}$ nyní lze psát jako

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

The charakteristický polynom z ${ displaystyle M}$ darováno

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

mající následujících osm kořenů

${ displaystyle {K_ {1}, dots, K_ {8}} = {3,1,52183, -0,7607 + 0,8579i, -0,7607-0,8579i, 1,1,0,0},}$

a osm vlastních vektorů ${ displaystyle { vec { xi}} _ {j}}$ takhle

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

Nyní můžeme vyjádřit ${ displaystyle { vec {S}} (1)}$ pomocí osmi vlastních vektorů

${ displaystyle { vec {S}} (1) = součet _ {j = 1} ^ {8} b_ {j} K_ {j} { vec { xi}} _ {j},}$

aby

${ displaystyle { vec {S}} (n) = součet _ {j = 1} ^ {8} b_ {j} K_ {j} ^ {n} { vec { xi}} _ {j} .}$

Nyní, protože ${ displaystyle | K_ {1} |> | K_ {j} |}$ pro všechny ${ displaystyle j> 1}$, je jasné že

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

Tak jako předtím získáme následující asymptotický vztah pro všechny varianty hádanek

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

s faktorem s dané následující tabulkou:

Reference