Guarda che bella questa foto!

È solo una torre…

…a Hanoi! Me l’hanno portata dei miei amici dopo un viaggio… Hanoi, Vietnam!

È una bella foto, ma, ti ripeto, è solo una torre…

Sì, ma è una torre a Hanoi! La torre di Hanoi! Come il gioco!

Quale gioco?

Dai, questo. [Rovista fra i suoi giochi]

Ah, sì, l’ho visto. Anzi, lo conosco pure, è un solitario, ma non lo so fare se la torre è troppo alta… però me l’hanno presentato come torre di Lucas, non di Hanoi. Lucas immagino sia l’inventore, Hanoi che c’entra?

Si racconta che in un monastero vietnamita ci sia un tempio con una torre come questa, di 64 piani. I monaci instancabilmente tentano di risolvere il solitario. Quando ci riusciranno, il mondo finirà.

Ma che balla!

Sì, lo so… la storia è stata inventata per vendere di più il gioco, quando è uscito. E hai ragione, l’inventore si chiama Lucas che, indovina…

…era un matematico?

Esatto. Ti insegno a risolverlo. Ripetimi le regole, così vediamo se le ricordi bene.

Allora, hai una torre alta un certo numero di piani, fatti di cerchi concentrici uno più piccolo dell’altro. La tua torre ne ha 6 ad esempio;

Ogni turno puoi spostare uno dei cerchi e metterlo su una delle altre due colonne, a patto che tu stia spostando solo il cerchio più in alto della sua colonna.

Esatto, quindi puoi spostare questo.

In più il cerchio che sposti deve essere messo sopra uno che è più grande di lui.

Quindi puoi fare questa mossa,

ma non puoi fare questa.

Vinci quando riesci a spostare tutta la torre su una delle altre due colonne.

Se la torre è piccola hai detto che non hai problemi, giusto?

Sì, più o meno. Con 2 piani è facilissimo, con 3 mosse hai fatto.

Anche con 3 piani è facile, servono solo 7 mosse.

 

Ah, sì, praticamente è uguale a prima.

Hai detto bene, sta tutto là il ragionamento! Anche per più piani, non fai altro che ripetere quello che hai fatto già. Guarda, prendiamo 4 piani.

Prima sposti i primi 3 piani sulla colonna in mezzo (è come spostare una torre di 3 piani, e lo sai fare in 7 mosse)

Praticamente ignoro il piano più grande.

Esatto. Finita questa parte, sposti il pezzo più grande sulla terza colonna.

Ah, ho capito, ora di nuovo in 7 mosse sposto la torre da 3 sopra al pezzo grosso. Praticamente utilizzo quello che già so.

Si chiama ragionamento ricorsivo, indovina come si risolve la torre a 5 piani?

Allora, prima devo spostare la torre da 4 sulla seconda colonna, ignorando il pezzo più grande.

E lo abbiamo fatto un attimo fa.

Così ora posso spostare la base della torre alta 5 sulla seconda colonna e poi rimetterci sopra la torre alta 4.

E così hai spostato tutta la torre.

Non è difficile in realtà, ma devi tenere a mente un po’ di cose…

E sì, basta un po’ di pratica; però devi rimanere attento e ricordare a quale torre ti stai interessando in quel momento.

Fammi provare con questa [Risolve la torre a 6 piani]

Ti volevo chiedere. Se sai l’altezza della torre, mi sai dire il numero di mosse necessarie per finire il gioco?

Boh, per 3 o 4 piani lo so, servono 3 e 7 mosse rispettivamente. Con quella da 5 piani…

Ricorda come hai fatto a risolverla.

Allora, prima ho spostato la torre alta 4 sulla seconda colonna, e sono 7 mosse. Poi ho spostato la base grande sulla terza colonna, un’altra mossa quindi. L’ultimo passo è spostare di nuovo la torre alta 4, e sono ulteriori 7 mosse… in totale $$7+7+1$$ mosse, 15!

E la torre alta 5 la risolvi in 31 mosse totali! Prima ne servono 15 per muovere i primi 4 piani, poi una per la base, e poi altre 15 per rimettere la torre sulla base…$$15+15+1$$

Quindi aumentando un piano, devi raddoppiare le mosse del piano precedente e sommare uno?

Sì, esatto. E puoi esprimerlo in maniera sintetica, utilizzando il principio dell’induzione…

Non so cosa sia.

Magari poi ne parliamo… comunque se hai una torre alta $$N$$ piani, si risolve con $$2^N-1$$ mosse.

Ok… forse. Proviamo con $$N=6$$, la tua torre. Si risolve con $$2^6-1$$ mosse… 63!

Perfetto! Allora finalmente posso farti la domanda più importante. Fra quanto tempo finirà il mondo?

Cosa?

Dai, la storia dei monaci! Hanno una torre alta 64 piani, e mettiamo che facciano una mossa al secondo. Fra quanto finiranno?

Ma va va… allora, $$2^{64} -1$$ fa… non a mente… $$18446744073709551615$$ secondi. Ma che numero è!

Ti semplifico la vita, sono 5 miliardi di secoli!

Eeeeh, ne abbiamo di tempo ancora!