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)