Universita degli Studi di Torino

Corso di Laurea in Matematica

ROMPICAPI CELEBRI

Anna Camperi

matr. 283464

Indice

Introduzione 3

1 Il principio di induzione matematica 7

2 I quadrati magici 8

2.1 La leggenda del Lo Shu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Metodi per costruire quadrati magici . . . . . . . . . . . . . . . . . . . . . 11

Costruzione di quadrati magici di ordine dispari . . . . . . . . . . . . . . . 12

Costruzione di quadrati magici di ordine pari, multiplo di 4 . . . . . . . . . 16

3 La torre di Hanoi 18

3.1 La leggenda della torre di Brahma . . . . . . . . . . . . . . . . . . . . . . . 18

3.2 Dimostrazione per induzione . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Bibliografia 25

Sitografia 26

2

Introduzione

Rompicapi e problemi matematici sono stati inventati sin dall’antichita e se ne trovano esempi

nelle culture di ogni epoca. La prima forma di rompicapo ad essersi sviluppata e stata l’in-

dovinello: se ne trovano infatti numerosi nell’Antico Testamento, nella mitologia greca e in

quella egizia. Uno dei piu conosciuti e contenuto nel Papiro di Rhind, che risale al 1850 a.C.

circa:

Sette case contengono sette gatti. Ogni gatto uccide sette topi.

Ogni topo avrebbe mangiato sette spighe di grano.

Ogni spiga di grano avrebbe prodotto sette misure di farina.

Qual e il totale?

Problemi simili appaiono nel Liber Abaci del matematico Leonardo Pisano, detto Fibonacci

(1180 - 1250 c.a), autore anche del celebre Problema dei conigli:

Un tale pose una coppia di conigli in un luogo circondato da pareti. La coppia inizio

a riprodursi a partire dalla fine del primo mese e ogni mese genero una nuova coppia

di conigli. Tutte le altre coppie, nate nel corso dell’anno, iniziarono a riprodursi dal

secondo mese dopo la nascita e anch’esse generarono una nuova coppia ogni mese.

Quante coppie di conigli nascono complessivamente in un anno?

Oltre agli indovinelli, hanno avuto diffusione sin dai tempi antichi anche rompicapi logici, come

i paradossi, e quesiti di tipo matematico, tra cui il problema della costruzione dei quadrati

magici, che analizzeremo piu in dettaglio in seguito, e il Problema dei buoi di Archimede,

che richiede di calcolare la composizione della mandria di buoi del Dio Sole: la soluzione di tale

enigma, che i matematici alessandrini non riuscivano a risolvere, puo essere ricondotta ad un

sistema di sette equazioni con otto incognite, che ammette infinite soluzioni.

La tradizione dei rompicapi e persistita durante tutto il Medio Evo per arrivare fino ai giorni

nostri: Carlo Magno (742-814), fondatore del Sacro Romano Impero, era cosı appassionato

3

dai problemi matematici da assumere un esperto perche ne creasse appositamente per lui. La

persona cui venne affidato l’incarico fu il celebre studioso ed ecclesiastico inglese Alcuino, che

viene ancor’oggi ricordato per l’enigma dell’attraversamento del fiume, rompicapo che ha

avuto importanti influssi sullo studio della logica e ha avuto un ruolo fondamentale per la nascita

del calcolo combinatorio:

Un viaggiatore si avvicina alla sponda di un fiume con un lupo, una capra e un cavolo.

Con grande disappunto, nota che c’e solo una barca per attraversare il fiume, sulla

quale c’e spazio solo per due: il viaggiatore e uno dei due animali oppure il cavolo.

Come il viaggiatore ben sa, se li lascia insieme da soli, la capra mangera il cavolo e

il lupo mangera la capra. Il lupo pero non mangia i cavoli. Come puo il viaggiatore

portare tutti gli animali e il cavolo sull’altra riva nel minor numero possibile di viaggi

avanti e indietro?

Nel XVI secolo Niccolo Tartaglia propose una versione interessante dell’enigma. I protagonisti

sono tre spose ed i loro mariti gelosi:

