Torre di Hanoi

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Torre di Hanoi ad otto dischi

La Torre di Hanoi (anche conosciuta come Torre di Lucas dal nome del suo inventore) è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti.

Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti i dischi su un paletto diverso, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.

Origini[modifica | modifica wikitesto]

Il gioco fu inventato nel 1883[1] dal matematico francese Édouard Lucas che diffuse il gioco sotto lo pseudonimo di N. Claus de Siam, mandarino del collegio di Li-Sou-Stian.[2] La leggenda secondo la quale in un tempio Indù alcuni monaci sono costantemente impegnati a spostare su tre colonne di diamante 64 dischi d'oro secondo le regole della Torre di Hanoi (a volte chiamata Torre di Brahmā), è stata inventata dalla ditta che per prima ha messo in commercio il rompicapo. La leggenda narra che quando i monaci completeranno il lavoro, il mondo finirà. Esistono anche versioni videoludiche del rompicapo.[3][4][5][6]

Soluzione[modifica | modifica wikitesto]

Soluzione Torre di Hanoi a quattro dischi

La proprietà matematica base è che il numero minimo di mosse necessarie per completare il gioco è , dove n è il numero di dischi. Ad esempio avendo 3 dischi, il numero di mosse minime è 7. Di conseguenza, secondo la leggenda, i monaci di Hanoi dovrebbero effettuare almeno 18.446.744.073.709.551.615 mosse prima che il mondo finisca, essendo . In altre parole, anche supponendo che i monaci facciano una mossa al secondo il mondo finirà tra 5.845.580.504 secoli, un tempo così lungo che quando il sole diverrà una gigante rossa e brucerà la Terra, il gioco non sarà stato completato.[7]

La soluzione generale è data dall'algoritmo seguente.

Algoritmo ricorsivo[modifica | modifica wikitesto]

La soluzione base del gioco della torre di Hanoi si formula in modo ricorsivo.[8][9]

Siano i paletti etichettati con A, B e C, e i dischi numerati da 1 (il più piccolo) a n (il più grande). L'algoritmo si esprime come segue:

  1. Sposta i primi n-1 dischi da A a B. (Questo lascia il disco n da solo sul paletto A)
  2. Sposta il disco n da A a C
  3. Sposta n-1 dischi da B a C

Per spostare n dischi si richiede di compiere un'operazione elementare (spostamento di un singolo disco) ed una complessa, ossia lo spostamento di n-1 dischi. Tuttavia anche questa operazione si risolve nello stesso modo, richiedendo come operazione complessa lo spostamento di n-2 dischi. Iterando questo ragionamento si riduce il processo complesso ad uno elementare, ovvero lo spostamento di n-(n-1)=1 disco.

Questo è un algoritmo ricorsivo,[8] di complessità esponenziale.

È interessante notare che il rompicapo è risolvibile per qualsiasi "n", con una dimostrazione per ricorrenza: Supponiamo di avere una torre in A composta da N dischi, e supponiamo che N sia il numero massimo di dischi ammessi per risolvere il gioco. Al termine dello spostamento della torre da A a B, aggiungiamo un ulteriore disco ad A, di grandezza pari a N+1, e ipotizziamo che questo disco sia stato fermo tutto il tempo sotto gli altri. A questo punto, spostiamo semplicemente il disco da A a C, e certamente riusciremo a spostare la torre da B a C, seguendo gli stessi passaggi che si sono resi necessari per spostarla da A a B. Avendo dimostrato che una torre di N dischi è spostabile da una colonna all'altra, è dimostrato che si può spostare anche una torre di N+1 dischi.

Note[modifica | modifica wikitesto]

  1. ^ (EN) Lucas summary, su www-history.mcs.st-and.ac.uk.
  2. ^ (EN) The Tower of Hanoi, su cs.wm.edu.
  3. ^ (EN) Hanoi: Sega Dreamcast Game Console (Animated), su kernelthread.com.
  4. ^ (EN) Hanoi: Nintendo Gameboy Advance Handheld (Animated), su kernelthread.com.
  5. ^ Francesco Sblendorio, Torri di Hanoi per MS-DOS & Windows, su sblendorio.eu, 1996.
  6. ^ (EN) Francesco Sblendorio, Towers of Hanoi - CP/M generic version and C128 specific, su github.com, 2015.
  7. ^ Progetto Polymath - La torre di Hanoi, su areeweb.polito.it.
  8. ^ a b (EN) Tower of Hanoi, su cut-the-knot.org.
  9. ^ www.matematicamente.it (PDF), su matematicamente.it.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica