...

Document

by user

on
Category: Documents
5

views

Report

Comments

Description

Transcript

Document
fine
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
Costruiamo il gioco
Materiale: 3 pioli, una tavoletta di legno in cui
inserire i pioli, dischi forati al centro di diametro
diverso.
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
fine
Giochiamo
Regole:
• Spostare un disco alla volta, da un piolo ad
un altro
• Non sovrapporre mai un disco ad uno di
diametro minore
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?
Iniziamo con qualche disco
Con 1 disco
numero
minimo di
mosse?
Contatore
mosse
fine
fine
Iniziamo con qualche disco
Con 1 disco
OK
numero
mosse:
M1=1
Contatore
mosse
1
Iniziamo con qualche disco
Con 2 dischi
numero
minimo di
mosse?
numero
mosse:
M2=?
Contatore
mosse
fine
fine
Iniziamo con qualche disco
Con 2 dischi
numero
minimo di
mosse?
Contatore
mosse
1
fine
Iniziamo con qualche disco
Con 2 dischi
numero
minimo di
mosse?
Contatore
mosse
2
fine
Iniziamo con qualche disco
Con 2 dischi
OK
Contatore
mosse
3
fine
Iniziamo con qualche disco
Con 2 dischi
OK
numero
mosse:
M2=3
Contatore
mosse
3
Iniziamo con qualche disco
Con 3 dischi
numero
minimo di
mosse?
numero
mosse:
M3=?
Contatore
mosse
fine
fine
Iniziamo con qualche disco
Con 3 dischi
numero
minimo di
mosse?
Contatore
mosse
1
fine
Iniziamo con qualche disco
Con 3 dischi
numero
minimo di
mosse?
Contatore
mosse
2
fine
Iniziamo con qualche disco
Con 3 dischi
abbiamo
effettuato 3
mosse
Contatore
mosse
3
fine
Iniziamo con qualche disco
Con 3 dischi
abbiamo
effettuato 4
mosse
Contatore
mosse
4
fine
Iniziamo con qualche disco
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?
Contatore
mosse
4
fine
Iniziamo con qualche disco
Con 3 dischi
continuiamo
Contatore
mosse
5
fine
Iniziamo con qualche disco
Con 3 dischi
continuiamo
Contatore
mosse
6
fine
Iniziamo con qualche disco
Con 3 dischi
OK
Contatore
mosse
7
fine
Iniziamo con qualche disco
Con 3 dischi
OK
numero
mosse:
M3=7
Contatore
mosse
7
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
numero
mosse:
M4=?
Contatore
mosse
fine
fine
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
Contatore
mosse
1
fine
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
Contatore
mosse
2
fine
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
Contatore
mosse
3
fine
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
Contatore
mosse
4
fine
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
Contatore
mosse
5
fine
Continuiamo con 4 dischi
Con 4 dischi
numero
minimo di
mosse?
Contatore
mosse
6
fine
Continuiamo con 4 dischi
Con 4 dischi
Ah, al centro
abbiamo una torre
di 3 dischi, quindi
M4 = M3 +?
Finora
abbiamo
effettuato 7
mosse
Contatore
mosse
7
fine
Continuiamo con 4 dischi
Con 4 dischi
Ah, al centro
abbiamo una torre
di 3 dischi, quindi
M4 = M3 +1+?
Contatore
mosse
8
fine
Continuiamo con 4 dischi
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?
Contatore
mosse
8
fine
Continuiamo con 4 dischi
Con 4 dischi
continuiamo
Contatore
mosse
9
fine
Continuiamo con 4 dischi
Con 4 dischi
continuiamo
Contatore
mosse
10
fine
Continuiamo con 4 dischi
Con 4 dischi
continuiamo
Contatore
mosse
11
fine
Continuiamo con 4 dischi
Con 4 dischi
continuiamo
Contatore
mosse
12
fine
Continuiamo con 4 dischi
Con 4 dischi
continuiamo
Contatore
mosse
13
fine
Continuiamo con 4 dischi
Con 4 dischi
continuiamo
Contatore
mosse
14
fine
Continuiamo con 4 dischi
Con 4 dischi
OK
numero
mosse:
M4=?
Contatore
mosse
15
fine
Continuiamo con 4 dischi
Con 4 dischi
OK
numero
mosse:
M4=15
Contatore
mosse
15
fine
Riassumiamo …
1
2
3
4
5
n
1
3
7
15
?
?
fine
… confrontiamo il numero di
mosse con le potenze di 2 …
dischi
1
2
3
4
5
mosse
1
3
7
15
?
Potenze
di 2
2
22
23
24
25
2
4
8
16
32
fine
… confrontiamo il numero di
mosse con le potenze di 2 …
Ah! Il numero
di mosse è
una potenza
di 2 meno
uno
1
2
3
4
5
1
3
7
15
?
2
22
23
24
25
2
4
8
16
32
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
D
2D - 1
1
2
3
4
5
1
3
7
15
?
2-1
22 -1
23 -1
24 -1
25 -1
fine
Peano ci aiuta con il
Principio (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 il
Principio (o Metodo) di Induzione
Matematica
1. 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 che
se 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
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 che
se una torre di d dischi si sposta in 2d1 mosse,
allora una torre costruita con d+1
dischi si sposta in 2d+1-1 mosse
2d - 1
mosse
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 che
se una torre di d dischi si sposta in 2d1 mosse,
allora una torre costruita con d+1
dischi si sposta in 2d+1-1 mosse
Aggiungiamo un disco.
Quante mosse?
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 che
se una torre di d dischi si sposta in 2d1 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
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 che
se una torre di d dischi si sposta in 2d1 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
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 che
se una torre di d dischi si sposta in 2d1 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
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 che
se una torre di d dischi si sposta in 2d1 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.
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 che
se una torre di d dischi si sposta in 2d1 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 =
2* 2d -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 che
se una torre di d dischi si sposta in 2d1 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 =
2* 2d -1 =
2d+1 -1
Fatto!
La proprietà
vale per ogni D
!!!
fine
fine
Facendo una mossa al
secondo, quanto tempo
almeno sarebbe
necessario per
ricostruire la Torre di
Brahma, con 64 dischi?
Il numero di
mosse é pari
a 264-1, cioé ci
vogliono 264-1
secondi per
spostare tutta
la Torre
E cioè ….(clicca
qui)
Fly UP