Tre bellissime spose con i loro mariti giungono nei pressi di un fiume. La barca che

li trasportera sull’altra riva puo ospitare soltanto due persone. Per evitare situazioni

compromettenti, gli attraversamenti devono essere organizzati in modo che nessuna

donna venga lasciata sola con un uomo a meno che non sia presente anche suo marito.

Come si puo ottenere questo risultato, sapendo che la barca puo essere condotta da

qualsiasi uomo o qualsiasi donna?

Due secoli dopo, il genio svizzero Leonardo Eulero (1707 - 1783) risolse un quesito matematico

ispirato ad una situazione concreta: il problema dei sette ponti di Konigsberg.

La citta di Konigsberg, facente parte in passato della Prussia Orientale ed ora della Repubblica

Russa, con il nome di Kaliningrad, famosa per aver dato i natali al filosofo Immanuel Kant

(1724-1804), e percorsa dal fiume Pregel e dai suoi affluenti e presenta due estese isole che sono

connesse tra di loro e con le due aree principali della citta da sette ponti. Ci si pone la questione

se sia possibile seguire un percorso che attraversa ogni ponte un’unica volta e ritornare al punto

di partenza.

Nel 1736 Eulero lavoro al problema, dimostrando in modo rigoroso che il percorso ipotizzato era

impossibile. Il grande merito del matematico svizzero fu quello di aver riformulato il problema

astraendo dalla situazione specifica di Konigsberg, dando un prezioso contributo alla nascita di

una nuova branca della matematica, nota come teoria dei grafi.

Oltre al problema dei sette ponti, Eulero affronto anche per il problema dei 36 ufficiali, che

puo essere cosı formulato:

E possibile disporre 36 ufficiali, provenienti a sei a sei da sei diversi reggimenti ed

aventi, in ognuno di essi, sei gradi militari differenti, in 6 righe e 6 colonne di 6

ufficiali ciascuna, in modo tale che in ogni riga e in ogni colonna ci sia un ufficiale di

ogni reggimento e di ogni grado?

Eulero congetturo che il problema non avesse soluzione, ma ad una dimostrazione rigorosa si

arrivera solo nel 1901, ad opera del matematico francese M. Tarry. Eulero riteneva inoltre che

tale congettura valesse anche per ogni n = 4 · k +2,∀k ∈ N; tale ipotesi venne smentita nel 1960

dai matematici Bose, Parker e Shrikhande che provarono che la congettura di Eulero e falsa per

tutti i valori n = 4 · k + 2 con n > 6.

Nel 1800, il matematico francese Edouard Lucas (1842 - 1891) propose il rompicapo della torre

di Hanoi, che verra approfondito in seguito, e il problema delle otto regine; quest’ultimo,

consisteva nel trovare il modo di disporre otto regine su una scacchiera in modo tale che nessuna

regina fosse minacciata dalle altre, ovvero in modo tale che ogni riga, ogni colonna ed ogni

diagonale contenesse esattamente una regina (poiche la regina puo spostarsi in orizzontale, in

verticale e in diagonale di un qualsiasi numero di caselle.)

Sempre del 1800 e il famoso gioco del quindici, creato nel 1870 da Sam Loyd. Esso consiste di

quindici caselle, numerate da 1 a 15 che possono scivolare liberamente in un piano, all’interno di

un quadrato 4× 4. Le quindici tessere sono disposte in serie numerica regolare, ma con i numeri

14 e 15 scambiati.Il gioco consiste nello scambiare le tessere, muovendole una alla volta, fino ad

arrivare ad una configurazione con tutte le caselle in serie numerica crescente.

Loyd offrı un premio di mille dollari a chi fosse riuscito a trovare la soluzione del gioco, ben

sapendo che questa non esisteva. Infatti, ricorrendo alla teoria delle permutazioni, se definiamo

scambio ogni situazione in cui un numero e preceduto da un numero piu grande, data una

configurazione qualsiasi e sufficiente contare il numero di scambi necessari per arrivare alla

soluzione finale: soltanto se il numero di scambi e pari il gioco e risolubile. Poiche non e possibile

