Il rompicapo per predire la fine dell’universo: cos’è e come si risolve la torre di Hanoi

La torre di Hanoi è un rompicapo ideato dal matematico francese Édouard Lucas d’Amiens e presentato per la prima volta nel 1883. Il gioco è composto da tre paletti e da una serie di dischi di dimensioni diverse che devono essere spostati rispettando alcune regole precise.

Quando il rompicapo fu messo in commercio, venne accompagnato da una storia pensata per renderlo più affascinante. Secondo questa leggenda, il gioco sarebbe  la versione semplificata della "Torre sacra di Brahma", una torre formata da 64 dischi d’oro che devono essere spostati seguendo le stesse regole del rompicapo e a cui i bramini del tempio lavorano giorno e notte spostando un disco al secondo. La leggenda, di cui esistono molte versioni differenti, racconta che quando l’ultimo disco sarà stato spostato, l’universo giungerà alla sua fine.

Naturalmente si tratta di una storia inventata per accompagnare il gioco, senza alcun fondamento di verità, ma questa idea porta con sé una domanda interessante: quanto tempo servirebbe davvero per risolvere una torre con 64 dischi se si potesse fare una mossa al secondo?

Vediamo come si gioca alla torre di Hanoi, come risolverla e quante mosse servono per risolvere la torre “Torre sacra di Brahma" e arrivare alla fine dell’universo.

Come si gioca alla torre di Hanoi

La torre di Hanoi è composta da tre paletti e da alcuni dischi (generalmente 8) di dimensioni diverse, forati al centro così da poter essere infilati sui paletti. All’inizio del gioco tutti i dischi si trovano sul primo paletto, impilati dal più grande in basso al più piccolo in cima.

L’obiettivo è spostare l’intera torre sull’ultimo paletto, rispettando alcune regole fondamentali:

• si può spostare un solo disco alla volta;
• ogni mossa consiste nello spostare un disco da un’asta a un’altra. Non è possibile, per esempio, togliere un disco e appoggiarlo temporaneamente fuori dalle aste;
• non si può mai appoggiare un disco più grande sopra uno più piccolo. I dischi devono quindi rimanere sempre ordinati dal più grande in basso al più piccolo in alto.

Come risolvere la torre di Hanoi e quante mosse servono

Per capire come si risolve la torre di Hanoi e quante mosse sono necessarie, iniziamo dal caso più semplice possibile: una torre composta da un solo disco.

Un solo disco

Se abbiamo un solo disco, la soluzione è immediata. Basta spostare il disco dalla prima all’ultima asta e il rompicapo è risolto. Serve una sola mossa.

Due dischi

Con due dischi la situazione è ancora semplice, ma dobbiamo iniziare a riflettere un po’. Se spostassimo immediatamente il disco più piccolo sull’ultimo paletto, poi non potremmo metterci sopra quello verde (perchè è più grande) e sprecheremmo delle mosse.

La sequenza corretta quindi è:

• spostiamo il disco più piccolo sull’asta centrale;
• spostiamo il disco più grande sull’asta finale;
• spostiamo finalmente il disco più piccolo sull’asta finale.

In questo modo ricreiamo la torre sull’ultima asta rispettando tutte le regole. Per due dischi, quindi, servono tre mosse.

Tre dischi

Con tre dischi la torre di Hanoi inizia a richiedere una vera strategia. Per riuscire a ricreare la torre nell’ultimo paletto a destra, dobbiamo fare in modo che il disco più grande, che si trova alla base della torre, sia libero di spostarsi sull’asta di destra. Per farlo, dobbiamo spostare temporaneamente i due dischi più piccoli sul palo centrale.

Possiamo procedere così:

• spostiamo il disco più piccolo sull’asta di destra;
• spostiamo il disco intermedio sull’asta centrale;
• spostiamo il disco più piccolo sopra quello intermedio.

Come prima, per spostare due dischi su un qualunque paletto, abbiamo usato 3 mosse. A questo punto, i due dischi più piccoli si trovano sull’asta centrale e il disco più grande è libero di spostarsi sull’asta destra, utilizzando un’altra mossa. Ora, con altre 3 mosse, trasferiamo anche gli altri due dischi sull’ultima asta, ricreando la torre.

Il conteggio delle mosse quindi è:

• 3 mosse per spostare i due dischi più piccoli sul paletto centrale,
• 1 mossa per spostare il disco più grande sull’asta di destra,
• altre 3 mosse per spostare di nuovo i due dischi più piccoli e andare a completare la torre.

In totale servono 7 mosse per spostare 3 dischi.

La soluzione generale

Se adesso proviamo a ragionare su una torre con 4 dischi, il meccanismo diventa più chiaro:

• per spostare il disco più grande dobbiamo prima spostare i tre dischi più piccoli sull’asta centrale. Come abbiamo visto, per spostare 3 dischi servono 7 mosse.
• A questo punto possiamo spostare il disco più grande sull’asta finale con una sola mossa.
• Infine dobbiamo spostare di nuovo i tre dischi sull’asta finale, il che richiede altre 7 mosse.

In totale:

7 + 1 + 7 = 15 mosse

E se volessimo spostare 5 dischi? Prima dovremmo usare 15 mosse per spostare 4 dischi sul palo centrale, poi useremmo una mossa per spostare il disco più grande sul palo di destra e poi altre 15 mosse per rispostare i dischi più piccoli sull’asta finale.

Quindi dovremmo usare 15 +1 +15 = 31 mosse.

E per 6 dischi? Per 8? Per 64? Il ragionamento è sempre lo stesso: per spostare una torre di X dischi dobbiamo

• spostare i primi X−1 dischi su un’asta intermedia
• spostare il disco più grande
• spostare di nuovo gli X−1 dischi sopra di lui

Questo tipo di soluzioni, in cui per capire cosa fare dobbiamo andare a guardare la soluzione del caso precedente, si chiamano soluzioni ricorsive e, proprio perché la torre di Hanoi ha una soluzione di questo tipo, viene spesso usata come esempio durante le lezioni di informatica per imparare a scrivere algoritmi ricorsivi.

Tra quanti secondi finirà l’universo

Un altro modo, un po’ più compatto, per descrivere quante mosse serviranno per risolvere la torre di Hanoi è la formula:

numero di mosse = 2^{(numero di dischi)} – 1

Con due dischi, infatti, ci servono 2² – 1 = 4 – 1 = 3 mosse, con 3 dischi ne servono 2³ – 1= 8 – 1 = 7, con 4 ne servono 2⁴ – 1 = 15 e così via.

Questa formula ci è molto utile per calcolare quante mosse ci servono per risolvere la Torre di Brahma, composta da 64 dischi d’oro, senza dover calcolare tutti i passaggi precenti. Applicando la formula abbiamo che servono 2⁶⁴ − 1 mosse. Se ci immaginiamo che i monaci riescano a fare una mossa al secondo, l’universo finirà 18.446.744.073.709.551.615 secondi dopo l’inizio del gioco, cioè circa 585 miliardi di anni. Insomma, nulla di cui preoccuparci.

non perderti questo articolo

Come vincere a Monopoly: ecco la strategia migliore