Quale disco alla diecimillesima mossa

Testo

Nella soluzione ottima della Torre di Hanoi, con i dischi numerati da $1$ (il più piccolo) in su, alla mossa numero $k$ si sposta il disco il cui numero è $\nu_2(k)+1$, dove $\nu_2(k)$ è l’esponente della massima potenza di $2$ che divide $k$. Quale disco viene mosso alla mossa $10000$?

Soluzione

Fattorizziamo la potenza di $2$ in $10000$: $10000 = 2^4\cdot 625,$ quindi $\nu_2(10000)=4$. Il disco spostato è $\nu_2(10000)+1 = 4+1 = \boxed{5}.$ (Il disco $1$, il più piccolo, si muove a ogni mossa dispari; i dischi più grandi si muovono sempre più di rado.)

Collegamenti

Argomenti: Successioni
Concetti: Potenza · Successione
Metodi: Aritmetica modulare
Competenze: Ragionare per casi
Tipo di esercizio: Calcolo numerico