passare da una configurazione pari ad una dispari, il gioco proposto da Loyd risulta impossibile,

in quanto la configurazione iniziale presenta un unico scambio (15 14), mentre quella finale non

ne ha. Se, invece, il 14 ed il 15 sono in ordine crescente, il gioco e risolubile.

Un secolo dopo la nascita del gioco di Loyd, l’architetto ungherese Erno Rubik creo un rompicapo

ancora piu sofisticato, che e diventato il giocattolo piu venduto della storia. Il cubo di Rubik

e composto da 3× 3× 3 cubi piu piccoli; le facce di quest’ultimi sono di diverso colore e quelle

del cubo piu grande sono imperniate in modo da poter ruotare in varie dimensioni. Lo scopo e

ottenere una configurazione in cui ogni faccia del cubo piu grande sia tutto dello stesso colore.

In questa tesina, analizzeremo piu in dettaglio i problemi dei quadrati magici e della torre di

Hanoi. Nel prossimo capitolo introdurremo il Principio di induzione matematica, che ci

servira per risolvere entrambi i rompicapi.

Capitolo 1

Il principio di induzione matematica

Il Principio di induzione matematica e una tecnica dimostrativa che fa esplicito riferimento

ai numeri naturali.

PRINCIPIO DI INDUZIONE MATEMATICA (PRIMA FORMA):

Proposizione 1.0.1. Sia (P (n)) una successione di proposizioni tali che

1) P (n0) e vera (passo base dell’induzione)

2) La verita di P (k) implica la verita di P (k + 1), k ≥ n0 (ipotesi induttiva)

Allora P (n) e vera , ∀n ≥ n0

Dimostrazione. Sia {S = x > n0/P (x)efalsa} . Supponiamo per assurdo che S non sia vuoto.

Per l’assioma del buon ordinamento di N, S ha un primo elemento, che indichiamo con m.

Consideriamo ora la proposizione P (m) : poiche m ∈ S, P (m) e falsa; inoltre, poiche m e il

primo elemento di S, m− 1 /∈ S (e m− 1 ≥ n0), quindi la proposizione P (m− 1) e vera e la 2)

ci dice allora che P (m) e vera . Abbiamo una contraddizione, dunque S e vuoto .

PRINCIPIO DI INDUZIONE MATEMATICA (SECONDA FORMA):

Proposizione 1.0.2. Sia (P (n)) una successione di proposizioni tali che

1) P (n0) e vera (passo base dell’induzione)

2) La verita di P (k), ∀0 ≤ k ≤ m, implica la verita di P (m) (ipotesi induttiva)

Allora P (n) e vera , ∀n ≥ n0

7

Capitolo 2

I quadrati magici

2.1 La leggenda del Lo Shu

Un quadrato magico di ordine n e una tabella quadrata contenente i primi n2 numeri interi,

in modo tale che la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le

diagonali dia sempre lo stesso numero, che viene detto costante magica.

Il primo quadrato magico risale all’antica Cina, ai tempi della dinastia Shang (2000 a.C. circa)

quando, secondo la leggenda, ci fu una grande inondazione. Per placare l’ira del fiume Lo, la

popolazione locale offrı sacrifici al dio del fiume. Malgrado cio, ogni volta appariva una tartaru-

ga che scivolava fuori dal fiume e passava con noncuranza vicino al sacrificio. La popolazione

considerava la tartaruga un segno del dio che continuava a rifiutare i sacrifici offerti. Un giorno

un bambino noto che c’era un quadrato sul guscio della tartaruga. Al suo interno vi erano i

primi nove numeri sistemati in tre righe e tre colonne. Il bambino osservo anche che i numeri

distribuiti nelle righe, nelle colonne e nelle due diagonali, se sommati, davano tutti 15 come

risultato. E fu cosı che la popolazione capı che quello era il numero di sacrifici da raggiungere

per placare il dio del fiume.

Il quadrato descritto nella leggenda, noto come Lo Shu e un quadrato magico di ordine 3, la

cui costante magica e 15:

