Gli otto dischi, che formano la cosiddetta torre, devono poi essere spostati su una delle altre due colonnine libere, seguendo però una regola precisa: si può spostare soltanto un disco alla volta ed è proibito collocare uno qualsiasi dei dischi su uno più piccolo.
Il gioco venne inventato nell'Ottocento da Edouard Lucas, studioso di teoria dei numeri, che deve la sua fama all'analisi della successione di Fibonacci. Professore di matematica in un liceo parigino, Lucas è uno dei più grandi in giochi matematici, inventore di tanti rompicapi e giochi ancora oggi popolari. Morì nel 1891, a quarantanove anni, per un banalissimo incidente. La scheggia di un piatto, rotto accidentalmente durante un banchetto, lo ferì al volto e morì in pochi giorni per erisipela.
Lucas lanciò il suo nuovo gioco nel 1883 e quella che segue, è la sua presentazione originale, dal tono ottocentesco, un po' ingenuo, ma divertente:
Questo gioco è stato scoperto, per la prima volta, fra le carte dell'illustre Mandarino FER-FER-TAM-TAM, e sarà pubblicato nell'immediato futuro, su ordine del governo cinese.
La Torre di Hanoi è composta da una serie dischi, di dimensioni decrescenti, in numero variabile, che noi abbiamo realizzato con otto dischi di legno, bucati al centro. In Giappone, in Cina e a Tonkino sono di porcellana.
Il gioco consiste nel demolire la torre e nel ricostruirla su un'altra colonnina, seguendo le regole date.
Divertente e istruttivo, facile da imparare e da giocare in città, in campagna oppure in viaggio, ha per obiettivo la divulgazione della scienza, come tutti gli altri giochi originali e curiosi del professor N. CLAUS (OF SIAM)

Lucas per rendere ancora più affascinante il suo gioco, inventò una curiosa leggenda, la Torre di Brahma, che riportiamo a parte e che ancora oggi molti ritengono autentica e di origine indiana.

Indichiamo con A, B e C le tre colonnine. Nel caso banale di un unico disco, occorrerà un solo movimento per risolvere il gioco, basta infatti spostare il disco dalla colonnina A alla colonnina C. Con due dischi, sono necessari 3 movimenti, si deve spostare il disco superiore sulla colonnina B, il disco più grande su C ed infine l'altro disco sempre su C. Quali sono gli spostamenti minimi necessari per trasferire la torre a tre dischi da A a C? Dobbiamo spostare il disco superiore su C e quello di mezzo su B, sul quale spostiamo poi il disco più piccolo.
In seguito, spostiamo il disco più grande su C, quello più piccolo su A e, per finire, il disco da B a C e da A a C. Sono, in totale, sette movimenti.
Con un po' di pratica si arriva facilmente a capire il procedimento da seguire con un numero qualsiasi di dischi, scoprendo la formula risolutiva del gioco. Se lo sappiamo risolvere con tre dischi, lo sapremo, infatti, risolvere anche con quattro. Sarà sufficiente trasportare dapprima i tre dischi superiori sulla seconda colonnina, con il procedimento già noto, successivamente il quarto disco sulla terza e infine si collocheranno su questo gli altri tre dischi, sempre con procedimento già utilizzato in precedenza. Risolto il caso dei quattro dischi, non ci saranno difficoltà a procedere, allo stesso modo, con cinque dischi. Sono richiesti 31 movimenti, ma i primi 15 movimenti sono identici a quelli della torre con quattro dischi. Si prosegue poi con sei dischi e così via, sempre rispettando le regole del gioco. A questo punto il lettore frastornato rischia di non capire più nulla.
Al solito, è bene ricordarlo, per capire la matematica, anche soltanto di gioco, non si può soltanto "leggere", ma è necessario "fare" matematica, con esercizi e riflessioni personali. In questo caso, giocando con dischi e colonnine reali (o virtuali, al computer), tutto sarà sicuramente più chiaro.
Saremo comunque in grado, alla fine della nostra indagine, di mettere in tabella il numero dei movimenti minimi necessari per lo spostamento della Torre, nel caso di un certo numero di dischi.

Vogliamo mettere in evidenza i valori in base due della tabella, che costituiscono una successione di grande semplicità: ogni volta che si aggiunge un disco alla torre, basta aggiungere un "1" al numero dei movimenti necessari.
La soluzione matematica di un problema, anche in questo caso, segue sempre la strada più semplice e lineare.
Dalla tabella possiamo facilmente dedurre la formula generale: con n dischi si hanno 2^n - 1 movimenti.
Resta in ogni caso da dimostrare la validità di questa formula che abbiamo scoperto, ma che rimane ancora, a questo punto, una semplice congettura.
Possiamo servirci del metodo di induzione matematica che, in generale, viene enunciato nel modo seguente:

Data una successione infinita di proposizioni A1, A2, A3, …, An, An+1, …, se verifichiamo che la prima proposizione è vera e che, se si suppone vera per una qualsiasi proposizione An, è vera anche per An+1, allora tutte le infinite proposizioni della successione sono vere.

