Salve. La mia domanda riguarda la Torre di Hanoi. Tutti sanno che il numero minimo di mosse necessarie per completare il gioco è 2n-1, dove n è il numero di dischi. Ma perché? C’è una spiegazione intuitiva per questo fatto? Grazie.

La torre di Hanoi è un celebre gioco da tavolo a giocatore singolo inventato dal matematico francese E. Lucas nel 1883. Questo gioco è basato su poche regole molto facili. Facendo riferimento alla figura di sotto la situazione iniziale del gioco prevede tre aste verticali delle quali quella posta a sinistra è riempita con una serie di anelli infilati uno sopra l’altro. Lo scopo del gioco è quello di trasferire l’intera serie di anelli sull’asta centrale sfruttando la terza asticella a destra, ma seguendo le regole:

1) si può spostare solo un anello per volta;
2) se un anello si appoggia sopra un altro, allora deve sempre appoggiarsi sopra un anello di diametro maggiore.

L’unica cosa matematicamente interessante di questo gioco è quella di capire qual è il numero minimo di mosse da fare per completarlo. Cominciamo col capire come giocare con un numero basso di anelli. Per esempio, se la torre è costituita da 1 anello solo basta infilare tale anello nell’asta centrale per completare il gioco, e quindi basta una mossa, e di meglio ovviamente non si può fare. Prendiamo ora una torre data da 2 anelli; allora dovendo spostarne uno alla volta la prima mossa consiste necessariamente nel togliere l’anello più piccolo, che sta al vertice della torre; questo lo infiliamo nell’asta di destra. Poi prendiamo l’anello di base a sinistra e lo infiliamo al centro, e quindi l’anello piccolo sopra quello di base: totale, 3 mosse sembrano essere necessarie. Analizziamo la situazione con 3 anelli, ed elenchiamo le mosse da seguire, numerando gli anelli da 1 a 3, essendo 1 l’anello alla base, 2 l’intermedio e 3 quello di sopra.
1 mossa: sposto l’anello 3 al centro;
2 mossa: sposto l’anello 2 a destra;
3 mossa: sposto l’anello 3 a destra;
4 mossa: sposto l’anello 1 al centro;
5 mossa: sposto l’anello 3 a sinistra;
6 mossa: sposto l’anello 2 al centro;
7 mossa: sposto l’anello 3 al centro.
Se uno fa un po’ di prove si convince che meno di 7 mosse non riesce a fare: sembra dunque che 7 sia la soluzione nel caso di 3 anelli. Con un po’ di pazienza si può vedere che con 4 anelli servono 15 mosse. Cosa lega il numero di anelli al numero di mosse? Abbiamo dedotto la seguente corrispondenza: 1-1, 2-3, 3-7, 4-15. Se n è il numero di anelli il numero di mosse sembra avere la forma 2n-1, ed infatti così è. Questo fatto si può dimostrare per induzione su n: ovvero basta mostrare che è vero per n=1 e poi dimostrare che se è vero per n allora è vero per n+1. Per n=1 il risultato è vero, dal momento che con un anello serve una mossa sola, che è 21-1, e di meglio non si può fare. Dunque la congettura vale per n=1. L’idea per dimostrare ora che se la congettura vale per n anelli allora per n+1 anelli può essere trovata, per esempio, osservando come abbiamo descritto le mosse nei casi 2 e 3 anelli, che sono due interi consecutivi. Infatti, riprendiamo l’esempio dei 3 anelli; osserviamo che le prima 3 mosse servono per ricostruire a destra una torre di Hanoi con 2 anelli. Ora ci serve una mossa per mettere l’anello 1 al centro, che era la 4 mossa, e dunque per ricostruire una torre con 2 anelli al di sopra dell’anello messo sappiamo che servono altre 3 mosse. In conclusione, per rimontare 3 anelli servono 2·3+1 mosse, infatti 7. Questo ragionamento si ripete tale quale con n+1 anelli, e adesso rendiamo rigorosa l’induzione. Denotiamo con mn il numero minimo di mosse per spostare n anelli. Per ipotesi (detta anche ipotesi induttiva) sappiamo che mn=2n-1; dobbiamo dimostrare che mn+1=2n+1-1. Ora, dalla torre di n+1 anelli, ricostruiamo una torre di n anelli sull’asta a destra, e quindi usando mn mosse; spostiamo quindi l’anello alla base al centro, usando 1 mossa, e quindi rimontiamo una torre di n anelli al centro, usando ancora mn mosse. In totale abbiamo dunque mn+1=2mn+1=2·2n-1=2n+1-1 che è quello che volevamo dimostrare.