8 3 4

1 5 9

6 7 2

8

Infatti:

• Somma delle righe:

(1) 8 + 3 + 4 = 15

(2) 1 + 5 + 9 = 15

(3) 6 + 7 + 2 = 15

• Somma delle colonne:

(1) 8 + 1 + 6 = 15

(2) 3 + 5 + 7 = 15

(3) 4 + 9 + 2 = 15

• Somma delle diagonali:

(1) 8 + 5 + 2 = 15

(2) 4 + 5 + 6 = 15

Dalla Cina, i quadrati magici viaggiarono verso il Giappone e l’India, dove apparve la prima

traccia di quadrato magico di ordine 4.

L’introduzione dei quadrati magici in Europa si deve a Emmanuel Moschopulos (1265 c.a.-1316),

ma il primo ad approfondire l’argomento fu Cornelio Agrippa (1486-1535). Molti quadrati magi-

ci si supponevano dotati di particolari virtu magiche e venivano utilizzati per costruire talismani.

Nel XVI secolo questi particolari quadrati connobbero un connubio con l’arte, come nel caso del

celebre quadrato di Albrecth Durer (1471-1528) nella sua incisione Melancholia:

Il quadrato magico rappresentato in quest’opera e il seguente:

16 3 2 13

5 10 11 8

9 6 7 12

4 15 14 1

Come si puo facilmente verificare, la costante magica di questo quadrato e 34.

Nel Seicento, il matematico francese Frenicle de Bessy (1605-1665) calcolo il numero dei quadrati

magici di ordine 4: sono 880, con somma costante 34 su righe, colonne e diagonali. Si dovette

invece attendere l’avvento del computer per allargare l’indagine a quadrati magici di ordine

superiore e scoprire cosı, nel 1973, che i quadrati magici di ordine 5 sono 275.305.224. Ancora

oggi non e noto il numero esatto dei quadrati magici di ordine 6, che dovrebbe essere dell’ordine

di 1, 7754 · 1019.

2.2 Metodi per costruire quadrati magici

Per costruire un quadrato magico e necessario anzitutto trovare una formula generale per de-

terminare la costante magica. Un quadrato magico si ottiene da una serie di n2 numeri interi

consecutivi. L’ultimo numero della serie e quindi n2, dove n e l’ordine del quadrato. Calcoliamo

prima di tutto la somma dei primi n2 numeri interi, ricordando che la somma dei primi n interi

e data dalla formula

1 + 2 + . . . + n =n · (n + 1)

2

Proviamo la validita di tale formula utilizzando il principio di induzione matematica (vedi

Proposizione 1.0.1):

Proposizione 2.2.1. La somma dei primi n interi e

1 + 2 + . . . + n =n · (n + 1)

2

Dimostrazione. Dobbiamo verificare che sono soddisfatte le condizioni 1) e 2) della propo-

sizione 1.0.1:

1) P (1) e vera, infatti 1·21 = 1

2) Supponiamo ora che P (n) sia vera, cioe che 1 + 2 + . . . + n = n·(n+1)2 e proviamo che

anche P (n+1) e vera, cioe 1+2+. . .+n+(n+1) = (n+1)·(n+2)2 , usando l’ipotesi induttiva:

1 + 2 + . . . + n + (n + 1) =n · (n + 1)

2+ (n + 1) =

(n + 1) · (n + 2)2

La somma dei primi n2 interi sara dunque

n2 ·(n2 + 1

)2

Per trovare la costante magica, bastera dividere la somma dei primi n2 interi appena trovata

per n. La formula generale e quindi

n2 ·(n2 + 1

)2 · n

=n ·

(n2 + 1

)2

Nel caso del Lo Shu la costante magica e proprio 15, infatti

n ·(n2 + 1

)2

=3 ·

(32 + 1

)2

=3 · 10

2= 15

Per costruire quadrati magici si procede in gran parte per tentativi ed errori, ma in alcuni casi

e possibile derivare un algoritmo. Analizzeremo questi casi nelle pagine seguenti.

Costruzione di quadrati magici di ordine dispari