In particolare, possiamo dire, in aritmetica, che se una proposizione A è vera per il numero 1 e se si suppone che sia vera per un intero qualsiasi n, si può dedurre che è vera anche per il successivo n + 1, allora è vera per tutti i numeri interi.
Applichiamo questo principio di induzione al nostro problema.

Si vede immediatamente che la formula è vera con un solo disco. Abbiamo infatti:

M(1) = 2^1 - 1 = 1.

Supponiamo ora che sia vera per n dischi e che si abbia quindi:

M(n) = 2^n - 1.

Nel caso di n + 1 dischi, incominciamo a spostare gli n dischi superiori dalla colonnina A alla B e, per questo, abbiamo supposto che siano necessari M(n) = 2^n - 1 movimenti. Spostiamo poi il disco più grande dalla colonnina A alla C, con un movimento. Infine, spostiamo gli n dischi dalla colonnina B alla C, sul disco più grande, e questo richiede altri
M(n) = 2^n - 1 movimenti. In totale, i movimenti che abbiamo compiuto, per spostare gli n + 1 dischi, sono:

M(n) + 1 + M(n) = 2^n - 1 + 1 + 2^n - 1 = 2 x 2^n - 1 = 2^(n+1) - 1

In questo modo, resta confermata la formula trovata, che è così dimostrata per induzione.

Che cosa succede se introduciamo una quarta colonnina nel nostro gioco? Abbiamo ancora, come minimo, 3 movimenti con 2 dischi, ma soltanto 5 con 3, 9 con 4, 13 con 5, 17 con 6, 25 con 7 e 33 con 8 dischi.
Si tenga presente che la quarta colonnina consente di costruire più torri. Ad esempio, con quattro colonnine possiamo fare due torri, una di due dischi e l'altra di uno. Poiché sono necessari tre movimenti per costruire la torre di due dischi con quattro colonnine, e un movimento per la torre di un disco, il totale dei movimenti sarà: 3 + 1 + 1 + 1 + 3 = 9. Prosegua il lettore curioso questa nuova indagine.

Federico Peiretti

La Torre di Brahma

Narra la leggenda che all'inizio dei tempi, Brahma portò nel grande tempio di Benares, sotto la cupola d'oro che si trova al centro del mondo, tre colonnine di diamante e sessantaquattro dischi d'oro, collocati su una di queste colonnine in ordine decrescente, dal più piccolo in alto, al più grande in basso. E' la sacra Torre di Brahma che vede impegnati, giorno e notte, i sacerdoti del tempio nel trasferimento della torre di dischi dalla prima alla terza colonnina. Essi non devono contravvenire alle regole precise, imposte da Brahma stesso, che richiedono di spostare soltanto un disco alla volta e che non ci sia mai un disco sopra uno più piccolo. Quando i sacerdoti avranno completato il loro lavoro e tutti i dischi saranno riordinati sulla terza colonnina, la torre e il tempio crolleranno e sarà la fine del mondo.

Il Tempio d'oro di Benares, il più antico e il più sacro dei mille templi di Benares, la città sacra dell'India. Qui, secondo la leggenda inventata da Lucas, si trova la Torre di Brama. Racconta Lucas che il mondo finirà, quando i sacerdoti avranno spostato tutti e sessantaquattro i dischi. Se calcoliamo il numero dei movimenti necessari per spostare i dischi, con la formula data nel testo, 2 elevato a 64, meno 1, otteniamo 18.446.744.073.551.615 movimenti. Nel caso in cui i sacerdoti impieghino un secondo per ogni movimento, ci vorranno più di cinque miliardi di secoli (secondo i calcoli dello stesso Lucas) per il trasporto di tutti i dischi da una colonnina all'altra. Possiamo quindi stare tranquilli, almeno da questo punto di vista, per il nostro futuro.

Per saperne di più

Il problema originale, nella versione del suo inventore:
M. Edouard Lucas, Récréations mathematiques, III, Albert Blanchard, 1979.

Fred Schuh, The master book of mathematical recreations, Dover, 1968.

Per la Torre di Hanoi con più di tre colonnine:
Benjamin Schwartz, Mathematical solitaires and games, Baywood, 1978.

La biografia di Lucas, con la presentazione del suo metodo per la ricerca dei numeri primi:
http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Lucas.html

Un'accurata presentazione del gioco:
http://cut-the-knot.com/recurrence/hanoi.html

Una curiosa variante della Torre di Hanoi:
http://cut-the-knot.com/recurrence/BiColorHanoi.html

La Torre di Hanoi sulla Wikipedia:
http://en.wikipedia.org/wiki/Tower_of_Hanoi

Le diverse soluzioni della Torre di Hanoi:
http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/hanoi_eng.html
http://obelix.ee.duth.gr/~apostolo/TowersOfHanoi/

Il testo, in inglese, della presentazione originale, fatta da Lucas, della Torre di Hanoi:
http://www.cs.wm.edu/~pkstoc/toh.html

Gioca on-line

http://www.tiziana1.it/torredi_hanoi.html

http://www.comunedasa.it/torri_Hanoi/applet_Hanoi.asp

http://mazeworks.com/hanoi/index.htm

http://www.funmin.com/online-games/tower-of-hanoi/index.php

http://www.parentinghumor.com/games/hanoi.htm