INTRODUZIONE

La torre di Hanoi è un rompicapo manipolativo creato dal matematico Édouard Lucas (1842-1891), ispirato dal gioco degli anelli cinesi, un altro rompicapo da lui studiato. Per approfondire la storia della torre di Hanoi, nonché per vari problemi e rompicapi di logica e matematica, si veda il libro Mathematical Recreations (1953) del matematico belga Maurice Kraitchik.

Il gioco si presenta come una base da cui si erigono tre bastoncini verticali. Sui bastoncini vengono inseriti dei dischi (o altra forma) di dimensioni diverse, tutti bucati in modo che possono essere inseriti o rimossi dai bastoncini. Il numero di dischi è variabile, ed è solitamente compreso fra 5 e 8.

Si comincia inserendo i dischi in ordine, dal più grande al più piccolo, in uno dei bastoncini, come mostrato in figura.

Lo scopo del gioco è spostare tutti i dischi da un bastoncino a un altro, sempre conservando l'ordine dal più grande al più piccolo, come mostrato in figura.

Per farlo, bisogna rispettare due regole:

1. si può spostare solo un disco alla volta;
2. un disco non può mai essere poggiato su un disco più piccolo

Naturalmente se i bastoncini fossero solo due il gioco sarebbe impossibile, ma la presenza del terzo bastoncino permette la risoluzione a prescindere dal numero di dischi.

Nel seguente video, viene mostrata la risoluzione della torre di Hanoi con 5 dischi.

COSTRUIRE LA TORRE DI HANOI

Anche se online si trovano varie versioni della torre di Hanoi a prezzi accessibili, riteniamo utile - come prima attività - far costruire agli studenti stessi delle torri di Hanoi. Si divide la classe in piccoli gruppi e ogni gruppo deve costruire autonomamente la propria torre di Hanoi usando polistirolo (per la base), stuzzicadenti lunghi (per i bastoncini), cartoncino o cartone (per costruire i dischi, chiaramente della forma che si preferisce: cerchi, quadrati, etc.).
Si mostrano alla classe le varie immagini di torri di Hanoi presenti nel file costruiamo_hanoi.pdf e se ne illustrano le varie componenti, specificando che i dischi sono bucati al centro. Si chiede quindi, come attività di problem solving, di ricostruirla, fornendo alla classe il minor numero di indicazioni possibile. Si specifica di costruire la torre con quattro dischi.
Si possono comunque comprare due o tre torri di Hanoi per l'intera classe.

RISOLVERE IL GIOCO

Dopo la costruzione, si spiegano le regole e si lascia la classe libera di esplorare la torre di Hanoi con quattro dischi tentando di risolvere il gioco. Se il gioco con quattro dischi risulta troppo complesso, si può iniziare con tre dischi. Una volta che gli studenti saranno in grado di risolvere la torre, si lancerà una sfida: vince chi riesce a risolverlo nel minor numero di mosse possibile (senza barare!).
Riportiamo in figura la soluzione con il minor numero di mosse possibile, ossia 15 mosse.

