Hanoi

La Torre di Hanoi è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti.

L’oggetto concreto

Narra la leggenda che all'inizio dei tempi, Brahma portò nel grande tempio di Benares, sotto la cupola d'oro che si trova al centro del mondo, tre colonnine di diamante e sessantaquattro dischi d'oro, collocati su una di queste colonnine in ordine decrescente, dal più piccolo in alto, al più grande in basso. E' la sacra Torre di Brahma che vede impegnati, giorno e notte, i sacerdoti del tempio nel trasferimento della torre di dischi dalla prima alla terza colonnina. Essi non devono contravvenire alle regole precise, imposte da Brahma stesso, che richiedono di spostare soltanto un disco alla volta e che non ci sia mai un disco sopra uno più piccolo. Quando i sacerdoti avranno completato il loro lavoro e tutti i dischi saranno riordinati sulla terza colonnina, la torre e il tempio crolleranno e sarà la fine del mondo. 

I monaci della leggenda dovrebbero compiere 18.446.744.073.709.551.615 mosse (264 - 1) per completare il lavoro; supponendo che i monaci facciano una mossa al secondo il mondo finirà tra 5.845.580.504 secoli. 

In realtà si tratta di una leggenda inventata dalla ditta che per prima ha messo in commercio il rompicapo, inventato nel 1883 dal matematico francese Édouard Lucas. 

Questo dilemma è arrivato a noi con il nome di Torre di Hanoi ed è noto come rompicapo matematico. Ancor oggi è un gioco, una sfida, molto intrigante. Non preoccupatevi però, riuscire a risolverlo non causa nessuna fine del mondo ma solo tanta soddisfazione. 

Il gioco inizia con tutti i dischi incolonnati, partendo dal disco più grande, in ordine decrescente di diametro su un piolo, in modo da formare una sorte di piramide.

Lo scopo del gioco è portare tutti dischi su un altro piolo, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.

Siano i pioli etichettati con A, B e C, e i dischi numerati da 1 (il più piccolo) a n (il più grande).

Per comprendere l’algoritmo che porta alla soluzione con il numero minore di mosse conviene cominciare con un disco, poi incrementare progressivamente il numero di dischi. Indicando con n, come già detto, il numero di dischi, con m il numero di mosse e con p la mossa iniziale (questo dato ci aiuta nella procedura risolutiva) si può costruire la seguente tabella:

Il numero minimo di mosse necessarie è dato, ricorsivamente, da m(n) = m(n-1) + 1 + m(n-1) = 2 ∙ m(n-1) + 1.

Il risultato può essere dimostrato usando il calcolo combinatorio. Ad ogni passaggio, si possono spostare un disco dal piolo di partenza a uno dei due pioli rimanenti, ciò significa che ci sono due possibilità per ogni disco. Pertanto, il numero totale di mosse possibili è 2n. Tuttavia, l'obiettivo è di spostare l'intero insieme di dischi sul piolo di arrivo, il che richiede di fare una mossa in meno rispetto al totale delle mosse possibili. Quindi, il numero minimo di mosse richieste per risolvere la Torre di Hanoi con n dischi è proprio 2n - 1. 

Per confermare che il numero minimo di mosse per risolvere la Torre di Hanoi con n dischi è 2n - 1 si può utilizzare il principio di induzione, in questo caso bisogna seguire i seguenti passi:

1.   Passo base: possiamo partire da n = 1; per risolvere questo caso basta spostare (con una mossa) l’unico disco a nostra disposizione nel paletto finale. Per n=1 abbiamo 21 - 1 = 1.

2.   Passo induttivo: assumiamo che ci vogliano almeno 2n -1 mosse per risolvere il problema con n dischi e dimostriamo (sostituendo n+1) che ci vogliano 2n+1 -1 mosse per risolvere il rompicapo con n+1 dischi. In effetti per risolvere il problema con n+1 dischi dobbiamo prima spostare n dischi lasciando solo il disco più grande al suo posto. Una volta fatto questo basterà spostare il disco più grande su un nuovo paletto e finire rispostando i primi n dischi più piccoli sopra di lui. In totale 2n - 1 mosse per spostare gli n dischi tranne quello grande, 1 mossa per spostare quello grande su un nuovo paletto, e altre 2n - 1 mosse per spostare tutti i dischi sopra al disco grande. 2n - 1 + 1 + 2n -1 = 2 ∙  (2n) - 1 = 2n+1 -1.

Il minimo numero di mosse richiesto per una torre di n dischi è dato da 2n-1. È interessante notare che ciò corrisponde ad un numero composto, in binario, da una sequenza di 1 pari al numero n dei dischi. Ad esempio per tre dischi si ha 1112 = 710.

L’oggetto virtuale

http://utenti.quipo.it/base5/jshanoi/hanoi4.htm 

 Biblio/sitografia

Gardner M., Enigmi e giochi matematici, Rizzoli, 1987, pagg. 48-50

http://it.wikipedia.org/wiki/Torre_di_Hanoi

http://areeweb.polito.it/didattica/polymath/htmlS/probegio/GAMEMATH/Hanoi/Hanoi.htm