Torre di Hanoi
La Torre di Hanoi è un classico rompicapo matematico. Tre pioli, una pila di dischi di dimensioni diverse e due regole rigide: sposta un disco alla volta e non mettere mai un disco più grande su uno più piccolo.
Tre pioli e un cono di dischi
La base ha tre pioli. I dischi sono tutti di dimensioni diverse e si infilano sui pioli. All’inizio l’intero set sta su un piolo, ordinato per dimensione, il più grande in basso e il più piccolo in cima, così la pila forma un cono. L’obiettivo è spostare tutta la torre su un altro piolo.
Le tre regole
1. Sposta un solo disco alla volta. 2. Una mossa prende il disco in cima a una pila e lo mette su un’altra pila, o su un piolo vuoto. 3. Un disco più grande non può mai stare su uno più piccolo. Queste tre regole sono tutto il gioco. Con esse, ogni posizione consentita è un modo di distribuire i dischi sui pioli mantenendo ogni piolo ordinato.
La soluzione più breve è 2ⁿ − 1
Il numero minimo di mosse per risolvere una torre di n dischi è 2ⁿ − 1. Un disco richiede 1 mossa. Due dischi ne richiedono 3. Tre ne richiedono 7, quattro 15 e cinque 31. Ogni nuovo disco raddoppia la soluzione precedente e aggiunge la mossa che porta il disco più grande: se n − 1 dischi richiedono T mosse, n dischi ne richiedono 2T + 1. Questa ricorrenza dà esattamente 2ⁿ − 1. Otto dischi, la torre più alta nell’app PictorX, richiedono 255 mosse. Non esiste un percorso consentito più breve.
Come funziona la ricorsione
Per spostare n dischi dal piolo di partenza al piolo di arrivo, usando il piolo rimanente come appoggio: 1. Sposta gli n − 1 dischi in cima dal piolo di partenza al piolo di appoggio. 2. Sposta il disco più grande dal piolo di partenza direttamente al piolo di arrivo. 3. Sposta gli n − 1 dischi dal piolo di appoggio al piolo di arrivo, sopra il disco più grande. Il passo 2 è consentito perché il disco più grande può stare su qualsiasi piolo. I passi 1 e 3 sono lo stesso rompicapo, con un disco in meno. La chiamata si ferma a un solo disco, che si sposta una volta. Svolgendola si ottengono le 2ⁿ − 1 mosse, e nessun passo mette mai un disco più grande su uno più piccolo.
La leggenda dei 64 dischi d’oro
Il matematico francese Édouard Lucas presentò il rompicapo nel 1883. Insieme raccontò una leggenda su un tempio indiano a Kashi Vishwanath, dove i sacerdoti spostano una pila di 64 dischi d’oro con queste stesse regole. Quando sarà fatta l’ultima mossa, dice la leggenda, il mondo finirà. Sessantaquattro dischi richiedono 2⁶⁴ − 1 mosse: 18.446.744.073.709.551.615. A una mossa perfetta al secondo, giorno e notte, sono circa 585 miliardi di anni. I sacerdoti non finiranno.
Gioca in PictorX
Apri Torre di Hanoi e sul piolo di partenza c’è già una torre di quattro dischi. Quindici mosse sono il minimo. Trascina il disco in cima su un altro piolo, oppure fai clic su un piolo e poi su quello che vuoi. I tasti 1, 2 e 3 fanno lo stesso. Un disco più grande su uno più piccolo viene rifiutato. Dischi va da 1 a 8, così puoi confrontare 1, 3, 7, 15, 31, 63, 127 e 255 con la formula. Passo riproduce una mossa di una soluzione più breve. Risolvi riproduce il resto. «Guarda 3 dischi» mostra la strategia ricorsiva in movimento. Annulla e Ripeti ripercorrono le tue mosse. Salva un PNG, oppure apri la base nell’editor di PictorX.
Domande frequenti
Quali sono le regole della Torre di Hanoi?
Sposta un disco alla volta. Prendi il disco in cima a un piolo e mettilo su un altro piolo. Non mettere mai un disco più grande su uno più piccolo. Tutta la torre parte da un piolo e deve finire su un altro.
Quante mosse richiede la soluzione più breve?
2ⁿ − 1. Un disco è 1 mossa, due dischi 3, tre 7, quattro 15 e cinque 31. Ogni disco aggiunto raddoppia la soluzione precedente e aggiunge una mossa.
Chi ha inventato la Torre di Hanoi?
Il matematico francese Édouard Lucas lo presentò nel 1883. La storia dei sacerdoti e dei 64 dischi d’oro di Kashi Vishwanath è la leggenda che associò al rompicapo.
Quanto tempo richiederebbero 64 dischi?
2⁶⁴ − 1 mosse, cioè 18.446.744.073.709.551.615. A una mossa al secondo sono circa 585 miliardi di anni.
Strumenti correlati
Torre di Hanoi
Sposta una torre di dischi su tre pioli nel browser. Un disco alla volta, mai uno più grande su uno più piccolo. La soluzione più breve è di 2ⁿ − 1 mosse.
Ago di Buffon
Lascia cadere aghi su un pavimento a righe nel browser. Conta gli incroci e guarda l’esperimento di Buffon del 1777 stimare π.
Ago di Buffon
Il problema dell’ago di Buffon del 1777: perché un ago lasciato cadere su righe parallele stima π, come la probabilità 2l/(πd) dell’ago corto nasce dall’area sotto una curva del seno e perché l’esperimento converge lentamente.
Cerchi di moltiplicazione
Collega ogni numero di un cerchio al suo multiplo. Disegna una tabellina, una cardioide o una figura di filo su carta, col gesso o su legno.
La congettura di Collatz
Esplora il problema di Collatz 3n+1 nel browser. Segui le successioni grandine, fai crescere un albero di Collatz geometrico ed esplora con lo zoom il frattale di Collatz continuo.
Formica di Langton
Avvia la formica di Langton nel browser. Osserva simmetria, caos e l’autostrada di 104 passi, poi prova regole multicolore, più formiche, una griglia esagonale e i turmiti.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Gioca alla Torre di Hanoi