Si chiede quindi alla classe cosa accade dopo che è stata effettuata la metà delle mosse (ossia all'ottava mossa): la risposta è che si sposta il pezzo più grande (che viene spostato solo in questa occasione).

ANALISI MATEMATICA

Ci si interroga con la classe su come vari il numero di mosse minimo necessario per la soluzione al variare del numero di pezzi della torre.
Chiaramente se il pezzo è solo uno, basta una mossa. Se i pezzi sono due, servono invece tre mosse.
Si invita la classe a compilare autonomamente, lavorando a coppie, la seguente tabella, aiutandosi con la torre di Hanoi.

Il passo successivo è cercare regolarità all'interno della tabella.
Una prima proprietà che si nota è che per passare da un numero della seconda colonna al successivo (per esempio, da 1 a 3, da 3 a 7 o da 7 a 15), bisogna moltiplicarlo per due e aggiungere uno. Infatti 3 = 1 × 2 + 1, 7 = 3 × 2 + 1, 15 = 7 × 2 + 1, 31 = 15 × 2 + 1.
C'è un motivo del perché questo accade, che può essere esplicitamente discusso con la classe. Per capirlo, analizziamo il caso della torre di Hanoi con tre dischi.

Confrontiamo questa risoluzione con quella della torre a quattro dischi proposta nella sezione precedente. Cosa notiamo? Le prime sette mosse della risoluzione della torre a quattro dischi corrispondono esattamente alla risoluzione della torre a tre dischi (salvo il fatto che il bastoncino di destinazione è diverso nei due casi). In seguito viene spostato il pezzo più grande - come avevamo notato alla fine della sezione precedente - e infine vengono nuovamente rieseguite le sette mosse della risoluzione della torre a tre dischi.
In generale, per risolvere una torre con n dischi, si risolve la torre con n−1 dischi, poi si sposta il disco più grande, infine si risolve nuovamente la torre con n−1 dischi. Quindi, se per risolvere la torre con n−1 dischi ci vogliono k mosse, allora per risolvere la torre con n dischi ci vorranno k + 1 + k mosse, ossia 2 × k + 1 mosse.

La regolarità appena studiata, permette di compilare altre righe della tabella.

Si nota come il numero di mosse cresca rapidamente al crescere del numero di pezzi in gioco. Se immaginiamo di eseguire un mossa ogni secondo, per completare una torre con 12 pezzi ci vogliono 4095 secondi, ossia più di un'ora. Per completare invece una torre con 20 pezzi - eseguendo una mossa al secondo e senza mai fermarsi - ci vorrebbero circa 12 giorni!

Una proprietà più difficile da osservare è invece la relazione diretta fra numero di pezzi e numero di mosse necessario per risolvere il gioco. Quante mosse bisogna fare per risolvere una torre con 10 pezzi? Quante con 15 pezzi? Per trovare la risposta, basta fare 2^k − 1, dove k è il numero di pezzi. Per esempio, per sapere quante mosse bisogna fare con 8 pezzi, si calcola 2⁸ − 1 = 255. Per un'attività di approfondimento sulle potenze, fai click qui.

LA LEGGENDA DEI MONACI

La leggenda dei monaci è la storia con la quale Édouard Lucas presenta il gioco, inventandosi che “è una vecchia leggenda indiana, tratta dal Mahabartha del monaco Ahu”. Si legge in classe il racconto racconto_torre_visnu.pdf che si trova nella sezione ALLEGATI. Si può accompagnare la lettura proiettando alla L.I.M. le immagini contenute in presentazione_racconto.pdf.
Alla fine del racconto, la domanda che viene fatta è: se una torre di Hanoi ha 32 pezzi, e ogni pezzo viene mosso in un'ora, quanto tempo è necessario per completare il gioco?
Dalla sezione precedente, sappiamo che il numero di mosse necessario è 2³²−1. Eseguendo il calcolo con la calcolatrice, ci rendiamo conto che il numero di mosse è di ben 4 294 967 295 (poco più di quattro miliardi)! Per rispondere alla domanda trasformiamo quindi le ore in giorni (dividendo per 24), trovando circa 179 milioni di giorni. Dividendo poi per 365 (trasformando i giorni in anni), otteniamo al risposta desiderata: i monaci impiegheranno circa 490 mila anni, insomma… un bel po'!

LINEAR HANOI

Una variante della torre di Hanoi interessante dal punto di vista matematico è la cosiddetta torre di Hanoi lineare.
Il gioco è identico a quello classico, con la sola differenza che ogni disco può essere spostato solo su un bastoncino adiacente: in altre parole, non sono permessi spostamenti diretti dal primo bastoncino al terzo bastoncino (o viceversa), ma bisogna sempre passare per il bastoncino centrale (facendo due spostamenti invece che uno).

Il gioco ha scarso interesse a livello strategico, perché non richiede ragionamenti più complessi rispetto al gioco classico, ma uno spiccato interesse matematico.
Si invita la classe a compilare la tabella, ampiamente affrontata nelle sezioni precedenti, NUMERO DI PEZZI - NUMERO DI MOSSE. Chiaramente, a parità di numero di pezzi, il numero di mosse sarà maggiore nel caso della torre di Hanoi lineare. Tuttavia, anche in questo caso è presente una regolarità interessante che la classe è invitata a scoprire autonomamente.
Il numero di pezzi k non è più legato al numero di mosse dalla formula 2^k − 1, bensì dalla simile 3^k − 1.