La Torre di Hanoi fine. Il gioco della Torre di Hanoi fu inventato dal matematico francese Eduard...
-
Upload
romhilda-corti -
Category
Documents
-
view
226 -
download
0
Transcript of La Torre di Hanoi fine. Il gioco della Torre di Hanoi fu inventato dal matematico francese Eduard...
La Torre di
Hanoi
fine
Il gioco della Torre di Hanoi fu inventato dal
matematico francese Eduard Lucas nel
1883, inizialmente con una torre di otto
dischi
fine
Il problema della Torre di Hanoi deriva da
una antica leggenda indiana che recita così:
«nel grande tempio di Brahma a Benares, su
di un piatto di ottone, sotto la cupola che
segna il centro del mondo, si trovano 64
dischi d'oro puro che i monaci spostano uno
alla volta infilandoli in un ago di diamanti,
seguendo l'immutabile legge di Brahma:
nessun disco può essere posato su un altro
più piccolo.
fine
All'inizio del mondo tutti i 64 dischi erano
infilati in un ago e formavano la Torre di
Brahma. Il processo di spostamento dei
dischi da un ago all'altro è tuttora in corso.
Quando l'ultimo disco sarà finalmente
piazzato a formare di nuovo la Torre di
Brahma in un ago diverso, allora arriverà la
fine del mondo e tutto si trasformerà in
polvere».
fine
fine
Costruiamo il gioco
Preparazione: infilare i dischi in un piolo, in ordine decrescente di diametro
Obiettivo: Spostare l’intera torre da un piolo ad un altro nel minor numero di mosse
Materiale: 3 pioli, una tavoletta di legno in cui inserire i pioli, dischi forati al centro di diametro diverso.
fine
Regole:• Spostare un disco alla volta, da un piolo ad un altro
• Non sovrapporre mai un disco ad uno di diametro minore
Giochiamo
fine
Qual é il numero minimo di mosse per spostare la Torre?
Facendo una mossa al secondo, quanto
tempo almeno sarebbe necessario
per ricostruire la Torre di Brahma, con 64 dischi?
fine
Contatore mosse
Contatore mosse
Con 1 disco
Iniziamo con qualche disco
numero minimo di mosse?
fine
OK
Contatore mosse
Contatore mosse 1
numero mosse:
M1=1
Iniziamo con qualche disco
Con 1 disco
fine
Contatore mosse
Contatore mosse
numero mosse:
M2=?
Iniziamo con qualche disco
Con 2 dischi
numero minimo di mosse?
fine
Contatore mosse
Contatore mosse 1
Iniziamo con qualche disco
Con 2 dischi
numero minimo di mosse?
fine
Contatore mosse
Contatore mosse 2
Iniziamo con qualche disco
Con 2 dischi
numero minimo di mosse?
fine
OK
Contatore mosse
Contatore mosse 3
Iniziamo con qualche disco
Con 2 dischi
fine
OK
Contatore mosse
Contatore mosse 3
numero mosse:
M2=3
Iniziamo con qualche disco
Con 2 dischi
fine
Contatore mosse
Contatore mosse
numero mosse:
M3=?
Iniziamo con qualche disco
Con 3 dischi
numero minimo di mosse?
fine
Contatore mosse
Contatore mosse 1
Iniziamo con qualche disco
Con 3 dischi
numero minimo di mosse?
fine
numero minimo di mosse?
Contatore mosse
Contatore mosse 2
Iniziamo con qualche disco
Con 3 dischi
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 3
Con 3 dischi
abbiamo effettuato 3
mosse
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 4
Con 3 dischi
abbiamo effettuato 4
mosse
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 4
Con 3 dischi
Ah, a destra abbiamo una torre di 2 dischi, quindi
M3 = M2 +1+ le mosse per spostare la torre di 2 dischi
numero mosse:3+1+3?
7 mosse?
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 5
Con 3 dischi
continuiamo
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 6
Con 3 dischi
continuiamo
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 7
Con 3 dischi
OK
fine
Iniziamo con qualche disco
Contatore mosse
Contatore mosse 7
numero mosse:
M3=7
Con 3 dischi
OK
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse
numero mosse:
M4=?
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 1
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 2
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 3
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 4
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 5
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 6
Con 4 dischi
numero minimo di mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 7
Con 4 dischi
Ah, al centro abbiamo una torre di 3 dischi, quindi
M4 = M3 +?
Finora abbiamo
effettuato 7 mosse
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 8
Con 4 dischi
Ah, al centro abbiamo una torre di 3 dischi, quindi
M4 = M3 +1+?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 8
Con 4 dischi
Ah, al centro abbiamo una torre di 3 dischi, quindi
M4 = M3 +1+ le mosse per spostare
la torre centrale
Il numero di mosse è
7+1+7? 15 mosse?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 9
Con 4 dischi
continuiamo
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 10
Con 4 dischi
continuiamo
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 11
Con 4 dischi
continuiamo
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 12
Con 4 dischi
continuiamo
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 13
Con 4 dischi
continuiamo
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 14
Con 4 dischi
continuiamo
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 15
Con 4 dischi
OK
numero mosse:
M4=?
fine
Continuiamo con 4 dischi
Contatore mosse
Contatore mosse 15
Con 4 dischi
OK
numero mosse:
M4=15
fine
Riassumiamo …
15
4
7
3
3
2
1
1
?
5
?
n
fine
… confrontiamo il numero di mosse con le
potenze di 2 …
15731 ?
4321 5dischi
mosse
Potenze di 2
2 4 8 16 32
2 22 23 24 25
fine
… confrontiamo il numero di mosse con le
potenze di 2 …
15731 ?
4321 5
2 4 8 16 32
2 22 23 24 25
Ah! Il numero di mosse è
una potenza di 2 meno
uno
Eh, sì. E l’esponente della potenza é il numero
di dischi della torre
fine
Congettura:Per spostare una torre di D dischi, sono
necessarie almeno M = 2D - 1 mosse
15731 ?
4321 5
2-1 22 -1 23 -1 24 -1 25 -1
D
2D - 1
fine
Peano ci aiuta con ilPrincipio (o Metodo) di Induzione
Matematica(Assioma dell’Induzione)
Il metodo si compone di due passi:1. Verifica che la proprietà vale per un numero naturale (di solito, si prova per D = 0 o D = 1)2. Dimostra che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1
L’assioma afferma che:Se sono soddisfatte queste due condizioni, allora la proprietà vale per ogni numero naturale (a partire dal primo per cui è stata verificata, di solito 0 o 1 ).
fine
Applico nel nostro caso ilPrincipio (o Metodo) di Induzione
Matematica1. Verifico che la proprietà vale per il numero naturale 1 (la prima torre che abbiamo costruito): il numero di mosse dato dalla formula é
21 - 1 = 1 OK
fine
2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.
fine
2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse,allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
fine2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
2d - 1 mosse
fine2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
Aggiungiamo un disco. Quante mosse?
fine2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
Aggiungiamo un disco. Quante mosse?Quelle per spostare la torre di d dischi, cioé 2d-1
fine2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
Aggiungiamo un disco. Quante mosse?Quelle per spostare la torre di d dischi, cioé 2d-1 + 1 per l’ultimo disco
fine2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
Aggiungiamo un disco. Quante mosse?Quelle per spostare la torre di d dischi, cioé 2d-1 + 1 + le mosse per spostare di nuovo la torre di d dischi
fine2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
Aggiungiamo un disco. Quante mosse?Quelle per spostare la torre di d dischi, cioé 2d-1 + 1 + le mosse per spostare di nuovo la torre di d dischi, cioè2d-1 + 1 + 2d-1.
fineAggiungiamo un disco. Quante mosse?Quelle per spostare la torre di d dischi, cioé 2d-1 + 1 + le mosse per spostare di nuovo la torre di d dischi, cioè2d-1 + 1 + 2d-1 = 2* 2d -1 =
2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
fineAggiungiamo un disco. Quante mosse?Quelle per spostare la torre di d dischi, cioé 2d-1 + 1 + le mosse per spostare di nuovo la torre di d dischi, cioè2d-1 + 1 + 2d-1 = 2* 2d -1 =2d+1 -1
Fatto!La proprietà vale per ogni
D !!!
2. Dimostro che se la proprietà vale per un numero naturale d allora la proprietà vale per il successivo di d, cioè d+1.Cioé, dimostro chese una torre di d dischi si sposta in 2d-1 mosse, allora una torre costruita con d+1 dischi si sposta in 2d+1-1 mosse
fine
E cioè ….(clicca qui)
Il numero di mosse é pari a
264-1, cioé ci vogliono 264-1 secondi per
spostare tutta la Torre
Facendo una mossa al secondo, quanto tempo
almeno sarebbe necessario per
ricostruire la Torre di Brahma, con 64 dischi?