SISSIS
LABORATORIO DI GIOCHI MATEMATICI A.A. 2000/2001
LA TORRE DI HANOI
TESINA DI PROF.
Emanuele Perez Gabriella Randazzo
Pietro Di Giorgio Rosanna Lo Baido Gaetana Clementi
PERCORSO
INTRODUZIONE
Il seguente lavoro prevede la discussione del celebre gioco ideato nel 1883 da Edouard Lucas. L’obiettivo è quello di mettere in evidenza una funzione dei giochi matematici che rende questi ultimi preziosi, se non necessari, nell’apprendimento della matematica.
L’idea chiave di tutto il lavoro è quella di confrontare il principio di induzione:
a) Attraverso il gioco e per successivi livelli di formalizzazione
b) Per via assiomatica e per successive applicazioni a particolari proprietà dei numeri naturali.
Esse rappresentano due vie complementari che insieme contribuiscono alla piena formalizzazione matematica.
1. BREVE STORIA DEL GIOCO TORRE DI HANOI
Il rompicapo della Torre di Hanoi fu inventato nel 1883 dal prof. Claus nel collegio di Li-Sou-Stian. Questo gioco è la versione semplificata della famosissima
“Torre di Brahma”, che si trova nel tempio di Benares in India, e che è composta da 64 dischi d’oro. Nel grande tempio di Brahma 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 spostato su un altro più piccolo. 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.
Successivamente si è scoperto che Claus è l’anagramma di Lucas e Li-Sou-Stian è quello di Saint-Louis. Infatti il vero autore del gioco è il matematico francese Edouard Lucas, del collegio di Saint-Louis.
2. IL GIOCO
L'aspetto interessante (e matematico) del gioco è la ricerca della strategia vincente, che porta alla scoperta della formula che indica il numero minimo di mosse necessarie per vincere.
Lo scopo del gioco è quello di spostare sulla terza asta i dischi che inizialmente si trovano sulla prima, nel rispetto delle seguenti regole:
q Si può spostare un disco alla volta togliendolo dall’asta in cui si trova e portandolo in una delle altre due;
q Non è consentito sovrapporre un disco più grande su uno più piccolo;
q Non è consentito lasciare un disco “sospeso in aria”, mentre se ne sposta un altro.
.
3. LA SOLUZIONE DEL GIOCO
La torre di Hanoi è un classico problema di ricorsione.
I giocatori hanno a disposizione 3 paletti o torri nei quali possono infilarsi dei dischi sovrapposti in modo che i loro diametri siano via via più piccoli.
Il gioco consiste nel trasferire i dischi dalla torre 1 alla torre 3 spostandone uno per volta ed utilizzando la torre di mezzo 2, affinché in nessun momento un disco sia posto su uno più piccolo.
Il gioco è molto facile da capire, e il nostro problema è trovare un algoritmo capace di riprodurlo nel rispetto delle regole.
Quindi supponiamo di avere solo tre dischi, ci e' sufficiente specificare torre di partenza e torre di destinazione, visto che possiamo muovere solo un disco alla volta.
Quali sono le mosse che ci portano alla soluzione:
• muovi: 1 -> 3
• muovi: 1 -> 2
• muovi: 3 -> 2
• muovi: 1 -> 3
• muovi: 2 -> 1
• muovi: 2 -> 3
• muovi: 1 -> 3
Pertanto il numero di mosse necessarie, con tre dischi, risulta essere sette. Con quattro dischi, ripetendo il procedimento, risulta essere quindici. Con un numero maggiore di dischi, specificare ogni mossa e' dunque impensabile.
La ricorsione, nel caso delle torri di Hanoi, e' l'unico modo per definire l'insieme di tutte le mosse con solo tre definizioni, che spiegano la seguente funzione ricorsiva:
Passo Base: Hanoi(0) = 0
Passo induttivo: Hanoi(n)=2Hanoi(n-1) + 1 per n>0
Questa funzione la possiamo esprimere piu' esplicitamente cosi':
1. Sposta n-1 dischi da torre a supporto, usando destinazione (sorgente = torre 1, supporto = torre 2)
2. Sposta l'n-esimo disco da sorgente a destinazione (destinazione = torre 3) 3. Sposta gli n-1 dischi dal supporto a destinazione, usando sorgente.
Come si vede si tratta di una doppia ricorsione, l'espansione di ciascun passo significa sostituire, opportunamente
• sorgente
• supporto
• destinazione
che di volta in volta verranno istanziati con l'operazione corrente, all'inizio avremo che sorgente =torre 1, supporto =torre 2 e destinazione =torre 3.
Questa relazione ricorsiva [Hanoi(n)=2Hanoi(n-1) + 1 per n>0] ci permette di trovare il valore del termine n-esimo, tuttavia è importante trovare una soluzione per una relazione ricorsiva, o, come anche si dice, una formula chiusa che esprima direttamente il termine n-esimo in termini di un numero di operazioni ben note di n e non in termini dei precedenti elementi della successione. Una soluzione permette di capire esattamente il valore di ogni termine, mentre una relazione ricorsiva dà solo una informazione locale. Ad esempio nel caso delle torri di Hanoi per potere congetturare la soluzione potremmo fare dei “quasi esperimenti” cioè saggiare alcuni casi particolari.
Si cominci ad esaminare che cosa succede per n=1.
Il numero delle mosse M1 vale 1. Le informazioni sono troppo povere per formulare ipotesi.
Per n=2 si ha M2=3. Qui si apre qualche spiraglio di luce. Il numero 3 può essere scritto in modi diversi.
q M2=3=2⋅n −1
q M2=3= n2-1
q M2=3= 2n-1+1
q M2=3= 2n-1
Si procede ad un nuovo “quasi esperimento” esaminando che cosa succede per n=3.
In questo caso il numero delle mosse M3=7. Se fosse valida la prima ipotesi dovremmo avere M3=5, per la seconda M3=8, per la terza M3=5. Resta in piedi solo la quarta ipotesi per la quale le cose vanno bene.
M3=23-1=7.
Facendo ulteriori prove per M4, M5, M6, l’ipotesi si rafforza.
Quindi se n è il numero dei dischi, la formula chiusa che esprime direttamente il termine n-esimo, e quindi il numero di mosse necessarie per completare il gioco è 2n-1.
4. GLI ASSIOMI
Ogni scienza deduttiva deve presupporre conosciuti alcuni termini fondamentali o primitivi desunti dall’osservazione e dall’esperienza o semplicemente assunti come tali per convenzione. Analogamente ai termini primitivi, non è possibile dimostrare tutte le affermazioni di una teoria: non si può infatti ammettere che nella dimostrazione di un’affermazione A si faccia uso di una affermazione B, la quale a sua volta richieda l’uso di una affermazione C e così via.
Tale procedimento equivarrebbe ad un’impossibile regressione all’infinito, a meno che non si ammetta di potersi fermare ad un certo punto. Devono quindi esistere un certo numero di proposizioni, dette postulati o assiomi, che si accettano
“ufficialmente” come veri e per cui non si richiede dimostrazione, da essi si può poi tentare di dedurre altre proposizioni con un ragionamento puramente logico.
Si dice che una teoria scientifica è presentata in forma assiomatica, se le sue proprietà sono poste in un ordine logico tale che si possa dimostrare che esse sono conseguenza di un certo numero di proposizioni iniziali, dette assiomi.
“Dimostrare” fino ad un’epoca abbastanza recente, significava: “ridurre all’evidenza col ragionamento”. Questo modo di intendere la dimostrazione matematica sarebbe pienamente accettabile se il progresso della scienza non avesse provato più e più volte che l’intuizione porta a certi risultati erronei quando si esercita al di là di certi
limiti. Se si rimanesse ostinatamente attaccati all’intuizione anche laddove non è per nulla nativa, ma frutto di analogie talvolta illusorie, il progresso scientifico sarebbe condannato ad un fatale arresto. La fisica atomica, ad esempio, con i suoi risultati e tutte le sue promesse, non sarebbe stata possibile se ci fossimo legati all’antica intuizione della materia. Oggi, dimostrare significa ricondurre agli assiomi.
5. GLI ASSIOMI DI PEANO
Il numero naturale è il primo concetto matematico creato dallo spirito umano. In natura si trovano oggetti dello stesso tipo e il primo obiettivo di natura matematica che si è presentato all’uomo è stato di classificarli e poi numerarli. Il concetto di numero astratto è stato elaborato in seguito. Tutte le scienze matematiche si sono sviluppate partendo dall’insieme dei numeri naturali. I cinque assiomi sui quali si basa la teoria dei numeri naturali vennero enunciati dal matematico italiano G.
PEANO (1858-1932):
6. PRINCIPIO DI INDUZIONE MATEMATICA
Che cosa dice il principio di induzione matematica ?
La formulazione che presenteremo è del matematico italiano Giuseppe Peano (1858- 1932). Gli assiomi di Peano rappresentano il tentativo più singolare fatto nel secolo XIX di ridurre l’aritmetica comune, e di conseguenza, in ultima istanza, la maggior parte della matematica, alla pura essenzialità di un simbolismo formale.
Ecco la sua formulazione:
sia A un insieme di numeri naturali.
Se
q 0 A
q per ogni numero naturale n se n A allora anche Sc(n) A allora A cioè contiene tutti i numeri naturali.
Con il simbolo Sc(n) si indica il successivo di n.
In questa formulazione si suppone che 1 sia il primo numero naturale, lo zero, quindi, non è un numero naturale.
Di questo principio si usa dare anche una formulazione in termini di proprietà nel seguente modo.
Per ogni numero naturale n sia assegnata una proprietà Pn Se
q è vera P0 cioè la Pn è vera per n=0
q per ogni numero naturale r, dal fatto che se è vera Pn per n = r si può dedurre che è vera Pn per n=Sc(r) ,
allora Pn è vera per ogni numero naturale n.
La formulazione del principio è quella classica dei teoremi.
- C’è una lunga ipotesi sostenuta, linguisticamente, dal “se” sottolineato, - C’è una tesi sostenuta, linguisticamente, dall' “allora” sottolineato.
L’ipotesi, a sua volta, si compone di due parti:
1) E’ vera P0, che come vedremo si tratta solo di una verifica.
2) Per ogni numero naturale r se è vera Pr allora è vera anche Psc(r).
Questa seconda parte, forse contro ogni aspettativa, è, a sua volta, un “teorema” con una ipotesi (se vale Pr) e una tesi (allora vale Psc(r)). Come teorema, ovviamente deve essere dimostrato se vogliamo utilizzare il ragionamento per ricorrenza.
E’ proprio la dimostrazione di questo teorema la parte più impegnativa del ragionamento per induzione.
Il principio di induzione o viene assunto come assioma, come ha fatto Peano, o viene dimostrato come teorema, partendo da altri assiomi. E’ questa la strada seguita, per esempio dal Pieri (1860-1913) che utilizza sulla sua costruzione assiomatica dell’aritmetica, il principio di minimo: Ogni sottoinsieme non vuoto di numeri naturali possiede un minimo.
7. ASSIOMI DI PEANO
Il sistema proposto da Peano si basa su tre concetti primitivi e cinque postulati.
Concetti primitivi C1) Zero
C2) Numero naturale.
C3) Successivo (di un numero naturale).
Postulati
P1) Zero è un numero naturale.
P2) Se n è un numero naturale, lo è anche il suo successivo.
P3) Uno non è il successivo di alcun numero naturale.
P4) Due numeri, i cui successivi sono uguali, sono essi stessi uguali.
P5) Se un insieme S contiene l’uno e contiene il successivo di ogni numero contenuto in S, allora ogni numero naturale è contenuto in S.
Utilizzando la nota simbologia insiemistica e logica, indicando con l’insieme dei numeri naturali e con n’ il successivo di un generico numero naturale n, gli assiomi di Peano si possono così formulare.
P1) 0
P2) n (n n’ ) P3) n (n’ 0)
P4) n m(n’=m’ n=m)
P5) [0 S (n S n’ S)] S.
Il seguente esempio chiarisce il ruolo dei primi quattro postulati di Peano:
Ecco come si può ricostruire l’insieme dei numeri naturali che già conosciamo.
Sappiamo, per il postulato P1, che lo zero è un numero naturale; da P2 deduciamo che deve esistere un numero naturale successivo dello zero, ossia 0’. Da P3 deduciamo che 0’ non può essere lo stesso zero. Esiste dunque un numero naturale diverso dallo zero: il suo successivo, che conveniamo di chiamare 1. Ciò stabilito, si
deduce, ancora da P2, che deve esistere un numero naturale successivo di 1, ossia 1’.
Per P3 esso non può essere 0, ma esso non può essere neppure 1. Infatti sappiamo già che è 1=0’ e se, per assurdo, fosse 1’=1, si avrebbe 1’=0’, da cui per P4 seguirebbe 1=0, che sappiamo già essere falso. Dunque 1’ è un numero naturale distinto da 0 e 1:
si può convenire di chiamarlo 2.
Continuando in questo modo si possono ottenere quanti si voglia numeri naturali.
8. INDUZIONE MATEMATICA E INDUZIONE SPERIMENTALE
Il metodo induttivo è tipico delle scienze sperimentali. E’ il procedimento che va dal particolare al generale e consiste nel ricavare, attraverso procedure opportune, una legge di carattere generale da alcune osservazioni sperimentali.
Per scoprire una proprietà di una certa classe di oggetti noi ripetiamo osservazioni e prove finché è possibile e in circostanze, per quanto è possibile, simili. Può allora accadere che una certa tendenza ben definita si manifesti in tutte le nostre osservazioni e i nostri esperimenti: nelle scienze sperimentali questa tendenza è allora accettata come proprietà della classe.
Questo procedimento induttivo, che è alla base di tutte le scienze sperimentali, come strumento dimostrativo è per sempre bandito dalla matematica rigorosa. Non solo una simile dimostrazione di una proposizione matematica sarebbe considerata ridicola, ma essa non sarebbe nemmeno accettabile come verifica di una verità già stabilita.
Infatti la prova ottenuta in un certo numero di casi non sarebbe sufficiente per dimostrare una proposizione matematica, mentre d’altra parte basterebbe un solo esempio contrario per negare la validità di un enunciato.
Tuttavia c’è una certa analogia tra i due metodi. Anche in matematica le osservazioni, le prove sperimentali, i “quasi esperimenti”, come li chiamava Eulero, possono servire per formulare ipotesi, per congetturare la tesi che poi dovrà essere dimostrata per induzione.
Ad esempio nel caso delle torri di Hanoi per potere congetturare la soluzione potremmo fare dei “quasi esperimenti” cioè saggiare alcuni casi particolari.
Si cominci ad esaminare che cosa succede per n=1.
Il numero delle mosse M1 vale 1. Le informazioni sono troppo povere per formulare ipotesi.
Per n=2 si ha M2=3. Qui si apre qualche spiraglio di luce. Il numero 3 può essere scritto in modi diversi.
q M2=3=2⋅n −1
q M2=3= n2-1
q M2=3= 2n-1+1
q M2=3= 2n-1
Si procede ad un nuovo “quasi esperimento” esaminando che cosa succede per n=3.
In questo caso il numero delle mosse M3=7. Se fosse valida la prima ipotesi dovremmo avere M3=5, per la seconda M3=8, per la terza M3=5. Resta in piedi solo la quarta ipotesi per la quale le cose vanno bene.
M3=23-1=7.
Facendo ulteriori prove per M4, M5, M6, l’ipotesi si rafforza.
A questo punto un cultore di scienze sperimentali formulerebbe la legge generale:
Mn=2n-1.
Il “suo metodo induttivo” ha raggiunto il suo scopo: attraverso un certo numero di esperimenti ha permesso di formulare una legge generale.
In matematica quella legge generale: Mn=2n-1 è solo una congettura, una ipotesi, che deve essere dimostrata. E’ in questa dimostrazione che interviene l’induzione matematica o induzione completa.
Si potrebbe quasi dire che essa inizia dove finisce il metodo induttivo delle scienze sperimentali.
A che cosa serve il principio di induzione?
Esso può essere utilizzato sia per dare definizioni che per effettuare dimostrazioni.
Definizione ricorsiva.
Prendiamo come esempio la definizione di addizione, a+b, di due numeri naturali a e b.
Il primo passo consiste nel dire quanto vale a+b quando b=0. Si pone (1) a+0=a
Il secondo passo consiste nel dire quanto vale a+b quando b 0 e quindi, essendo il successore di un numero, può essere scritto come b+1. Si pone:
(2) a+(b+1)=(a+b)+1 In forma compatta:
A1) a+0=a
A2) a+(b+1)=(a+b)+1
Questa formulazione potrebbe suscitare qualche perplessità, perché nella definizione dell’operazione compare l’operazione da definire. In realtà tale definizione è corretta:
si tratta di una definizione ricorsiva; mediante essa, dati due numeri naturali, se non è possibile stabilire immediatamente il risultato dell’operazione, si è rinviati a un caso
“più semplice”, il quale se non è immediatamente definito, rimanda a sua volta a un altro caso; comunque con un numero finito di "passi all’indietro” si può stabilire il risultato dell’operazione.
Questa definizione non dice tanto che cosa è a+b quanto, piuttosto, fornisce un algoritmo per calcolarlo.
Si tratta di una definizione di tipo operativo, dinamico, in quanto fornisce una regola di calcolo.
Strumento per dimostrare.
Un esempio molto semplice di dimostrazione ricorsiva è il seguente:
vogliamo dimostrare che la somma dei primi n numeri naturali è n(n+1)/2, ossia che per qualsiasi n si ha:
Sn= 1+2+3+…+n = n(n+1)/2
Chiamiamo come proprietà P(n) la suddetta proposizione.
Per dimostrare che tale proposizione è vera utilizziamo il principio di induzione:
1) Verificare che vale P(1)
La cosa è immediata : S1= 1=1x2/2
2) dimostrare che se vale P(n) per n=r, qualunque sia r, allora P(n) vale anche per n=r+1.
La nostra ipotesi è:
Sr= 1+2+3+…+r = r(r+1)/2;
La nostra tesi è:
Sr+1= 1+2+3+…+r+(r+1) = (r+1)(r+2)/2;
Ora, utilizzando l’ipotesi, che si chiama ipotesi di induzione, possiamo scrivere:
Sr+1= r(r+1)/2+(r+1);
Non ci resta che fare qualche piccola manipolazione di carattere algebrico:
Sr+1= r(r+1)/2+(r+1) = [r(r+1)+2(r+1)]/2 = (r2+3r+2)/2 = (r+1)(r+2)/2;
cioè la nostra tesi.
Essendo verificate le due ipotesi del principio di induzione possiamo concludere che P(n) è vera per ogni numero naturale n.
Esempi di relazioni ricorsive.
Sia data ad esempio la relazione seguente:
s1=a, sn=sn-1+d.
Relazioni di tale tipo prende il nome di relazioni ricorsive. La condizione s1=a, è la cosiddetta condizione iniziale.
Nell’esempio dato il termine n-esimo dipende esclusivamente dal precedente (e da una costante). In generale in una relazione ricorsiva il termine n-esimo dipenderà da un certo numero r di termini precedenti e da una funzione nota di n. In tal caso
serviranno generalmente r condizioni iniziali (ad esempio i valori dei primi r termini).
Il seguente è un esempio di successione definita ricorsivamente:
a0=0, a1=1, an=an-1+an-2.
I primi termini della successione sono i seguenti:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,…
Si tratta della successione dei numeri di Fibonacci.
Anche se una relazione ricorsiva ci permette di trovare il valore del termine n-esimo an, per ogni n, tuttavia è importante trovare una soluzione per una relazione ricorsiva o, come anche si dice, una formula chiusa che esprima direttamente an in termini di un numero di operazioni ben note di n e non in termini dei precedenti elementi della successione. Una soluzione permette di capire esattamente il valore di ogni an, mentre una relazione ricorsiva dà solo una informazione locale.
Nel caso delle torri di Hanoi si può vedere facilmente che il problema viene risolto dalla seguente relazione ricorsiva:
M1=1,Mn=2Mn-1+1.
Infatti per trasferire un solo disco occorre una sola mossa, pertanto M1=1. Per trasferire n dischi è opportuno utilizzare la seguente strategia: prima spostare gli n-1 dischi di diametro inferiore dall’asticella di partenza a quella intermedia (occorrono Mn-1 mosse) quindi spostare il disco di diametro maggiore rimasto sull’asticella di partenza, sull’asticella di arrivo (occorre una sola mossa), infine trasferire gli n-1 dischi di diametro inferiore dall’asticella intermedia a quella di arrivo (occorrono altre Mn-1 mosse).
Mentre per la soluzione in formula chiusa abbiamo visto (almeno come congettura) che è:
Mn=2n-1
Occorre ora dimostrare che è effettivamente soluzione per ogni n.
Procediamo per induzione. Per n=1, M1=1=21-1, e la base dell’induzione è verificata.
Supposta vera la Mn-1=2n-1-1, si tratta di provare che vale Mn=2n-1. Infatti
Mn=2Mn-1+1=2(2n-1-1)+1=2n-1, e la dimostrazione è conclusa.
Una formulazione più complessa.
Sia ={0,1,2,3,…} l’insieme dei numeri naturali.
Attraverso i seguenti assiomi, noti come postulati di Peano, verrà data una definizione di che prescinde dalla natura degli elementi di . La definizione formale di è la seguente:
L’insieme dei numeri naturali è costituito da una terna ( , σ, 0) dove è un insieme, σ è una applicazione da in e 0 è un elemento di tali che
1 σ è iniettiva;
2 0 Im σ;
3 ogni sottoinsieme U di tale che (a) 0 U,
(b) k U σ(k) U k coincide con tutto .
Dato un elemento n , l’elemento σ(n) si dice il successivo di n. Resta definita in allora in modo naturale una relazione d’ordine, . Il postulato 3 è noto come il principio di induzione matematica. Si può dimostrare che se (AA, σ, 0) e (A’A’, σ’, 0’) sono due terne identiche che verificano i postulati precedenti, allora esse sono
“sostanzialmente identiche”, nel senso che esiste una corrispondenza biunivoca φ tra
A
A e A’A’ tale che σ’(φ(n))= φ(σ (n)), cioè il successivo del trasformato è il trasformato del successivo. Quindi si può dire che i postulati di Peano caratterizzano i numeri naturali.
Soffermiamoci ora sul principio di induzione matematica 3 . Esso sostanzialmente dice che se un sottoinsieme U di è tale che contiene lo zero e, accanto ad ogni elemento contiene anche il successivo, allora necessariamente U coincide con tutto
. L’accettazione di questo assioma fornisce “gratuitamente” un metodo di dimostrazione per induzione che è di fondamentale importanza in matematica.
Vediamo in che cosa consiste. Supponiamo che per ogni intero n 0 si possa formulare una proposizione P(n) dipendente dall’intero n, ad esempio la proposizione seguente: “se un insieme finito S ha n elementi, allora l’insieme delle parti di S ha 2n elementi”. Supponiamo di volere provare che la proposizione P(n) è vera per ogni n:
si tratta di dimostrare infinite proposizioni! Ebbene il metodo di dimostrazione per induzione permette di ottenere questi infiniti risultati con due soli passi. Si procede al modo seguente:
(1) Base dell’induzione: Dimostrare che è vera P(0);
(2) Passo induttivo: Dimostrare che per ogni k dall’essere vera P(k) segue che è vera P(k+1).
Allora si può concludere di avere dimostrato che P(n) è vera per ogni n.
Infatti, posto U = {n | P(n) è vera}, risulta 0 U perché è stato provato che P(0) è vera. Inoltre, se k U, cioè se P(k) è vera, allora P(k+1) è vera (passo induttivo) e quindi k+1 U, da cui segue, in virtù di 3, U= , ossia P(n) è vera per ogni n.
Diamo qui di seguito delle formulazioni equivalenti del principio di induzione 3, perché, a seconda dei casi che si presentano, può essere conveniente utilizzare una formulazione invece di un’altra. Consideriamo le seguenti due asserzioni, II e MM :
II Ogni sottoinsieme V di tale che
(a) 0 V,
(b) n V ogniqualvolta k V k tale che 0 k<n coincide con tutto .
M
M (Principio del buon ordinamento, o del minimo) Ogni sottoinsieme non vuoto T contenuto in contiene un elemento minimo, cioè esiste un elemento t T tale che t x per ogni x T.
Un insieme parzialmente ordinato X si dice ben ordinato se ogni sottoinsieme non vuoto di X ha un elemento minimo. In questa terminologia MM afferma che l’insieme
dei numeri naturali è bene ordinato.
Utilizzando M si può provare che non esiste alcun intero c compreso tra 0 e 1.
Supponiamo per assurdo che esista un c tale che 0<c<1. Allora l’insieme T={c | 0<c<1} è non vuoto e pertanto possiede minimo m. Moltiplicando per m>0 ogni membro della
0<m<1 si ottiene 0<m2<m<1
che contraddice la minimalità di m.
Infine si può dimostrare la seguente proposizione:
Le tre asserzione 3, II, e MM, sono equivalenti.
4. Il gioco dei tranci di Pizza
Il problema in oggetto è il seguente: qual è il massimo numero Ln di regioni definite da n linee del piano? Tale problema fu risolto per la prima volta nel 1826, dal matematico svizzero Jacob Steiner.
Per risolvere il problema si adopera un procedimento ricorsivo come abbiamo fatto per il gioco della Torre di Hanoi.
5. La soluzione del gioco
Iniziamo con valori di n piccoli, dove n è il numero di linee che abbiamo per dividere il piano in regioni: ad esempio per n=1 cioè con una sola linea il piano viene suddiviso in 2 regioni; con n= 2 abbiamo 4 regioni allora potremmo supporre che ogni volta che aumentiamo le linee di 1 il numero di regioni raddoppia:
Numero di linee Numero di regioni
0 1
1 2
2 4
3 7
1
2
1
2
4
3
Con n= 3 linee a disposizione si vede che la terza linea può al massimo dividere tre regioni, e non importa il modo in cui abbiamo posto le prime due linee.
Allora L3= 7 regioni è il massimo che possiamo ottenere.
Se allora generalizziamo i risultati ottenuti
1
2
3
4 5
6 7
