Le mosse della Torre di Hanoi

Testo

Nel gioco della Torre di Hanoi si spostano $n$ dischi di dimensioni diverse tra tre pioli, un disco alla volta, senza mai porre un disco più grande sopra uno più piccolo. Il numero minimo di mosse soddisfa la ricorsione $M_n = 2M_{n-1}+1$ con $M_1=1$. Quante mosse servono per $n=12$ dischi?

Soluzione

Per spostare $n$ dischi si spostano prima gli $n-1$ superiori su un piolo d’appoggio, poi il disco più grande, poi di nuovo gli $n-1$: da qui $M_n=2M_{n-1}+1$. La soluzione della ricorsione è $M_n = 2^n - 1.$ Per $n=12$: $M_{12} = 2^{12} - 1 = 4096 - 1 = \boxed{4095}.$

Collegamenti

Argomenti: Successioni
Concetti: Potenza · Progressione geometrica · Successione
Metodi: Induzione
Competenze: Usare formule
Tipo di esercizio: Calcolo numerico