Per capire come bisogna procedere per costruire quadrati di ordine dispari, ritorniamo all’esem-

pio del Lo Shu. Tutti i quadrati di ordine dispari hanno una cella centrale; il numero che occupa

questa cella puo essere determinato calcolando su quante righe, colonne e diagonali si ripete

all’interno del quadrato. Nel caso del Lo Shu e presente in una riga, in una colonna e nelle due

diagonali, cioe quattro volte. Contiamo ora quante sono le possibili terzine di numeri compresi

tra 1 e 9 (senza ripetizione) la cui somma sia 15. Abbiamo:

9 + 5 + 1

9 + 4 + 2

8 + 6 + 1

8 + 5 + 2

8 + 4 + 3

7 + 6 + 2

7 + 5 + 3

6 + 5 + 4

Abbiamo stabilito che il numero centrale compare in quattro terzine. L’unico numero che nella

lista precedente compare quattro volte e il 5, che e quindi il numero centrale.

Un algoritmo per costruire un quadrato magico di ordine dispari viene attribuito al matematico

Simon de la Loubere (1642-1729) che lo ideo nel 1693, benche probabilmente lo studioso ne fosse

venuto a conoscenza nel corso di uno dei suoi viaggi in Asia. Serviamoci del suo algoritmo su

un quadrato di ordine 5, cioe un quadrato che contiene i primi 25 numeri, con costante magica

pari a 65:

1. Posizioniamo l’1 nella cella centrale in alto:

2. Procediamo in diagonale verso destra e verso l’alto, e posizioniamo la cifra successiva, il

2, in un quadrato immaginario al di fuori del quadrato vero. Visto che il 2 si trova al di

fuori del quadrato, portiamolo alla fine della colonna alla quale allineato:

3. Mettiamo la cifra successiva, il 3, verso l’alto in diagonale, alla destra del 2:

4. Iteriamo il procedimento per il numero successivo, il 4, inserendolo nella cella immaginaria

che si trova in alto e alla destra del 3 e poi spostiamolo all’estremita oppsta della riga:

5. Inseriamo il numero 5 in alto a destra rispetto al numero 4:

6. Lo stesso tipo di movimento non puo essere eseguito per inserire il numero 6, in quanto

la cella che si trova diagonalmente verso l’alto alla destra del 5 risulta gia occupata. Il 6

viene quindi scritto al di sotto del 5:

7. Procedendo allo stesso modo per i numeri rimanenti si otterra il seguente quadrato:

Il procedimento e lo stesso per ogni altro quadrato di ordine dispari. Riportiamo di seguito i

passaggi che si devono compiere per costruire il Lo Shu:

1

1

2

1

3

2

1

3

4 2

1

3 5

4 2

1 6

3 5

4 2

1 6

3 5 7

4 2

8 1 6

3 5 7

4 2

8 1 6

3 5 7

4 9 2

Costruzione di quadrati magici di ordine pari, multiplo di 4

Per costruire un quadrato di ordine 4, per prima cosa disegnamo le linee di intersezioni attra-

verso le diagonali:

Disponiamo quindi i numeri come se fossero in successione, lasciando in bianco le celle attraver-

sate dalle linee di intersezione. Iniziamo con l’1 nella cella in alto a sinistra: poiche tale cella e

attraversata dalla diagonale, non scriviamo nulla. Passiamo a quella successiva alla sua destra

e scriviamo il numero successivo, cioe il 2. Anche la terza cella e vuota, quindi inseriamo il

numero 3. La quarta cella e attraversata dalla diagonale, pertanto non scriviamo alcun numero.

Passiamo quindi alla seconda riga del quadrato e procediamo in modo analogo a quanto visto

per la prima riga fino a raggiungere l’ultima cella nell’angolo in basso a destra.

Iniziamo ora dall’angolo in basso a destra e spostiamoci in orizzontale verso sinistra, inserendo

i numeri soltanto nelle celle attraversate dalle diagonali. Cominciamo quindi mettendo l’1 nella

cella in basso a destra. Le due celle alla sua sinistra sono piene, quindi raggiungiamo l’angolo

