La proprietà matematica base è che il numero minimo di mosse necessarie per completare il gioco è
, dove n è il numero di dischi. Ad esempio avendo 3 dischi, il numero di mosse minime è 7. Di conseguenza, secondo la leggenda, i monaci di Hanoi dovrebbero effettuare almeno 18.446.744.073.709.551.615 mosse prima che il mondo finisca, essendo
. In altre parole, anche supponendo che i monaci facciano una mossa al secondo il mondo finirà tra 5.845.580.504 secoli, un tempo così lungo che quando il sole diverrà una gigante rossa e brucerà la Terra, il gioco non sarà stato ancora completato.
La soluzione base del gioco della torre di Hanoi si formula con un algoritmo ricorsivo:
Chiamiamo i paletti con A, B e C, e numeriamo i dischi da 1 (il più piccolo) a n (il più grande).
1. Sposta i primi n-1 dischi da A a B (il disco n resta da solo sul paletto A)
2. Sposta il disco n da A a C
3. Sposta n-1 dischi da B a C
Per spostare n dischi si richiede di compiere un'operazione elementare (spostamento di un singolo disco) ed una complessa, ossia lo spostamento di n-1 dischi. Tuttavia anche questa operazione si risolve nello stesso modo, richiedendo come operazione complessa lo spostamento di n-2 dischi.
Iterando questo ragionamento si riduce il processo complesso ad uno elementare, ovvero lo spostamento di n-(n-1)=1 disco.
È interessante notare che il rompicapo è risolvibile per qualsiasi "n", con una dimostrazione per ricorrenza:
Supponiamo di avere una torre in A composta da N dischi, e supponiamo che N sia il numero massimo di dischi ammessi per risolvere il gioco.
Al termine dello spostamento della torre da A a B, aggiungiamo un ulteriore disco ad A, di grandezza pari a N+1, e ipotizziamo che questo disco sia stato fermo tutto il tempo sotto gli altri.
A questo punto, spostiamo semplicemente il disco da A a C, e certamente riusciremo a spostare la torre da B a C, seguendo gli stessi passaggi che si sono resi necessari per spostarla da A a B.
Avendo dimostrato che una torre di N dischi è spostabile da una colonna all'altra, è dimostrato che si può spostare anche una torre di N+1 dischi.
Riproduzione del coperchio della scatola del puzzle originale.
