Torre di Hanoi

IL GIOCO

Il gioco consiste nello spostare i dischi (che possono essere in numero variabile) dalla colonnina, dove sono impilati dal più grande al più piccolo, in una delle altre due seguendo le seguenti regole:
  • si deve spostare un disco alla volta
  • non si può mai spostare un disco più grande sopra uno più piccolo
  L'abilità del giocatore consiste nel compiere l'operazione richiesta nel minimo numero di mosse possibile. Provare a giocare con 1, con 2, con 3 dischi e scrivere in ciascun caso qual è il numero minimo di mosse da compiere. Poi aumentare ancora il numero dei dischi e annotare in una tabella i risultati ottenuti. Cercare anche di descrivere la strategia che si deve seguire di volta in volta per ottenere il numero minimo di mosse.

Gioca e prova a compilare la seguente tabella:

Numero di dischi = nNumero minimo di mosse =M
1 1
 2
 3
 4
 5

Hai individuato un metodo per risolvere il gioco nel minor numero di mosse possibile? Prova a descriverlo facendo anche un esempio:

Sapresti suggerire un metodo per calcolare il numero minimo di mosse con 6 dischi, senza dover provare a giocare?