Torre di Hanoi - PerGioco.net

La Torre di Hanoi è uno dei rompicapo più noti e studiati della matematica ricreativa, nonché un classico esempio di problema algoritmico basato sulla ricorsione. Il gioco è costituito da una serie di dischi di dimensioni diverse, inizialmente impilati in ordine decrescente su uno dei tre pioli disponibili. L’obiettivo è trasferire l’intera torre su un altro piolo, utilizzando il terzo come supporto, nel rispetto di due regole fondamentali: è possibile muovere un solo disco alla volta e non è mai consentito collocare un disco più grande sopra uno più piccolo.

Il rompicapo fu introdotto nel 1883 dal matematico francese Édouard Lucas, che lo presentò con il nome La Tour d’Hanoï. Fin dalla sua origine, il gioco è stato accompagnato da una narrazione suggestiva — quella dei monaci impegnati a spostare 64 dischi in un tempio — che ha contribuito alla sua diffusione, ma il suo vero interesse risiede nella struttura matematica sottostante.

Dal punto di vista teorico, la Torre di Hanoi rappresenta un esempio paradigmatico di algoritmo ricorsivo. Indicando con $T(n)$T(n) il numero minimo di mosse necessarie per trasferire una torre di $n$n dischi, si ottiene la relazione:

da cui deriva la formula chiusa:

Questa crescita esponenziale implica che il problema diventa rapidamente impraticabile: già con 20 dischi si supera il milione di mosse, mentre con 64 dischi si raggiungono valori astronomici.

La struttura del problema è profondamente legata alla ricorsione: per spostare una torre di $n$n dischi è necessario risolvere due volte il problema con $n-1$n−1 dischi, intervallando le due fasi con lo spostamento del disco più grande. Questa autosimilarità rende la Torre di Hanoi un modello ideale per lo studio dell’induzione matematica e dei processi iterativi.

Un ulteriore livello di interpretazione emerge considerando la rappresentazione delle configurazioni come nodi di un grafo, collegati da archi che rappresentano le mosse lecite. Il grafo risultante presenta una struttura altamente regolare e autosimile, strettamente connessa al codice di Gray, in cui configurazioni consecutive differiscono per una sola variazione. Questa corrispondenza consente di descrivere la sequenza ottimale delle mosse attraverso rappresentazioni binarie.

Dal punto di vista geometrico, il grafo delle configurazioni rivela inoltre una struttura frattale che richiama il triangolo di Sierpiński: il problema con $n$n dischi contiene al suo interno copie ridotte del problema con $n-1$ dischi, organizzate secondo uno schema autosimile. Questo collegamento rende la Torre di Hanoi un esempio concreto di interazione tra matematica discreta e geometria frattale.

Oltre alla versione classica a tre pioli, esistono numerose varianti. La più studiata è quella con quattro pioli, nota come problema di Reve, per la quale non esiste una formula chiusa semplice e la cui soluzione ottimale è stata dimostrata solo in tempi recenti. In generale, l’estensione a un numero maggiore di pioli conduce a problemi ancora aperti nella teoria algoritmica e combinatoria.

Grazie a queste caratteristiche, la Torre di Hanoi occupa una posizione centrale sia nella didattica sia nella ricerca: è utilizzata per introdurre concetti fondamentali dell’informatica teorica, come la ricorsione, la complessità algoritmica e la rappresentazione dei dati, e allo stesso tempo continua a stimolare nuovi studi e generalizzazioni.

In definitiva, la Torre di Hanoi rappresenta un perfetto equilibrio tra semplicità e profondità: un sistema di regole elementari capace di generare una struttura matematica ricca, elegante e sorprendentemente complessa.