Torri di Hanoi: professore sardo risolve il dilemma | Matematica

Le Torri di Hanoi sono un rompicapo matematico che ha ispirato nel 1939 Bonnie Madison Stewart a formulare l’omonimo problema poi pubblicato sull’American Mathematical Monthly e rimasto irrisolto fino ad oggi. L’intuizione geniale arriva da Roberto Demontis, un professore sassarese di 37 anni che attualmente insegna in un istituto agrario. Ma oggi la sua carriera potrebbe subire una svolta.

Torri di Hanoi: un gioco antico e premonitore?

Il gioco delle Torri di Hanoi è piuttosto semplice: ci sono tre paletti e un numero imprecisato di dischi con un diametro via via crescente, impilati in ordine in uno dei paletti. Lo scopo del gioco è quello di trasferire tutti i dischi in un altro paletto, mantenendo l’ordine, facendo attenzione a non poggiare un disco più grande sopra un disco più piccolo e potendo spostare solamente in disco per volta. Sembra semplice, ma se il numero di dischi è molto elevato allora il processo di soluzione è davvero lungo: pensate di dover risolvere un cubo di Rubik 100 x 100 x 100, molto più complesso del classico 3 x 3 x 3.

Una leggenda narra che in un tempio indù alcuni monaci ogni giorno alcuni monaci spostano uno dei 64 dischi d’oro tra le loro tre Torri di Hanoi e quando avranno terminato il mondo finirà. Questo gioco quindi sembra avere origini antichissime, in realtà la leggenda è stata inventata dall’azienda produttrice del gioco a scopi pubblicitari. La paternità del rompicapo delle Torri di Hanoi appartiene al matematico francese Édouard Lucas che inventò il gioco nel 1883. Da semplice gioco questo rompicapo è diventato ispirazione per matematici ed informatici di tutto il mondo.

Il gioco delle Torri di Hanoi

Il dilemma: quante mosse servono?

La soluzione al problema abbiamo detto è tutt’altro che semplice da formalizzare con una lista di istruzioni, tuttavia è possibile utilizzare una formulazione ricorsiva che risolve efficacemente il problema. L’algoritmo è il seguente, supponiamo di avere n dischi e 3 paletti (A,B,C): 

1. Sposta i primi n-1 dischi da A a B (questo lascia il disco n da solo sul paletto A)
2. Sposta il disco n da A a C
3. Sposta n-1 dischi da B a C

Il punto 2 è un’azione elementare, direttamente permessa dalle regole del gioco. I punti 2 e 3 invece possono essere visti come la richiesta di risolvere il problema delle Torri di Hanoi con n-1 dischi. Un algoritmo ricorsivo funziona proprio così: o compie un’azione banale oppure richiama una versione semplificata del problema. Dopo un certo numero di chiamate ricorsive il problema n diventerà 1 e il problema sarà risolvibile direttamente.

Il dilemma è questo: qual è il numero minimo di mosse per risolvere il problema delle Torri di Hanoi? Nel caso sopraesposto con solamente tra paletti ed un numero n di dischi il problema è facilmente risolvibile: servono 2ⁿ – 1 mosse come minimo, lo si dimostra risolvendo l’equazione di ricorrenza. Per vostra curiosità, seconda la leggenda del monastero induista, il mondo dovrebbe finire tra 18.446.744.073.709.551.615 giorni, ovvero 50.539.024.859.478.223 anni cioè circa 50 biliardi di anni. Circa 10 milioni di volte la vita media residua del nostro Sole. Sono molto ottimisti i monaci se pensano di sopravvivere allo stadio di gigante rossa del Sole.

Visualizzazione grafica della procedura indicata dall’algoritmo

Ma allora vi chiederete dov’è il problema? La soluzione già esisteva. In realtà i matematici amano mettersi i bastoni tra le ruote: e se aumentiamo il numero di paletti? Con più di tre paletti non c’è più un unico percorso da seguire per spostare i dischi e quindi il problema di trovare quello minimo è molto complesso. Dal 1939 ad oggi sono state proposte numerose soluzioni, ma che nessuno mai era riuscito a dimostrare fossero proprio quelle minime, finché non arriva il nostro Roberto Demontis. La dimostrazione era stata proposta già qualche anni fa, ma ci è voluto un po’ prima che la comunità scientifica la approvasse, pubblicandola nella rivista “Discrete Mathematics, Algorithms and Applications” (DMAA). Il matematico spiega a La Nuova Sardegna:

Immaginate di avere un certo numero di pioli. Su uno di questi si trova un certo numero di dischi tutti di dimensione diversa, impilati in ordine crescente, dal più grande al più piccolo. Volete spostare questa torre su un altro piolo. Per fare ciò tuttavia dovete rispettare due regole: potete cioè spostare solo un disco alla volta e non potete mai mettere un disco più grande sopra uno più piccolo. Qual è il numero minimo di mosse? Questo problema ammette una soluzione immediata nel caso in cui si disponga di soli tre pioli. Al punto tale che è un classico esempio di semplice dimostrazione per induzione. Al contrario, il numero minimo di mosse per ricostruire la Torre di Hanoi nel caso in cui si disponga di almeno quattro pioli è cosa ben più complessa perché non si poteva risolvere con metodi deterministici. In altre parole, mentre nel caso elementare di tre pioli le mosse successive sono univocamente determinate dopo la prima, nel caso più complesso viene meno questo determinismo: dopo ogni mossa è possibile cambiare strategia pur restando nel numero minimo di quelle necessarie a risolvere il puzzle.

L’insegnate ha avviato in seguito alla pubblicazione una serie di collaborazioni con diverse università e riviste scientifiche e ci dà una importante lezione:

Ritengo che questo mio piccolo successo sia anche merito degli insegnanti che ho avuto: dalla maestra Speranza Cesaraccio, ai professori Tore Sini e Giovanni Canu e al mio relatore di tesi Umberto Cerruti. Grazie a loro ho potuto capire la bellezza della matematica, la purezza e l’essenza del suo linguaggio scevro da ogni retorica, in continua analisi di ciò che ci circonda.

Perché è proprio vero che la matematica è l’unico linguaggio veramente universale e inequivocabile. A molti potrà sembrare ostico e inintelligibile, ma è alla matematiche che dobbiamo tutto: ci da la possibilità di comprendere, prevedere e controllare la natura con una precisione arbitraria. Il dilemma delle Torri di Hanoi potrà sembrare inutile e fine a sé stesso ed in realtà tutta la matematica è così; nasce per pura curiosità dell’intelletto umano. E poi qualcuno si accorge che può essere tremendamente utile anche ai fini pratici. Pensiamo ad esempio all’algebra di Boole su cui oggi si basano i PC: prima della rivoluzione digitale nessuno avrebbe mai pensato sarebbe servita davvero a qualcosa.

Dalla sezione scienze è tutto e ricordate di assecondare sempre la vostra curiosità e la vostra voglia di conoscere. Noi saremo felici di darvi una mano! Continuate a seguirci!