Valahol megtalálható a rendes bizonyítása a Hanoi tornyoknak?

A Hanoi torony megoldásához legalább 2^n - 1 lépés szükséges (ahol n a korongok száma).

Bizonyítás (n szerinti teljes indukcióval):

n = 1 esetben legalább 2^1 - 1 = 2 - 1 = 1 lépésre van szükségünk. Ez igaz, mivel a balszélső rúdról azt az egy korongot át kell raknunk a jobbszélsőre, ami nem történhet meg 0 lépésben.

Tegyük fel, hogy tetszőleges (n-1)-re igaz az állítás. Azt kell igazolnunk, hogy ekkor igaz n-re is.

A szabályok alapján egyszerre csak egy korongot mozgathatunk, valamint nagyobb korong nem kerülhet kisebb fölé. Ez azt jelenti, hogy a legnagyobb korong csak legalul lehet, és csak úgy tudjuk elmozgatni, hogy amelyik rúdról mozgatjuk, csak ez a korong van, és ahova tesszük nincs korong. Mivel három rúd van, ebből következik, hogy a legnagyobb mozgatásakor az összes többi korong egy rúdon van.

A lépésszám szempontjából lényegtelen, hogy melyik rúdról melyik rúdra pakolunk, ugyanis a rudak szerepét felcserélve az eredeti problémához jutunk.

Tetszőleges n számú korongot szétválaszthatunk úgy, hogy vesszük a legnagyobbat és az összes többi n - 1 darabot.

Ahhoz, hogy a legnagyobb korongot elmozgathassuk, az indukciós feltevésünk szerint legalább 2^(n-1) - 1 lépésre szükségünk van, mert az n-1 korongot le kell venni róla. Ugyanígy ha a legnagyobb korongon nincs másik, ahhoz hogy a többit rárakhassuk szintén 2^(n-1) - 1 számú lépés kell. Ugyanakkor a legnagyobb korongot is mozgatnunk kell, ami legalább 1 lépés. Ez összesen legalább

[2^(n-1) -1] + [2^(n-1) -1] + 1 =

2^(n-1) -1 + 2^(n-1) -1 + 1 =

2^(n-1) + 2^(n-1) -1 =

2*2^(n-1) -1 =

2^n - 1

lépés. Éppen ezt kellett bizonyítani.