114
SPAZIO APERTO
Ecco scattato il ragionamento: sic-
come per spostare 3 dischi, come ave-
vo dimostrato, occorrono 7 mosse,
allora per spostare 4 dischi occorrono
7 mosse per spostare una torre alta 3
dischi, unamossa per spostare il quar-
to disco, e altre 7 mosse per spostare
nuovamente una torre di 3 dischi, per
un totale di 7+1+7=15 mosse (vedi
figure 6-7-8).
Conquesto ragionamento, si capisce
che nel caso di 5 dischi occorreranno
15mosse per spostare i primi 4 dischi,
poi una mossa per spostare il quinto
disco, e altre 15 mosse per spostare
nuovamente una torre di 4 dischi, per
un totale di 15+1+15=31 mosse.
Adesso è facile comprendere
che 6 dischi si possono spostare in
31+1+31=63 mosse, e così via.
Se abbiamo voglia di approfondi-
re, possiamo chiederci se tutti questi
numeri che abbiamo trovato (1, 3,
7, 15, 31,…) hanno una qualche ca-
ratteristica particolare, e la risposta è
affermativa: sono tutte potenze di 2,
al quale viene sottratto 1. Ad esempio,
5 dischi si spostano in 2
5
–1 mosse, e
quindi posso dedurre che 10 dischi si
sposteranno in 2
10
–1 = 1023 mosse.
Ecco, abbiamo visto che uno stu-
dente, sia che abbia dimestichezza
con le potenze, sia che non ne abbia,
può risolvere con le sue conoscenze il
problema della torre di Hanoi.
Purtroppo non ho mai trovato altri
quesiti, ma a questo punto ci si può
chiedere che disco verrà spostato
ad una data mossa, e da che palo a
che palo. La soluzione spero risulti
sorprendente, perché per sapere che
discomuovere, basta scrivere il nume-
ro della mossa in binario, e cercare il
primo 1 dal fondo, e la sua posizione
ci dice che disco verrà spostato. Ad
esempio, di una torre alta 10 dischi,
Figura 7
Figura 8
