A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Tekintsük a Hanoi tornyai néven közismert játék négytornyos változatát: darab különböző méretű korong egymásra van helyezve nagyság szerint sorban úgy, hogy alul van a legnagyobb, felül a legkisebb. A korongokat egy másik helyre kell áthelyezni a következő szabályok betartásával:
‐ Egy lépésben csak egy korongot helyezhetünk át; ‐ Nem tehetünk nagyobb korongot kisebb korongra; ‐ Egyszerre összesen legfeljebb négy tornyot alkothatnak a korongok.
Bizonyítsuk be, hogy a szükséges minimális lépésszám legalább és kisebb, mint .
|