in basso a sinistra e inseriamo il numero successivo, che e il 4, poiche il 2 e il 3 sono gia stati

inseriti. Procedendo nel modo indicato, si ottiene il seguente quadrato:

Un quadrato di ordine 8, invece, andra considerato come l’insieme di quattro quadrati di or-

dine 4. Quindi, in questo caso, bisogna disegnare le diagonali in ognuno dei quattro quadranti.

Dopo averle disegnate, si procede nel modo indicato per un quadrato di ordine 4, e si ottiene il

quadrato seguente:

In generale, quindi, un quadrato di ordine 4 · n con n ≥ 2, andra considerato come l’insieme di

2 ·n quadrati di ordine 4. Quindi, una volta disegnate le diagonali di ogni quadrante, si procede

nel modo indicato per un quadrato di ordine 4.

Capitolo 3

La torre di Hanoi

3.1 La leggenda della torre di Brahma

Narra una leggenda indiana che all’inizio dei tempi, Brahma porto nel grande tempio di Benares,

sotto la cupola d’oro che si trova nel centro del mondo, tre colonnine di diamante e sessantaquat-

tro dischi d’oro, collocati su una di queste colonnine e ordinati dal piu grande in basso al piu

piccolo in alto. E la sacra torre di Brahma che vede impiegati, giorno e notte, i sacerdoti del

tempio a trasferire la torre di dischi dalla prima alla terza colonnina. Essi devono seguire regole

precise, dettate dallo stesso Brahma, che richiedono di spostare un disco alla volta, facendo in

modo che nessun disco sia mai posato su uno di diametro inferiore.

Quando i sacerdoti avranno completato il loro lavoro e l’intera torre sara trasferita sulla terza

colonnina, la torre e il tempio crolleranno e il mondo avra fine. Questa suggestiva leggenda e

in realta un’invenzione del matematico francese Edouard Lucas, che se ne servı nel 1883 per

lanciare nel modo piu originale il rompicapo da lui inventato: la torre di Hanoi.

18

Il gioco, che nella versione originale consta di tre colonnine e otto dischi infilati in una di queste

in ordine decrescente, consiste nello spostare la torre di dischi dalla colonnina in cui si trova

ad una delle colonnine libere, utilizzando la colonnina rimanente come supporto. Le regole del

gioco sono quelle imposte da Brahma nella leggenda: si puo spostare soltanto un disco alla volta

e ogni disco non puo mai avere sopra di se un disco piu grande.

Ci chiediamo quale sia il numero minimo di mosse mn necessario per spostare l’intera torre.

Nel caso banale di un solo disco, basta una mossa per spostare il disco dal piolo A al piolo B,

cioe m1 = 1.

Se abbiamo due dischi, sono necessari tre movimenti: si sposta il disco superiore sul piolo C,

il disco piu grande sul piolo B e quindi il disco piu piccolo sopra quello piu grande, quindi

m2 = 2 ·m1 + 1.

Vediamo ora in dettaglio quante mosse bisogna compiere nel caso di una torre formata da tre

dischi.

Innanzitutto, dobbiamo spostare il disco superiore su B

e quello di mezzo su C

Spostiamo poi il disco in B sopra quello in C

e il disco in A sul piolo B

Spostiamo ora il disco superiore di C in A

il disco in C su B

ed infine il disco in A su B

Per una torre di tre dischi occorrono quindi sette mosse, cioe m3 = 2 ·m2 + 1. Se sappiamo

risolvere il problema con tre dischi, lo sapremo risolvere anche con quattro: sara infatti sufficiente

spostare dapprima i tre dischi superiori sulla seconda colonnina con il procedimento gia noto,

poi il quarto disco sulla terza colonnina ed infine si collocheranno su quest’ultimo gli altri tre

dischi, cioe m4 = 2 ·m3 + 1.

In generale, nel caso di una torre di n dischi, il procedimento e del tutto analogo: si spostano

i primi n− 1 dischi sulla terza colonnina

si sposta l’n-esimo disco dalla prima alla seconda colonnina

