Ördöglakat

Kétkezi logikai játékok a könnyűtől a szinte lehetetlenig.

Friss topikok

Kétszínű Hanoi

2013.04.21. 20:40 Gál Péter F.

Egy jó játék sokakat inspirál továbbgondolásra. Nehezebb változatok vagy épp könnyebbek jelennek meg, kicsi vagy nagy átalakításokkal új, érdekes mutánsok születnek. A Hanoi torony is ilyen játék, sok játéktervező fantáziáját mozgatta meg.

Az egyik érdekes ötlet kétféle színű korongok használata:

BiHanoi_Alap.jpg

A szabályok ugyanazok, mint a klasszikus Hanoi toronynál megismertek:

1. Mindig csak valamelyik torony legfelső korongját szabad áthelyezni egy másik pálcára.
2. Nem szabad kisebb korongra nagyobbat tenni.
A cél azonos színű korongokból álló tornyok kialakítása. A két legalsó elemet is át kell helyezni másik pálcára! Egy helyes végállapot látható a következő képen:

BiHanoi_Cel.jpg

Kicsit még nehezebb a játék, ha azt kötjük ki, hogy a két legnagyobb elem cseréljen helyet, és azokon alakuljanak ki a tornyok.
Talán a képeken is látható, hogy a két torony azonos méretű korongokból áll. Felmerül a kérdés, hogy szabad-e egymásra helyezni két különböző színű, de azonos átmérőjű korongot. Nos, ez megállapodás kérdése. Az elterjedtebb változat szerint két azonos méretű koron egymásra helyezhető. Ez a szabály eredményezi a legérdekesebb játékot (és a fentebb ismertetett alapszabályoknak is ez felel meg).
Helyesek tehát a következő képeken látható elrendezések:

BiHanoi_JoLepes2.jpg

Vagy:

BiHanoi_KoztesAllapot.jpg

A klasszikus Hanoi tornyoknál volt szó a megoldáshoz szükséges és elégséges lépésszámról. Ott megállapítottuk, hogy n korong áthelyezéséhez 2n-1 lépésre van szükség. A 4 emeletes kétszínű Hanoi tornyaiban összesen 8 korong játszik. Ebből könnyen következik, hogy ezt a játékot 28-1=255 lépéssel biztosan meg lehet oldani. De vajon tényleg kell-e ennyi hozzá?
Ha kipróbálja az olvasó, biztosan rájön, hogy 255-nél sokkal kevesebb lépés is elegendő!
Mennyi az a minimális lépésszám, amivel a 4 emeletes feladvány megoldható? Mennyi akkor, ha a két legnagyobb korong helyet cserél és mennyi akkor, ha nem kötjük ki a helycserét, csak azt, hogy másik pálcára kerüljenek?
És mennyi lépés szükséges 5-6 emeletes kétszínű tornyokhoz?
Az általános esetre a válasz (ha jól tudom) nem ismert. Tehát ma senki sem tudja, hogy egy n emeletes kétszínű tornyot mennyi lépésben lehet megoldani. Léteznek ügyes algoritmusok, amik hatékonyan megoldják a feladatot, de senkinek sem sikerült bizonyítani, hogy megtalálta a lehető legkevesebb lépésből álló megoldást!
Ugye, milyen érdekes? Egy pici változtatással, néhány korong átszínezésével, egy jól kitárgyalt, nem túl nehéz játékból egy nagyon-nagyon komoly probléma tud születni.
Örömmel veszem az olvasók minden észrevételét, megjegyzését, információját e játékkal (is) kapcsolatban. Még jobban örülnék, ha megpróbálnátok minél jobb lépéssorozatokat találni!

Szólj hozzá!

A bejegyzés trackback címe:

https://ordoglakat.blog.hu/api/trackback/id/tr15238035

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.
süti beállítások módosítása