Le torri di Hanoi: storia

La leggenda

Il problema delle Torri di Hanoi deriva da una antica leggenda indiana che recita così: «nel grande tempio di Brahma a Benares, su di un piatto di ottone, sotto la cupola che segna il centro del mondo, si trovano 64 dischi d'oro puro che i monaci spostano uno alla volta infilandoli in un ago di diamanti, seguendo l'immutabile legge di Brahma: nessun disco può essere posato su un altro più piccolo. All'inizio del mondo tutti i 64 dischi erano infilati in un ago e formavano la Torre di Brahma. Il processo di spostamento dei dischi da un ago all'altro è tuttora in corso. Quando l'ultimo disco sarà finalmente piazzato a formare di nuovo la Torre di Brahma in un ago diverso, allora arriverà la fine del mondo e tutto si trasformerà in polvere.»

Non ti preoccupare useremo al massimo 7 dischi e non 64 !

torri di Hanoi: il giocoIl gioco interattivo si presenta costituito da tre aste, in una delle quali sono infilati alcuni dischi di misura diversa, disposti in ordine di grandezza, partendo dal basso, dal più grande al più piccolo.
Le regole del gioco sono due e molto semplici: (1) si può spostare solo il disco situato sulla sommità di una torre, e (2) un disco più grande non può essere posato sopra un disco più piccolo.
Lo scopo è quello di spostare tutti i dischi su un'altra asta in modo che risultino ancora disposti nello stesso ordine.

Ogni disco, una volta portato su un'asta, è calamitato e quando viene rilasciato è attratto verso la base se la mossa è corretta altrimenti torna automaticamente al posto da dove è stato prelevato.

Il numero minimo di mosse previsto per la soluzione del gioco è indicato sempre per tutti i livelli. In generale se i dischi sono `n` il numero minimo di mosse è `2^n-1`.
Su tutti e 5 i livelli è evidenziato il numero di mosse eseguite sino a quel momento. Il gioco è stato limitato all'utilizzo di 3 dischi nel primo livello, fino a 7 dischi nel quinto livello.


Le torri di Hanoi e il principio di induzione

Il principio di induzione è un potente strumento di dimostrazione, al quale si ricorre ogni volta che si debba dimostrare la validità di una proprietà in un numero infinito di casi.

Potremmo scrivere così il suo enunciato:
Se una proprietà `P_n` vale per `n=1` e se dalla validità di `P_n` si può dedurre quella di `P_(n+1)`, allora `P_n` vale per ogni intero `n`.

Un buon modo per introdurre il principio di induzione è il gioco delle Torri di Hanoi.

Ci chiediamo: è sempre possibile effettuare uno spostamento, qualunque sia il numero dei dischi?.
La risposta è sì. Ragioniamo in questo modo:
Supponiamo di saper spostare, in accordo con le regole del gioco, una configurazione di quattro dischi. Se ora dobbiamo spostare cinque dischi ci comporteremo così: (1) cominciamo a spostare i quattro dischi, infilati inizialmente sul piolo di sinistra, senza muovere mai il più grande alla base che non ci dà fastidio perché essendo il più grande di tutti è come se non ci fosse, (2) A questo punto avremo i quattro dischi infilati in uno degli altri pioli, facciamo in quello di destra. Allora liberiamo il disco più grande e muoviamolo sul piolo centrale; (3) ora possiamo riportare eseguendo i passaggi di prima i quattro dischi sul piolo centrale.
Quello che abbiamo fatto per quattro dischi, l'abbiamo ripetuto per cinque dischi, dunque saremo in grado di ripeterlo anche per sei dischi. Procedendo per induzione possiamo rifarlo per un qualsiasi altro numero di dischi.

In definitiva possiamo dire che se è possibile spostare un certo numero di dischi, è anche possibile spostarne uno di più.

Ora dovremmo chiederci: siamo sicuri di coprire tutti i numeri? Se i dischi da spostare sono 47, sposteremo un disco, poi due, poi tre, ... dopo un po' di tempo si giungerà al disco quarantasette. Ma se dovessimo spostarne un numero un po’ più grande, diciamo 52698752145698523245874? Riusciamo a contare fino a raggiungerlo? E' il principio di induzione che ce lo conferma: contando un numero dopo l’altro raggiungiamo tutti i numeri senza eccezione. Di conseguenza, possiamo spostare quanti dischi vogliamo.

Bisogna avere un po' di tempo libero, perché per spostare n dischi da un piolo ad un altro occorrono `2^n-1` mosse.

Anche questo si può dimostrare per induzione.
Infatti è vero per `n=1` (per spostare un disco basta una mossa).
Supponiamo ora che per `n` dischi ci vogliano `2^n-1` mosse. Quante ce ne vorranno per spostarne `n+1`?
Bisognerà spostare prima gli `n` dischi piccoli lasciando stare il più grande, e per questo occorrono `2^n-1` mosse; poi si sposta il disco grande (1 mossa) e quindi ancora gli `n` piccoli (`2^n-1` mosse). In totale `2^n -1+1+2^n-1` mosse, cioè `2 xx 2^n-1 = 2^n+1` mosse.
In conclusione, se per spostare `n` dischi ci vogliono `2^n-1` mosse, per `n+1` dischi ne occorrono `2^(n+1)-1`. Si può dunque applicare il principio di induzione, e concludere la dimostrazione.

Ad esempio, per spostare 64 dischi occorrono `2^64-1` mosse, cioè 18.446.744.073.709.551.615 mosse.
Eseguendo una mossa al secondo, ci vogliono 584.546.491.649 anni, 58 giorni, 14 ore, 56 minuti e 15 secondi.

... ma quanto è grande il numero 2 alla 64 ?

Vai al gioco delle Torri di Hanoi