Il gioco della fine del mondo

Hanoi è la capitale dello stato di Vietnam dal 1976, anno della riunificazione tra Vietnam del Nord e Vietnam del Sud. Lo scorso 10 ottobre (un giorno matematicamente molto particolare secondo il calendario gregoriano: 10/10/10) gli abitanti di Hanoi e tutti i vietnamiti hanno festeggiato il millesimo anniversario della costruzione della città, voluta dall'imperatore Lý Thái Tổ che la chiamò Thăng Long, cioè "dragone che si alza in volo".
La città di Hanoi è ben nota, oltre che ai geografi, agli storici e ai viaggiatori, anche agli informatici. Perché mai? Semplicemente perché nel 1883 il matematico francese Edouard Lucas, per attribuire un tocco di esotismo ad un rompicapo di sua invenzione, si inventò una leggenda collegata all'antica città di Hanoi. Secondo la leggenda di Lucas, in un tempio di Hanoi alcuni monaci sono intenti, da tempo immemore, a poggiare dischi d'oro su colonne di diamante, consapevoli che nel momento in cui avranno terminato il loro compito il mondo avrà fine.
Più precisamente, ci sono 3 colonne e 64 dischi di dimensioni diverse. All'inizio dei tempi i dischi erano incolonnati sulla prima colonna in ordine di grandezza, cioè in modo tale che ogni disco poggiasse su un disco più grande (i dischi formavano quindi un cono). Da allora i monaci hanno cominciato a spostare dischi, uno alla volta, rispettando la regola fondamentale secondo la quale è vietato poggiare un disco su un disco più piccolo, e con l'obiettivo supremo di spostare tutti i dischi sulla terza colonna.
Come si risolve il rompicapo? La soluzione che si impara nei corsi di programmazione è un tipico esempio di algoritmo ricorsivo, e anche un eccellente esempio di ragionamento per induzione.
Supponiamo di essere in grado di risolvere il gioco per n dischi, e cimentiamoci nella versione con n+1 dischi. Sulla prima colonna avremo quindi n+1 dischi, che dobbiamo spostare sulla terza colonna. Sapendo risolvere il rompicapo con n dischi, non avremo difficoltà a spostare i primi n dischi dalla prima alla seconda colonna; potremo agevolmente spostare il disco (n+1)-esimo dalla prima alla terza colonna, e infine ripeteremo il procedimento degli n dischi spostando tutti i dischi dalla seconda alla terza colonna.
Siccome il gioco è banalmente risolvibile se n=1 (si tratta semplicemente di spostare un disco dalla prima alla terza colonna), per induzione possiamo concludere che è possibile risolvere il rompicapo per qualsiasi numero n.
Si può dimostrare che il numero minimo di mosse necessarie per risolvere il rompicapo con n dischi è pari a 2ⁿ-1. Se i dischi fossero soltanto 3, basterebbero quindi 2³ - 1 = 7 mosse; con 64 dischi, il numero diventa enorme: i monaci dovrebbero effettuare più di 18 miliardi di miliardi di spostamenti!
Possiamo quindi stare tranquilli: se immaginiamo che per spostare un disco i monaci impieghino un secondo, il mondo finirà tra circa 584 miliardi di anni, un tempo ben superiore a quello necessario a trasformare il Sole nella gigante rossa che inghiottirà anche il nostro pianeta.