math.it
sinistra
destra
LE TORRI DI HANOI: la storia

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 è 2n - 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.

 


Altre risorse sul WEB

Numerit: Towers of Hanoi
The JavaScript Source: Games: Towers of Hanoi
Towers of Hanoi

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 dimostrarela validità di una proprietà in un numero infinito di casi.

Potremmo scrivere così il suo enunciato:
Se una proprietà Pn vale per n=1 e se dalla validità di Pn si può dedurre quella di Pn+1, allora Pn 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 2n–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 2n–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 2n–1 mosse; poi si sposta il disco grande (1 mossa) e quindi ancora gli n piccoli (2n–1 mosse). In totale 2n–1+1+2n–1 mosse, cioè 2×2n–1=2n+1–1 mosse.
In conclusione, se per spostare n dischi ci vogliono 2n–1 mosse, per n+1 dischi ne occorrono 2n+1–1. Si può dunque applicare il principio di induzione, e concludere la dimostrazione.

Ad esempio, per spostare 64 dischi occorrono 264–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 ?


Valid XHTML 1.0 Transitional