La torre di Hanoi: un classico rompicapo che da più di un secolo porta i matematici alla ricerca di nuove sfide per risolverlo, una delle quali vinta quest’anno da un professore sardo.
A meno che non stiate giocando a scacchi, non vi porreste mai come problema il dover spostare una torre; eppure è su questo che si basa uno dei più conosciuti giochi rompicapo: la torre di Hanoi. Questo gioco è di solito costituito da tre aste, su una delle tre vi sono impilati dei dischi concentrici di raggio diverso, dal più largo, in basso, al più stretto, in alto. Lo scopo è quello di spostare tutti i dischi sulla seconda asta seguendo due semplici regole: si può spostare solo un disco alla volta e non è possibile poggiare un disco più largo sopra uno più stretto. Ovviamente questa operazione si può effettuare solo sfruttando la terza asta per aiutarsi. Se non aveste aste e dischi a disposizione, online si trovano moltissime versioni del gioco.
Versione in legno del gioco. Immagine via Shutterstock
Anche se il gioco fu ufficialmente inventato nel 1883 dal matematico francese François Anatole Lucas, l’idea su cui si basa la torre di Hanoi era storicamente diffusa in molte culture e il suo meccanismo noto tra i matematici. Già nel 1550, infatti, l’italiano Gerolamo Cardano riportò nel De Subtililate la storia che racconta di un monastero in cui si trovano tre tronchi di legno, su uno dei quali sono impilati sessantaquattro dischi d’oro. Il compito dei monaci è quello di spostare i dischi da un tronco all’altro secondo le regole descritte in precedenza. Secondo la leggenda, quando i monaci avranno spostato l’ultimo disco ci sarà la fine del mondo, tra quanto tempo succederà?
Dal punto di vista matematico, il problema consiste nel trovare il numero minore di mosse necessarie per effettuare l’operazione di spostamento. Se n è il numero di dischi da spostare, ci vorranno $latex 2^n-1$ mosse per muovere tutta la torre.
Si può dare una dimostrazione di questa legge usando il principio di induzione. L’induzione funziona in modo che, se la legge vale per 1 disco e, supponendo che sia vera per n-1 dischi, si dimostra che vale anche per n dischi, allora la legge è vera sempre. Per un disco, la legge si verifica banalmente, dato che servirà una sola mossa per spostare la torre e quindi $latex 1=2^1-1$. Se abbiamo n dischi, invece, quello che dovremo fare è:
– spostare i primi $latex n-1$ dischi sull’asta ausiliaria e questo stiamo supponendo che richieda $latex 2^{n-1}-1$ mosse,
– spostare il disco che sta alla base sull’asta di destinazione, 1 mossa
– rispostare la torre composta da $latex n-1$ dischi sul disco appena mosso, altre $latex 2^{n-1}-1$ mosse.
Dunque, complessivamente il numero di mosse per spostare n dischi sarà $latex 2^{n-1}-1+1+2^{n-1}-1=2\cdot 2^{n-1}-1 = 2^n-1$
proprio come si voleva dimostrare.
Nel caso del monastero, quindi, i monaci dovranno spostare $latex 2^{64}-1 $ volte i dischi per portare a termine il loro compito. Questo numero è talmente alto che, anche se impiegassero un solo secondo per spostare ogni disco, ci vorrebbero circa 582 miliardi di anni, più di cento volte l’attuale età della Terra! Si tratta un classico esempio di crescita esponenziale, altri sono spiegati nell’articolo Cos’è la crescita esponenziale. Ovvero “E se i Vulcaniani ci avessero sempre preso in giro?”.
Come risolvere la torre a sei livelli conoscendo le mosse per risolvere quella con cinque livelli. Le immagini sono prese dalla versione online del gioco presente su flashgames.it.
agli inizi del Novecento, la torre di Hanoi ha sempre affascinato matematici e informatici. Per fornire le giuste istruzioni su come muovere i dischi al fine di risolvere il puzzle sono stati elaborati numerosi algoritmi, sfruttando la teoria dei grafi o la rappresentazione binaria. Ma, visto che ai matematici piace generalizzare, già nel 1908 Dudeney in The Canterbury Puzzles and other curious problems propose la versione del problema con quattro aste, chiamandolo puzzle di Reve. Nel 1941, invece, Frame e Stewart presentarono due diverse strategie per n dischi e un qualsiasi numero k di aste. Per entrambe il numero di mosse richieste era dato da
$latex M_{n,k}=\sum_{t=1}^i 2^{t-1}\frac{(k+4-t)!}{(k-3)!(t-1)!}+2^i\big (n-\frac{(k+4-t)!}{(k-3)!(i-1)!}\big)$, con $latex i= max \big (k\in Z^+ | n- \frac{(k+4-t)!}{(k-3)!(i-1)!}>0\big)$
Dimostrare che questo fosse il numero minimo di mosse da impiegare è rimasta una questione irrisolta per molto tempo. La prova dell’effettiva minimalità di Mn,k è stata data solo pochi mesi fa dal professore sardo Roberto Demontis, dopo un lavoro di ricerca durato cinque anni.
Anche se meno del cubo di Rubik, anche la torre di Hanoi è oggetto di numerose sfide. Al momento il record di velocità nella risoluzione di una torre a sei livelli è detenuto da una bambina di sei anni, Liba Wahaj, che ha impiegato 55.45 secondi. Fortunatamente ancora troppo lenta per farci temere la prossima fine del mondo!
Bibliografia:
- Klavžar, U. Milutinović, C. Petr. On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem Discrete Appl. Math., 120(1-3):141–157, 2002.
- Demontis What is the least number of moves needed to solve the k-peg Towers of Hanoi problem?
- Danesi The Liar Paradox and the Towers of Hanoi : The 10 Greatest Math Puzzles of All Time Wiley, 2004
Immagine di copertina:
Silhouette the pagoda building against golden sunset, Slometo via Shutterstock