(*) Kolejny słupek wyznaczamy w zależności od liczby krążków. Jeśli liczba krążków jest parzysta, kolejnym słupkiem jest ten po prawej stronie (gdy dojdziemy do słupka C w następnym ruchu używamy słupka A). Natomiast jeśli liczba krążków jest nieparzysta, kolejnym słupkiem jest ten po lewej stronie (gdy dojdziemy do słupka A w następnym ruchu używamy słupka C).
Najmniejsza liczba wymaganych ruchów Równanie określające liczbę ruchów potrzebnych do rozwiązania problemu wież Hanoi dla krążków:
Dowód Łatwo pokazać, że w pierwszym kroku przekładamy krążków na jeden słupek (bez straty ogólności załóżmy, że jest to krążek nr 3) – wymaga to co najmniej ruchów przekładamy -ty krążek na drugi słupek – wymaga to jednego ruchu przekładamy pozostałe krążki ze słupka 3. na -ty krążek leżący na 2. słupku – wymaga to co najmniej ruchów
a więc
Aby wykazać, że można przeprowadzić poniższe rozumowanie.
Aby móc ruszyć -ty krążek, trzeba najpierw zdjąć wszystkie leżące na nim krążki, tak by po ich zdjęciu jeden ze słupków pozostał wolny (aby na jego „dno” mógł trafić -ty krążek). A więc ze słupka 1 przekładamy krążki na słupek 3.