La torre di Hanoi

Condividi su facebook
Condividi su twitter
Condividi su whatsapp
Condividi su telegram
Condividi su email
Condividi su print
139 La torre di Hanoi

Anche Piero Angela, in una puntata del suo Superquark, ha parlato di Mate Fitness, la palestra della matematica di Genova, che ho avuto l’onore di inaugurare con una mia conferenza nell’aprile 2006. Nel servizio ad un certo punto si parla della “Torre di Hanoi”, un rompicapo ideato dal matematico Edouard Lucas, nel quale si tratta di spostare una costruzione con un certo numero di dischi. Nel servizio scopriamo che non solo i ragazzi sono interessati a questo gioco, ma anche gli adulti con altro occhio affrontano il problema e sono infastiditi se qualcosa non va come previsto.
Il testo è semplice: ci sono tre pali fissati nel terreno, e in uno di essi sono infilati quattro dischi, in ordine di grandezza con il minore in alto. Bisogna spostare la torre su un altro palo, muovendo un disco alla volta e badando che un disco grande non sia mai posto sopra uno più piccolo, in nessuna fase del gioco.
Ci si chiede se è possibile riuscire nel nostro intento e, in caso di risposta affermativa, quante mosse occorreranno come minimo per spostare tutta la costruzione.
Su molti siti internet c’è anche una piccola animazione che dà la soluzione. Ma noi ci chiediamo quante mosse occorrerebbero se i dischi fossero più di quattro, ad esempio dieci, o magari ancora di più.
La soluzione è semplice se costruiamo una tabella nella quale annotiamo il numero di mosse necessarie quando ci sono pochi dischi: con un disco ci vuole una sola mossa (ovvio), con due dischi ce ne vorranno tre (disco grigio, verde, grigio), con tre dischi sette mosse (grigio verde grigio giallo grigio verde grigio), e con quattro dischi quindici mosse.
Basta che facciamo un po’ di attenzione, e che segniamo con una penna i dischi da muovere, e troveremo subito la regola anche con un numero maggiore di dischi. Sì, perché con quattro dischi le mosse sono: grigio verde grigio giallo grigio verde grigio (cioè esattamente le sette mosse che occorrono per spostare la torre alta tre dischi), rosso, poi nuovamente le sette mosse di prima. Ecco quindi spiegato il motivo per il quale le mosse sono quindici, cioè il doppio di sette più una. Così con cinque dischi, le mosse saranno il doppio di 15 più 1, cioè 31, e poi il doppio di 31 più 1 e così via.
L’osservazione matematica ci permette allora di affermare che per spostare una torre alta 10 piani ci vorranno 1023 mosse, senza doverle materialmente eseguire una per una.
Ci sono tante altre cose da scoprire sulla Torre di Hanoi, ma per oggi può bastare.
Però se qualcuno se la sente, può dire quante mosse occorrono con una torre di venti piani. Basta notare che le mosse sono sempre una potenza di 2, meno 1, ad esempio con 10 dischi occorrono 2 alla decima meno una mossa, cioè 1023, come detto sopra. Allora, con venti dischi…

Giorgio Dendi

Condividi su facebook
Condividi su twitter
Condividi su whatsapp
Condividi su telegram
Condividi su email
Condividi su print

Ti potrebbero interessare

“Sono positivo al coronavirus”. Boris Johnson, premier britannico, annuncia la

A partire dal contesto scolastico è un’azione di grande valore

Prima i tweet con cui le invita a tornarsene al

“Ieri con la collega Erica Mazzetti abbiamo incontrato i vertici

La nuova serie irriverente debutterà il 26 Luglio solo su

Con l’inizio del nuovo anno scolastico, in diversi Stati membri,

Chiudi il menu
ArabicEnglishFrenchGermanItalianRomanianSpanish
Questo sito si avvale di cookie necessari al funzionamento ed utili alle finalità illustrate nella cookie policy. Se vuoi saperne di più o negare il consenso consulta la cookie policy. Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, accetti l’uso dei cookie.