infine si sposta la torre di n− 1 dischi sulla seconda colonnina

Detto n il numero dei dischi, avremo quindi che il numero minimo di mosse necessario per

spostare l’intera torre e:

mn = 2 ·mn−1 + 1

Per ottenere una formula esplicita per n procediamo per iterazione:

mn = 2 ·mn−1 + 1 =

= 2 · (2 ·mn−2 + 1) + 1 =

= 22 ·mn−2 + 2 + 1 =

= 22 · (2 ·mn−3 + 1) + 2 + 1 =

= 23 ·mn−3 + 22 + 2 + 1 =

= . . .

= 2n−1 ·mn−(n−1) + 2n−2 + . . . + 22 + 2 + 1 =

= 2n−1 ·m1 + 2n−2 + . . . + 22 + 2 + 1 =

= 2n−1 + 2n−2 + . . . + 22 + 2 + 1 =

= 2n − 1

dove l’ultima uguaglianza discende dalla formula della somma dei primi n termini di una suc-

cessione geometrica.

Pertanto, il minimo numero di mosse necessario per spostare una torre di n dischi e

2n − 1 (3.1)

Per la torre di Brahma, formata da 64 dischi, occorrerebbero quindi

264 − 1 = 18.446.744.073.709.551.615

movimenti. Se calcoliamo un movimento al secondo e se teniamo presente che in un secolo ci

sono 100 · 365, 24 · 24 · 60 · 60 ≈ 3, 16 · 109 secondi, per portare a termine l’operazione i sacerdoti

del tempio di Benares impiegherebbero piu di cinque miliardi di secoli.

3.2 Dimostrazione per induzione

Dimostriamo la validita della (3.1) utilizzando il principio di induzione matematica (vedi

Proposizione 1.0.1):

Proposizione 3.2.1. Il numero minimo di mosse necessario per spostare una torre di n dischi

e

2n − 1

Dimostrazione. Indichiamo con M(n) il numero minimo di mosse. Dobbiamo verificare che sono

soddisfatte le condizioni 1) e 2) della proposizione 1.0.1:

1) La formula e chiaramente vera quando n = 1. Infatti, M(1) = 21 − 1 = 1.

2) Supponiamo ora che la formula valga per n dischi, cioe che M(n) = 2n − 1 e proviamo che e

verificata anche per n + 1, cioe che M(n + 1) = 2n+1 − 1.

Nel caso di n + 1 dischi, incominciamo a spostare gli n dischi superiori dalla prima alla seconda

colonnina: per effettuare questo spostamento, abbiamo supposto che siano necessari M(n) =

2n − 1 movimenti. Spostiamo poi il disco piu grande dalla prima alla terza colonnina (oper-

azione che richiede un unico movimento), quindi spostiamo gli n dischi dalla seconda alla terza

colonnina, con un procedimento che richiede M(n) = 2n − 1 movimenti.

In totale, il numero minimo di mosse per spostare una torre di n + 1 dischi sara quindi:

M(n + 1) = M(n) + 1 + M(n) = 2n − 1 + 1 + 2n − 1 = 2 · 2n − 1 = 2n+1 − 1

Bibliografia

[1] M. Danesi, Labirinti, quadrati magici e paradossi logici. I dieci piu grandi enigmi matem-

atici di tutti i tempi, Dedalo, 2006

[2] I giochi matematici. Rompicapi o divertimenti?, Traduttore: A. Lissoni, Kangourou Italia,

2007

[3] D. Romagnoli, Laboratorio di Combinatorica, Universita di Torino, Dipartimento di Matem-

atica, Anno Accademico 2007-2008

[4] D. Romagnoli, Elementi di Matematica Discreta, Universita di Torino, Dipartimento di

Matematica, Quaderno n. 23, Gennaio 2004

[5] F. Peiretti, Le tre torri di Hanoi da Fibonacci a Lucas, Articolo tratto da Tuttoscienze di

mercoledı 28 novembre 2001

25

Sitografia

[1] www.wikipedia.org

[2] www.polito.it/polymath

[3] www.math.it

26