UNIVERSIT `
A DEGLI STUDI DI PISA
Facolt`
a di Scienze Matematiche, Fisiche e Naturali
Corso di Laurea Specialistica in
Matematica
Tesi di Laurea
CURVE DI RIFLESSIONE
Relatore:
Candidato:
Prof. FRANCO FAVILLI
TOMMASO PAVANELLO
Controrelatore:
Prof. VLADIMIR GEORGIEV
Indice
Introduzione 3
1 Griglie senza specchi interni 6
1.1 Costruzione delle linee . . . 6
1.2 Propriet`a delle linee . . . 9
1.3 Struttura delle linee in R(2p,2q) . . . 13
1.4 Un algoritmo per identificare le intersezioni tra le linee . . . 22
2 Griglie con specchi interni 24 2.1 Inserimento di uno specchio in una griglia . . . 24
2.2 Inserimento di uno specchio in una griglia priva di specchi interni. . . 29
2.3 Griglie monolineari . . . 33
3 Curve di riflessione e grafi 37 3.1 Notazione essenziale . . . 37
3.2 Grafi Sona . . . 39
3.3 Generazione ricorsiva di grafi gaussiani . . . 40
3.4 Grafi Sona e grafi gaussiani . . . 44
3.5 Curve di riflessione e nodi . . . 56
Introduzione
In un’area dell’Africa centrale, situata approssimativamente nella parte est dell’Angola, nord-ovest dello Zambia e zone limitrofe dello Zaire, vivono i Chokwe (o Cokwe o anche Tchokwe), popolazione stimata approssimativamente in poco pi`u di un milione di persone. I tradizionali disegni dei Chokwe chiamati Sona (Lusona al singolare) hanno destato l’interesse di Paulus Gerdes e altri matematici dopo di lui che li hanno analizzati da vari punti di vista, svelando interessanti propriet`a. I Sona sono disegni tracciati sulla sabbia con la punta delle dita. Dapprima viene impressa sulla sabbia una griglia di punti, poi vengono tracciate delle linee chiuse continue tra i punti. Le linee non possono passare sopra i punti della griglia e non possono ripercorrere tratti gi`a percorsi. Possono per`o autointersecarsi ed al termine del disegno, di solito, tutti i punti della griglia vengono circondati dalle linee disegnate. Dimensione e forma della griglia sono variabili da Lusona a Lusona. A volte i Sona vengono adornati con linee extra dal puro scopo decorativo.
Nella cultura tradizionale dei Chokwe i Sona non erano una mera forma d’arte. Ad ogni Lusona era associato qualcosa come una storia, un proverbio o anche un gioco. Questi disegni avevano in realt`a un ruolo importante nella trasmissione della conoscenza da una generazione all’altra. I Sona pi`u semplici erano conosciuti dalla maggior parte degli uomini.
Gli “Akwa kuta Sona” (coloro che sanno come disegnare), i pochi esperti a conoscenza delle tecniche di esecuzione dei Sona pi`u complessi, tramandavano queste conoscenze ai propri figli maschi ed erano tenuti in alta considerazione nella societ`a Chokwe.
L’influenza portoghese iniziata alla fine del quindicesimo secolo e culminata nella dominazione coloniale alla fine del diciannovesimo secolo port`o al declino della cultura e delle tradizioni Chokwe e i Sona, da elemento culturale importante quale erano, sono stati quasi dimenticati. Non sorprende che attualmente la parola Sona venga usata dai Chokwe
per indicare anche la scrittura, di cui erano privi fino all’avvento della dominazione coloniale. Di fatto i Sona una forma di scrittura lo sono stati.
L’originario scopo didattico dei Sona ha trovato nuova linfa grazie a Gerdes, che ha pensato di poter utilizzare i Sona come mezzo per far scoprire agli studenti le interessanti propriet`a algebriche e geometriche di cui sono dotati (vedere ad esempio [12]). La storia e bellezza come forma d’arte dei Sona possono aiutare gli studenti a mantenere vivo l’in-teresse nell’apprendimento e nella scoperta. Alcune idee di Gerdes sono state sviluppate ad esempio in [6].
`
E possibile descrivere dal punto di vista matematico i Sona (e forme artistiche di altre culture come, ad esempio, i nodi celtici, cfr. [20]) con le “curve di riflessione”, in inglese “mirror curves”. Il nome di queste curve viene dalla loro descrizione intuitiva di traiettorie (planari) di raggi di luce in scatole le cui pareti sono formate da specchi e dove all’interno possono trovarsi specchi a doppia superficie riflettente. Pareti della scatola e specchi sono messi in modo tale che il raggio di luce possa essere riflesso solo ortogonalmente.
In questo lavoro presentiamo le curve di riflessione descrivendole come linee chiuse composte da segmenti che possono unire solo punti adiacenti di una griglia di punti a coordinate intere a somma dispari in un’area limitata del piano cartesiano, limitandoci a considerare griglie su aree rettangolari. Abbiamo omesso la griglia di punti disegnata preliminarmente dagli artisti Chokwe visto che non ha un ruolo essenziale nella costru-zione delle curve di riflessione ed `e ottimamente sostituita dai riferimenti dati dal piano cartesiano. Il problema che ci poniamo `e quello di capire cosa succede inserendo uno specchio in una griglia, studiando come cambiano le linee, in particolare il loro numero.
La tesi `e organizzata come segue.
Il Capitolo 1 `e dedicato alla definizione delle curve di riflessione e la dimostrazione di alcune basilari propriet`a, su griglie prive di specchi interni.
Nel paragrafo 1.2 presentiamo una dimostrazione di un noto risultato: il numero di linee di cui `e composta la curva di riflessione su una griglia di lati 2p e 2q, con p, q ∈ N, `
e uguale al massimo comun divisore tra p e q.
Nel paragrafo 1.3 presentiamo la dimostrazione che le linee possiedono una struttura periodica, risultato non presente nella letteratura sulle curve di riflessione.
Nel paragrafo 1.4 utilizziamo la struttura delle linee dimostrata nel paragrafo prece-dente per descrivere un algoritmo in grado di identificare quali linee si intersecano in un punto della griglia a partire dalle coordinate del punto.
Nel capitolo 2 allarghiamo l’analisi a comprendere griglie con specchi interni.
Nel primo paragrafo presentiamo la dimostrazione di alcuni risultati noti sulle con-seguenze di inserire uno specchio all’interno di una griglia che ne `e priva. Introduciamo inoltre un criterio nuovo, collegato alla struttura delle linee dimostrata nel capitolo pre-cedente, per decidere quale orientamento di uno specchio posto in un’autointersezione di una linea in un punto interno lasci intatta la linea.
Nel secondo paragrafo applichiamo i risultati ottenuti nel primo paragrafo per risolvere completamente il problema di inserire uno specchio in una griglia priva di specchi interni. Nel terzo paragrafo affrontiamo un tema molto discusso in letteratura, quello delle griglie monolineari, ovvero le curve di riflessione composte da un’unica linea. In que-sto paragrafo dimostriamo il Teorema 2.8 in modo sostanzialmente differente da quello seguito in [19].
Nel capitolo 3 presentiamo le curve di riflessione dal punto di vista della teoria dei grafi. Nel primo paragrafo introduciamo la notazione necessaria. Introduciamo inoltre la nozione di grafo gaussiano.
Nel secondo paragrafo, seguendo [5], definiamo i grafi Sona, grafi derivati da curve di riflessione, e mostriamo che sono grafi gaussiani.
Nel terzo paragrafo, seguendo [23], approfondiamo la nozione di grafo gaussiano e mostriamo come sia possibile generarli tutti a partire dal grafo con un nodo e due loop. Nel quarto paragrafo presentiamo una dimostrazione originale del fatto che ogni grafo gaussiano `e isomorfo ad un grafo Sona.
Nel quinto paragrafo, seguendo [23], presentiamo brevemente le connessioni tra grafi gaussiani e diagrammi di nodi e mostriamo come le curve di riflessione possono essere usate per rappresentare i nodi.
Abbiamo anche modificato il software SonaPolygonals (programma scritto in java, la cui prima versione `e descritta in [7]). Questo software ci `e stato utile sia per formulare alcune congetture che poi abbiamo dimostrato (la struttura delle linee, Sezione 1.3 e Teorema 2.6), sia per le figure presenti nel testo.
Capitolo 1
Griglie senza specchi interni
Dati p, q ∈ N\{0}, consideriamo il rettangolo di lati 2p e 2q nel piano cartesiano che ha come vertici i punti (0, 0), (2p, 0), (0, 2q), (2p, 2q). Di questo rettangolo ci interessano i punti con coordinate intere a somma dispari. Indicheremo con R(2p, 2q) la griglia di punti appena descritta.
1.1
Costruzione delle linee
Disegneremo delle linee unendo tra loro punti della griglia con segmenti utilizzando le seguenti regole di costruzione.
Per prima cosa associamo una matrice A(x,y) ad ogni punto (x, y) di R(2p, 2q): ai
punti sulle rette x = 0 e x = 2p associeremo la matrice −1 0 0 +1
!
, a quelli sulle rette
y = 0 e y = 2q la matrice +1 0 0 −1
!
, a tutti gli altri la matrice +1 0 0 +1
! .
Gli altri elementi della costruzione sono: il punto da cui partiamo (x0, y0) e un vettore
(a0, b0) con a0, b0 ∈ {1, −1}. Giunti ad (xn, yn), il passo successivo consiste nell’unire con
un segmento (xn, yn) e (xn+1, yn+1) definito come segue:
(
(xn+1, yn+1) = (xn, yn) + (an, bn)
(an+1, bn+1) = A(xn+1,yn+1) (an, bn)
Partiamo da x0 = 0, y0 = 1, a0 = 1, b0 = 1 (Figura 1-1). Notiamo che i segmenti
Figura 1-1: Una linea su R(32,24)
un punto del bordo, nel qual caso la regola di costruzione viene modificata moltiplicando per −1 l’incremento della coordinata che ha raggiunto il valore estremo, lasciando l’altro incremento invariato. In altre parole, tutte le volte che un segmento ha come secondo estremo un punto del bordo, il successivo verr`a disegnato come se fosse un raggio di luce e venisse riflesso, con il bordo come se fosse uno specchio (da cui il nome di curve di riflessione).
Gli estremi ammissibili per i segmenti cos`ı generati hanno tutti una coordinata pari ed una dispari. Infatti considerando per ogni punto visitato la somma delle sue coordinate, partiamo da uno con somma dispari e ad ogni passaggio sommiamo 0 oppure 2 oppure −2. I punti teoricamente visitabili come estremi di un segmento della linea, chiamiamoli punti ammissibili, sono quindi tutti i punti con una coordinata pari e l’altra dispari dentro il rettangolo, ovvero tutti i punti di R(2p, 2q). Fissata un’ascissa, abbiamo q punti ammissibili se essa `e pari, q + 1 se dispari, per un totale di q(p + 1) + p(q + 1) = 2pq + p + q. I segmenti teoricamente possibili sono quelli che connettono ogni punto ammissibile con i suoi immediati vicini, chiamiamoli segmenti ammissibili, e sono quindi 4 per ogni punto ammissibile interno e due per ogni punto sul bordo. I punti ammissibili sul bordo sono 2(p + q), quelli interni sono 2pq − p − q. Quindi il totale dei segmenti ammissibili `e
4(p+q)+4(2pq−p−q)
2 = 4pq. Il 2 al denominatore corregge il fatto che ogni segmento connette
due punti e veniva contato due volte. Il totale dei segmenti ammissibili `e finito, quindi prima o poi la linea costituita dalla successione dei segmenti dovr`a percorrere nuovamente un segmento gi`a percorso. Prima di farlo ci fermiamo.
Teorema 1.1. La linea costruita sopra `e chiusa: il punto di partenza e il punto finale coincidono.
Dimostrazione. I segmenti successivi della linea sono costruiti sulla stessa retta finch´e il secondo estremo di uno di essi non si trova sul bordo. A quel punto il segmento seguente viene costruito su una retta ortogonale alla precedente (quindi non torna indietro sul percorso appena fatto).
Notiamo che la costruzione `e fatta in modo tale che con le stesse regole si pu`o co-struire la linea in senso inverso partendo da un qualsiasi punto visitato e utilizzando come incremento l’opposto di quello usato per arrivare al punto considerato. Infatti da (xn+1, yn+1) = (xn, yn) + (an, bn) si ottiene
(xn, yn) = (xn+1, yn+1) + (−an, −bn).
Inoltre, visto che (an+1, bn+1) = A(xn+1,yn+1) (an, bn) e che A
−1
(x,y) = A(x,y), per ogni (x, y)
punto ammissibile, si ottiene
(−an, −bn) = A(xn+1,yn+1) (−an+1, −bn+1).
Se il primo segmento che la linea si trova a dover percorrere per la seconda volta fosse diverso dal segmento di partenza si avrebbe che venendo da due direzioni diverse si potrebbe imboccare lo stesso segmento. Ma questo non `e possibile: infatti sarebbe equi-valente, tornando indietro, alla possibilit`a di imboccare due diversi segmenti nel disegnare una linea a partire da un unico punto ammissibile e questo `e escluso per costruzione.
Ora si avranno due casi. O sono stati visitati tutti i punti ammissibili sulla parete x = 0 (quindi del tipo (0, 2k + 1), con k ∈ N, 0 ≤ k < q)) oppure no. Nel primo caso ci fermiamo, nel secondo disegniamo una seconda linea utilizzando le stesse regole della prima partendo da un punto ammissibile sulla parete x = 0 che non sia stato visitato. Proseguiremo nel disegnare altre linee fino ad esaurire i punti ammissibili sulla parete x = 0.
1.2
Propriet`
a delle linee
Vedremo adesso alcune propriet`a delle linee definite nella sezione precedente. Il risultato principale di questa sezione `e la dimostrazione che il numero delle diverse linee in R(2p, 2q) `
e il massimo comun divisore di p e q.
Lemma 1.2. Le linee cos`ı disegnate non hanno segmenti in comune.
Dimostrazione. Se due diverse linee avessero un segmento in comune si avrebbe che in un punto ammissibile (quello dove si uniscono) dovrebbero confluire due diverse linee ed entrambe imboccare lo stesso segmento. Ci`o `e impossibile, come visto nella dimostrazione del Teorema 1.1
Teorema 1.3. Ogni segmento ammissibile viene percorso una ed una sola volta da una delle linee.
Dimostrazione. Dimostriamo l’enunciato per induzione sull’ascissa dei punti ammissibili. Caso x = 0. Da ogni punto ammissibile (0, 2k + 1), con k < q intero, partono due segmenti ammissibili i cui altri estremi sono (1, 2k + 2) e (1, 2k). Ogni linea `e chiusa e non torna sui propri passi quindi entrambi appartengono alla stessa linea. Cos`ı, per costruzione, tutti i segmenti ammissibili con un estremo sulla parete x = 0 vengono percorsi una ed una sola volta da una delle linee.
Passo induttivo. Supponiamo l’enunciato vero fino a x = n e dimostriamo che `e vero anche per x = n + 1. Prendiamo in considerazione il caso n + 1 < 2p. Su ogni punto ammissibile interno incidono quattro segmenti. Ognuno dei due segmenti che lo connettono con punti ammissibili della retta x = n + 2 si trova ad essere sulla stessa retta di uno dei due che lo connettono con punti ammissibili della retta x = n, i quali per ipotesi vengono percorsi una ed una sola volta da una delle linee. Per costruzione in un punto ammissibile interno i segmenti successivi nella costruzione delle linee si trovano sulla stessa retta, quindi la tesi `e dimostrata. Per i punti ammissibili sui bordi (n + 1, 2q) e (n + 1, 0) si ha che uno dei due segmenti incidenti viene percorso una ed una sola volta da una delle linee per ipotesi e l’altro necessariamente appartiene alla stessa linea visto che ogni linea `e chiusa e non torna sui propri passi. Se n + 1 = 2p siamo giunti sul bordo, le linee si chiudono e non c’`e niente da dimostrare.
Corollario 1.4. Le linee inducono una partizione sui segmenti ammissibili. La partizione possiede tante classi di equivalenza quante sono le linee.
Corollario 1.5. Le linee inducono una partizione sui punti ammissibili della retta x = 0, della retta x = 2p, della retta y = 0 e della retta y = 2q. In ognuno di questi casi la partizione possiede tante classi di equivalenza quante sono le linee.
Dimostrazione. Su ogni punto ammissibile sui bordi incidono due segmenti appartenenti entrambi ad una linea, e quindi esso `e quindi univocamente associabile ad una (sola) linea.
Teorema 1.6 (Gerdes). Il numero k di linee necessarie per percorrere tutti i segmenti ammissibili di una griglia di lati 2p e 2q `e il massimo comun divisore tra p e q:
k = mcd(p, q). Dimostreremo preliminarmente alcuni lemmi.
Sia Q(p, q) = k (con p, q, k ∈ N\{0}) la funzione che associa a p e q il numero di linee k necessarie per percorrere tutti i segmenti ammissibili della griglia R(2p, 2q).
Lemma 1.7. Si ha Q(p, q) = Q(q, p).
Dimostrazione. La griglia R(2q, 2p) e la costruzione si possono ottenere facendo una simmetria della griglia R(2p, 2q) rispetto all’asse x = y. Quindi dai Corollari 1.4 e 1.5 del Teorema 1.3 segue che sarebbe possibile ripetere la costruzione partendo dai punti sulla parete y = 0 ottenendo le stesse linee (Figure 1.2(a) e 1.2(b)).
Senza perdere di generalit`a possiamo da ora in poi supporre p ≥ q. Il caso p = q `e semplice (Figura 1.2(c)).
Lemma 1.8. Si ha Q(p, p) = p.
Dimostrazione. Una linea che parte dal generico punto ammissibile (0, ky − 1) (con 0 < k ≤ q) finisce in (2p − 2k + 1, 2p) poi in (2p, 2p − 2k + 1) poi in (2k − 1, 0) ed infine torna al punto di partenza, toccando ogni parete una ed una sola volta. Di punti ammissibili sulla parete x = 0 ce ne sono p, quindi Q(p, p) = p.
(a) Linee di R(12, 8). (b) Linee di R(8, 12).
(c) Linee di R(8, 8). (d) Linea con punto di partenza (0, 3) su parte di una griglia con q = 4 e p multiplo di q.
Dimostrazione. Consideriamo R(2p, 2q) e la linea che passa dal generico punto ammissi-bile (0, 2k − 1) sulla retta x = 0. Se detta linea viene percorsa con incremento (1, 1) a partire proprio da (0, 2k − 1) verr`a riflessa in (2p − 2k + 1, 2p) e poi tra gli altri punti ammissibili visiter`a (2q, 2q − 2k + 1). Percorrendola invece con incremento (1, −1) verr`a riflessa in (2k − 1, 0) e poi tra gli altri punti ammissibili visiter`a ancora (2q, 2q − 2k + 1), provenendo dall’altra direzione possibile (Figura 1.2(d)). Quindi tutti e quattro i seg-menti ammissibili con (2q, 2q − 2k + 1) come estremo appartengono ad una sola linea, la stessa che passa per (0, 2k − 1). La funzione che associa (0, 2k − 1) a (2q, 2q − 2k + 1), ristretta ai punti ammissibili della retta x = 0, ha come immagine quelli della retta x = 2q ed `e biunivoca. `E ben definita e surgettiva quindi la funzione che associa ad ogni punto ammissibile posto sulla retta x = 2q l’unica linea che lo visita. Le linee perci`o inducono una partizione sui punti ammissibili della retta x = 2q con numero di classi di equivalenza uguale a Q(p, q).
Se sostituissimo la matrice identit`a associata ad ognuno dei punti ammissibili sulla retta x = 2q con la matrice −1 0
0 +1 !
(specchio verticale), e costruissimo le linee partendo dai punti ammissibili della retta x = 2q con incremento (1, 1), avremmo di fatto traslato R(2p − 2q, 2q) di +2q sulle ascisse lasciando intatta la struttura delle linee che dipende solo da p e q. La linea di R(2p − 2q, 2q) traslato che parte da (2q, 2q − 2k + 1) coincider`a con quella di R(2p, 2q) con punto iniziale (0, 2k − 1) in ogni segmento con ascissa x ≥ 2q dato che coincidono in ogni punto iniziale (punti ammissibili della retta x = 2q) e hanno gli stessi vincoli per x > 2q. Per x = 2q la prima verr`a riflessa subito mentre l’altra imboccher`a lo stesso segmento della prima dopo essere passata per un punto ammissibile della retta x = 0. Quindi la partizione indotta dalle linee di R(2p, 2q) e quella indotta dalle linee di R(2p − 2q, 2q) traslato coincidono sui punti ammissibili della retta x = 2q dimostrando il lemma.
Dimostrazione del Teorema 1.6. Notiamo che Q(p, 1) = 1 (abbiamo un solo punto am-missibile sulla retta x = 0). Procediamo per induzione su n = p + q, con p ≥ q > 0 (ipotesi non restrittiva per il Lemma 1.7).
Se n = 2 si ha Q(1, 1) = 1 e la tesi `e verificata.
Supponiamo ora che la tesi sia verificata fino a n − 1.
Se invece p > q e p+q = n abbiamo Q(p, q) = Q(p−q, q) e visto che p−q+q = p ≤ n−1 possiamo usare l’ipotesi induttiva Q(p, q) = Q(p − q, q) = mcd(p − q, q) = mcd(p, q), dimostrando il teorema.
1.3
Struttura delle linee in R(2p,2q)
Il prossimo teorema ci dar`a indicazioni su quali siano i punti dove si incontrano linee diverse. Quello che dimostreremo ci aiuter`a inoltre a caratterizzare completamente la struttura delle linee in R(2p, 2q).
Utilizzeremo una notazione semplificata. Visto che p e q sono fissati definiamo M = mcd(p, q). Denoteremo come di consueto con [x]n la classe di equivalenza di x ∈ Z modulo n.
Teorema 1.10. I punti ammissibili visitati da una sola linea in R(2p, 2q) sono tutti e soli quelli della forma 2cM, 2d + 1 o della forma 2d + 1, 2cM , con c, d ∈ N.
Per dimostrare il teorema avremo bisogno di alcuni lemmi nei quali dimostreremo condizioni algebriche soddisfatte da ogni punto ammissibile che `e all’intersezione tra una linea e le rette del tipo x = 2cM e y = 2dM deve soddisfare. Tali condizioni algebriche dipendono unicamente dalle linee che visitano i punti in questione. Mostreremo che le suddette condizioni algebriche per ognuno dei punti considerati possono dipendere da una sola linea e ne dedurremo che ognuno di essi `e visitato da una unica linea.
Consideriamo la linea che passa da (0, t), con t = 2s − 1, dove s ∈ N e 0 < s ≤ M, e costruiamola a partire da (0, t).
Numeriamo nell’ordine di incontro nella costruzione della linea le intersezioni (che sono punti ammissibili) che si avranno tra la linea stessa e le rette del tipo x = 2cM e quelle del tipo y = 2dM . Con (xk, yk) indicheremo la k-esima intersezione. La prima intersezione `e proprio il punto di partenza, quindi (x1, y1) = (0, t). Tra un’intersezione
e la successiva l’incremento nella costruzione della linea rimane invariato visto che pu`o cambiare solo quando vengono raggiunte le pareti e le pareti sono su rette del tipo con-siderato. Definiamo (ak, bk) l’incremento durante la costruzione della linea andando da
(xk−1, yk−1) a (xk, yk). Gli incrementi possibili sono quattro: (+1, +1), (−1, 1), (1, −1),
avremo la k-esima intersezione per il minimo 0 < wk≤ 2M tale che xk−1 + wkak2M = [0]2M _ yk−1+ wkbk2M = [0]2M .
Lemma 1.11. Ogni punto ammissibile (xk, yk) che sia intersezione tra la linea con ori-gine in (0, t) e le rette del tipo x = 2cM e y = 2dM , con c, d ∈ N, verifica la seguente condizione xk 2M +y k 2M = [t]2M _ xk 2M+y k 2M = [−t]2M
Dimostrazione. Dimostriamo l’enunciato per induzione su k. Per k = 1 abbiamo x1 2M+y 1 2M = [0]2M + [t]2M = [t]2M e la tesi `e verificata.
Sia dunque k > 1 e la tesi verificata fino a k − 1. Dimostriamo che `e vera anche per k. Se (ak, bk) = (−1, 1) o (ak, bk) = (+1, −1) si ha semplicemente xk 2M+y k 2M =x k−1± wk 2M +y k−1∓ wk 2M =x k−1 2M +y k−1 2M e la condizione `e verificata.
Dobbiamo considerare quindi i rimanenti quattro casi possibili.
1. Se (ak, bk) = (1, 1) e xk−12M+yk−12M = [t]2M, abbiamo wk = 2M − t, da cui xk 2M +y k 2M =x k−1 2M +y k−1 2M+ [4M − 2t]2M = [−t]2M. 2. Se (ak, bk) = (1, 1) e xk−1 2M+y k−1 2M = [−t]2M, abbiamo w k = t, da cui xk 2M +y k 2M =x k−1 2M +y k−1 2M+ [2t]2M = [t]2M. 3. Se (ak, bk) = (−1, −1) e xk−1 2M+y k−1 2M = [t]2M, abbiamo w k = t, da cui xk 2M +y k 2M =x k−1 2M +y k−1 2M+ [−2t]2M = [−t]2M.
4. Se (ak, bk) = (−1, −1) e xk−1 2M+y k−1 2M = [−t]2M, abbiamo w k = 2M − t, da cui xk 2M+y k 2M =x k−1 2M+y k−1 2M+ [−4M + 2t]2M = [t]2M.
Dal lemma appena dimostrato segue che la linea che passa per (0, t) intersecher`a le rette solo nei punti del tipo
[t]2M, [0]2M , [0]2M, [t]2M , [−t]2M, [0]2M , [0]2M, [−t]2M .
Lemma 1.12. Ogni punto ammissibile (xk, yk) che sia intersezione tra la linea con
ori-gine in (0, t) e le rette del tipo x = 2cM e y = 2dM , con c, d ∈ N, verifica la seguente condizione xk 4M −y k 4M = [t]4M _ xk 4M −y k 4M = [−t]4M . Dimostrazione. Procediamo per induzione su k.
Per k = 1 abbiamo x1 4M−y 1 4M = [0]4M − [t]4M = [−t]4M e la tesi `e verificata.
Sia dunque k > 1 e supponiamo la tesi verificata fino a k − 1. Dimostriamo che `e vera anche per k. Se ak, bk = 1, 1 o ak, bk = − 1, −1 si ha xk 4M −y k 4M =x k−1± wk 4M −y k−1± wk 4M =x k−1 4M −y k−1 4M e la condizione `e verificata.
Rimangono da verificare i casi ak, bk = − 1, 1 e ak, bk = 1, −1. Per ipotesi
induttiva la (k − 1)-esima intersezione verifica xk−1 4M −y k−1 4M = [t]4M _ xk−1 4M−y k−1 4M = [−t]4M .
A. xk−1 2M,y k−1 2M =[0]2M, [t]2M. B. xk−1 2M,y k−1 2M =[t]2M, [0]2M. C. xk−1 2M,y k−1 2M =[0]2M, [−t]2M. D. xk−12M,yk−12M=[−t]2M, [0]2M.
Supponiamo sia vera la condizione A. Passando da modulo 2M a modulo 4M abbiamo quattro possibilit`a: 1. Se xk−1 4M,y k−1 4M
=[0]4M, [t]4M, `e verificata l’ipotesi induttiva: xk−1
4M −y k−1
4M = [−t]4M.
2. Se xk−14M,yk−14M=[2M ]4M, [t]4M, non `e verificata l’ipotesi induttiva: xk−1 4M −y k−1 4M = [2M − t]4M. 3. Se xk−1 4M,y k−1 4M
=[0]4M, [t + 2M ]4M, non `e verificata l’ipotesi indut-tiva: xk−1 4M−y k−1 4M = [−2M − t]4M = [+2M − t]4M. 4. Se xk−1 4M,y k−1 4M
=[2M ]4M, [t + 2M ]4M, `e verificata l’ipotesi indutti-va:
xk−1
4M −y k−1
4M = [−t]4M.
Solo le condizioni 1 e 4 verificano l’ipotesi induttiva. Se ak, bk = 1, −1 sia nella 1
che nella 4 ricaviamo wk = t e si ha
xk 4M −y k 4M =x k−1 4M−y k−1 4M + [t]4M + [t]4M = [t]4M.
Se invece ak, bk = − 1, 1 sia nella 1 che nella 4 ricaviamo wk= 2M − t e si ha
xk 4M −y k 4M =x k−1 4M −y k−1 4M+ [−2M + t]4M + [2M + t]4M = [t]4M. e la tesi `e verificata.
Supponiamo sia vera la condizione B. Passando da modulo 2M a modulo 4M abbiamo le seguenti quattro possibilit`a:
1. Se xk−1
4M,y k−1
4M
=[t]4M, [0]4M, `e verificata l’ipotesi induttiva: xk−1 4M −y k−1 4M = [t]4M. 2. Se xk−1 4M,y k−1 4M
=[t]4M, [2M ]4M, non `e verificata l’ipotesi induttiva: xk−1 4M −y k−1 4M = [t − 2M ]4M. 3. Se xk−1 4M,y k−1 4M
=[t + 2M ]4M, [0]4M, non `e verificata l’ipotesi indut-tiva: xk−1 4M−y k−1 4M = [2M + t]4M. 4. Se xk−1 4M,y k−1 4M = [2M + t]4M, [2M ]4M
, `e verificata l’ipotesi indutti-va:
xk−1
4M −y k−1
4M = [t]4M.
Solo le condizioni 1 e 4 verificano l’ipotesi induttiva. Se ak, bk = 1, −1, sia nella 1 che nella 4 ricaviamo wk = 2M − t e si ha
xk 4M−y k 4M =x k−1 4M −y k−1 4M+ [2M − t]4M + [2M − t]4M = [−t]4M.
Se invece ak, bk = − 1, 1 sia nella 1 che nella 4 ricaviamo wk= t e si ha
xk 4M −y k 4M =x k−1 4M−y k−1 4M + [−t]4M + [−t]4M = [−t]4M e la tesi `e verificata.
Supponiamo sia vera la condizione C. Passando da modulo 2M a modulo 4M abbiamo le seguenti quattro possibilit`a:
1. Se xk−14M,yk−14M=[0]4M, [2M − t]4M, non `e verificata l’ipotesi indut-tiva:
xk−1
4M −y k−1
2. Se xk−1
4M,y k−1
4M
=[0]4M, [−t]4M, `e verificata l’ipotesi induttiva: xk−1 4M −y k−1 4M = [t]4M. 3. Se xk−1 4M,y k−1 4M
=[2M ]4M, [2M − t]4M, `e verificata l’ipotesi indutti-va: xk−1 4M −y k−1 4M = [t]4M. 4. Se xk−1 4M,y k−1 4M
=[2M ]4M, [−t]4M, non `e verificata l’ipotesi indutti-va:
xk−1
4M−y k−1
4M = [2M + t]4M.
Solo le condizioni 2 e 3 verificano l’ipotesi induttiva. Se ak, bk = 1, −1, sia nella 2
che nella 3 ricaviamo wk = 2M − t e si ha
xk 4M−y k 4M =x k−1 4M −y k−1 4M+ [2M − t]4M + [2M − t]4M = [−t]4M.
Se invece ak, bk = − 1, 1, sia nella 2 che nella 3 ricaviamo wk = t e si ha
xk 4M −y k 4M =x k−1 4M−y k−1 4M + [−t]4M + [−t]4M = [−t]4M e la tesi `e verificata.
Supponiamo sia vera la condizione D. Passando da modulo 2M a modulo 4M abbiamo le seguenti quattro possibilit`a:
1. Se xk−14M,yk−14M=[2M − t]4M, [0]4M, non `e verificata l’ipotesi indut-tiva: xk−1 4M −y k−1 4M = [2M − t]4M. 2. Se xk−1 4M,y k−1 4M
=[−t]4M, [0]4M, `e verificata l’ipotesi induttiva: xk−1
4M −y k−1
4M = [−t]4M.
3. Se xk−14M,yk−14M=[2M − t]4M, [2M ]4M, `e verificata l’ipotesi indutti-va:
xk−1
4M −y k−1
4. Se xk−1
4M,y k−1
4M
=[−t]4M, [2M ]4M, non `e verificata l’ipotesi indutti-va:
xk−1
4M −y k−1
4M = [−2M − t]4M.
Solo le condizioni 2 e 3 verificano l’ipotesi induttiva. Se ak, bk = − 1, +1, sia nella 2
che nella 3 ricaviamo wk = 2M − t e si ha
xk 4M −y k 4M =x k−1 4M −y k−1 4M+ [−2M + t]4M + [−2M + t]4M = [t]4M.
Se invece ak, bk = + 1, −1, sia nella 2 che nella 3 ricaviamo wk = t e si ha xk 4M −y k 4M =x k−1 4M −y k−1 4M + [t]4M + [t]4M = [t]4M e la tesi `e verificata.
Dimostrazione del Teorema 1.10. Supponiamo che il punto ammissibile (x, y) di R(2p, 2q) verifichi le condizioni seguenti (dove t `e dispari e compreso tra 0 e 2M ):
1. [x]2M = [0]2M W [y]2M = [0]2M , 2. [x]2M + [y]2M = [t]2M W [x]2M + [y]2M = [−t]2M , 3. [x]4M − [y]4M = [t]4M W [x]4M− [y]4M = [−t]4M .
Allora anche punti ammissibili del tipo x+4rM, y, x, y+4rM , x+2M +4rM, y+2M e x + 2M, y + 2M + 4rM le verificano per r intero. Invece punti ammissibili del tipo x + 2M + 4rM, y e x, y + 2M + 4rM con r intero non verificano la terza condizione. In altre parole i punti (w, z) con
[w]4M = [x]4M ^ [z]4M = [y]4M oppure con [w]4M = [x + 2M ]4M ^ [z]4M = [y + 2M ]4M verificano le tre condizioni, mentre quelli con
[w]4M = [x + 2M ]4M
^
[z]4M = [y]4M
oppure con [w]4M = [x]4M ^ [z]4M = [y + 2M ]4M
non verificano la terza. Sappiamo che la linea di R(2p, 2q) che ha origine in (0, t), con t dispari compreso tra 0 e 2M , passa di sicuro per 2M − t, 2M, per 2M, 2M − t e per t, 0, un punto per ogni lato del quadrato di lato 2M e lati sulle rette x = 0, x = 2M, y = 0 e y = 2M . Per le condizioni dimostrate non ci sono altri punti dei lati di tale quadrato dove la linea possa passare. Questo implica che per ogni quadrato di lato 2M e lati sulle rette del tipo x = 2cM e y = 2dM , con c, d ∈ N, si avr`a al pi`u una intersezione della linea su ogni lato. Ci sono M punti ammissibili per ogni lato di tali quadrati, tanti quante sono le linee di R(2p, 2q). Ad ogni diverso t dispari tra 0 e 2M corrisponder`a dunque una linea diversa e due diverse linee non potranno intersecarsi sui bordi di tali quadrati. In ogni punto ammissibile interno alla griglia R(2p, 2q) che sia anche punto di intersezione tra una linea e le rette sopra citate avremo una autointersezione di una linea. Dato che solo una linea potr`a passare per quel punto dovr`a passarci due volte, percorrendo entrambe le direzioni possibili.
Rimane da dimostrare che le linee non si autointersecano nei punti ammissibili interni ai quadrati di lato 2M e lati sulle rette del tipo x = 2cM e y = 2dM . Allo scopo notiamo che la struttura delle linee in ognuno di tali quadrati `e la stessa di R(2M, 2M ) (non considerando l’ordine delle linee), dato che coincide su ogni punto ammissibile sui lati.
Struttura e numerazione delle linee. Grazie a quanto dimostrato siamo in grado di caratterizzare completamente la struttura delle linee in R(2p, 2q).
Numeriamo progressivamente le linee di R(2p, 2q) contandole in direzione delle y positive e partendo da quella che origina in (0, 1). Facciamo lo stesso con quelle di R(2M, 2M ). Di fatto la linea numero s sar`a quella che passa da (0, t), con t = 2s − 1, dove s ∈ N e 0 < s ≤ M . Possiamo allora associare ogni linea di R(2M, 2M ) ad una di R(2p, 2q), quella con lo stesso numero. Consideriamo le Mpq2 sottogriglie quadrate
di R(2p, 2q) di lato 2M e lati sulle rette del tipo x = 2cM e y = 2dM , c, d ∈ N, e confrontiamole con R(2M, 2M ). Avremo due sole possibilit`a. Una sottogriglia cui corrisponde lo stesso ordine di numerazione delle linee rispetto a quelle di R(2M, 2M ) e una con l’ordine invertito. Notiamo che questi due tipi sono disposti a scacchiera (Figura 1-3).
Figura 1-3: Tre linee su R(48, 36). Sono evidenziate le sottogriglie quadrate di lato 2M = 12 e lati sulle rette del tipo x = 2cM e y = 2dM , con c, d ∈ N.
1.4
Un algoritmo per identificare le intersezioni tra
le linee
Vedremo adesso che siamo in grado di sapere quali linee si incontrano in un punto ammissibile conoscendo le sue coordinate.
Due diverse linee si incontrano in quattro punti ammissibili interni di ogni sottogriglia quadrata di R(2p, 2q) di lato 2M e lati sulle rette del tipo x = 2cM e y = 2dM , c, d ∈ N (Figura 1-3). Per vedere come vanno le cose consideriamo la sottogriglia R(2M, 2M ). Utilizziamo la numerazione delle linee introdotta nell’ultimo capoverso del precedente paragrafo. Prendiamo due linee a e b, con b > a. Un punto di intersezione tra la linea a e la linea b si trova sull’intersezione tra la retta y = x + 2a − 1 (la retta su cui si trovano i segmenti con incremento (1, 1) e punto iniziale (0, 2a − 1), in parole povere il viaggio di andata della linea a) e la retta y = −x + 2b − 1 (la retta su cui si trovano i segmenti con incremento (−1, 1) e punto iniziale (0, 2b − 1), il viaggio di ritorno della linea b), ovverosia il punto (b − a, b + a − 1). Allo stesso modo troviamo altri tre punti di intersezione: (b+a−1, b−a), (2M −b+a, 2M −b−a+1) e (2M −b−a+1, 2M −b+a), per un totale di quattro. Non ci sono altri punti di intersezione tra due diverse linee che siano interni alla sottogriglia R(2M, 2M ). Infatti il numero dei punti ammissibili interni di R(2M, 2M ) `e 2M2− 2M . D’altra parte le linee sono M e i modi diversi di prenderne due sono M2. Quattro intersezioni per ogni coppia di linee fa 4 M2 = 4M (M −1)2 = 2M2− 2M , esaurendo i punti ammissibili interni. Se a = b abbiamo una unica linea, i punti descritti sono i punti dove la linea si autointerseca oppure dove viene riflessa sulle pareti. Il punto (b − a, b + a − 1) `e (0, 2a − 1), ovvero il punto di partenza della linea.
Consideriamo un punto ammissibile (x, y) di R(2p, 2q). In (x, y) si intersecano due linee, non necessariamente diverse, a e b, con b ≥ a. Quello che faremo `e trovare un punto ammissibile in R(2p, 2q)T R(2M, 2M ) visitato dalle stesse linee di (x, y). Sar`a quindi uno dei quattro punti descritti sopra. A questo punto sar`a facile trovare (b − a, b + a − 1) da cui ricaveremo a e b. Consideriamo fM : Z2 → (0, 4M ) × (0, 4M ), fM x, y = [x]4M, [y]4M . Come conseguenza della struttura delle linee di R(2p, 2q) dimostrata nel precedente paragrafo, possiamo notare che fM−1fM x, y
T R(2p, 2q) `e un insieme di punti ammissibili visitati dalle stesse linee. Solo uno di questi si trova in fM−1fM x, y
Primo passo. Consideriamo (x1, y1) = fM−1 fM x, y \ R(2p, 2q)\R(4M, 4M ). In pratica x1 e y1 sono i resti delle divisioni di x e y per 4M .
Secondo passo. Notiamo che in R(2p, 2q)T R(4M, 4M ) le linee sono simmetriche rispetto alla retta x = 2M e anche rispetto alla retta y = 2M . Se x1 > 2M prendiamo
x2 = 4M − x1, altrimenti x2 = x1. Facciamo la stessa operazione sulla y. Abbiamo cos`ı
trovato un punto (x2, y2) di R(2p, 2q)T R(2M, 2M ) che `e intersezione delle medesime
linee di (x, y).
Terzo passo. Notiamo che in R(2p, 2q)T R(2M, 2M ) le linee sono simmetriche rispet-to alla retta y = x e anche rispetrispet-to alla retta y = −x + 2M (le diagonali del quadrarispet-to). Se y2 > −x2+ 2M prendiamo x3 = 2M − x2 e y3 = 2M − y2, altrimenti x3 = x2 e y3 = y2.
Quarto ed ultimo passo. Se y3 < x3 prendiamo y4 = x3, x4 = y3, altrimenti y4 = y3 e
x4 = x3.
Infine consideriamo il punto finale (x4, y4). Sappiamo che `e visitato dalle stesse linee
di (x, y) e per costruzione corrisponde al punto (b − a, b + a − 1) per due linee con b ≥ a. Quindi otteniamo
a = y4−x4+1
2 e b =
y4+x4+1
Capitolo 2
Griglie con specchi interni
Possiamo estendere le griglie includendo specchi a doppia superficie riflettente posti nei punti ammissibili interni. Di fatto possiamo definire questi specchi interni sostituendo la matrice identit`a associata ad un punto ammissibile interno alla griglia con la matrice
+1 0 0 −1
!
(specchio orizzontale) o la matrice −1 0 0 +1
!
(specchio verticale).
2.1
Inserimento di uno specchio in una griglia
In questa sezione vedremo cosa succede, in generale, inserendo uno specchio in una griglia. Teorema 2.1. Inserendo uno specchio in un’autointersezione di una linea un orienta-mento lascer`a integra la linea, l’altro la spezzer`a in due.
Dimostrazione. Numeriamo i segmenti ammissibili incidenti nell’intersezione in ordine di visita nella costruzione della linea. Inserendo uno specchio invece di proseguire nella normale costruzione la linea effettuer`a una riflessione. Non potendo tornare indietro ripercorrendo il segmento numero 1 o andare avanti in linea retta percorrendo il segmento numero 2, dovr`a percorrere il numero 3 o il numero 4.
• Un orientamento dello specchio far`a deviare la costruzione della linea ad imboccare il percorso di ritorno pi`u breve percorrendo il segmento numero 4. La linea viene spezzata, dato che un “ramo” di essa non verr`a percorso.
• L’altro orientamento dello specchio far`a deviare la costruzione della linea ad imboc-care il numero 3 e le far`a percorrere il cammino dal numero 3 al numero 2 in verso
contrario rispetto al verso di percorrenza originario. Dopo aver percorso il numero 2 una seconda riflessione la obbligher`a ad imboccare il numero 4 e completare il percorso fino al punto di partenza. In questo caso la linea viene percorsa per intero anche se una parte viene percorsa in verso contrario rispetto al verso di percorrenza originario (Figura 2-1).
(a) Linea di R(12, 8) con punto di partenza in (0, 1). (b) Linea di R(12, 8) con punto di partenza in (0, 1) e specchio orizzontale in (3, 4). (c) Linea di R(12, 8) con punto di partenza in (0, 1) e specchio verticale in (3, 4). Figura 2-1: Esempio.
Numerare tutti i segmenti visitati da una linea nell’ordine di visita quindi `e condizione sufficiente per riconoscere in ogni autointersezione quale sia l’orientamento da usare per porre uno specchio in modo da non spezzare la linea. Tuttavia limitarci a numerare i segmenti modulo due basta allo scopo (cfr. [4]).
Teorema 2.2 (De Michieli Vitturi & Favilli). Numeriamo modulo 2 i seg-menti ammis-sibili visitati da una linea nell’ordine di visita. Uno specchio posto in un’autointersezione in modo da separare i segmenti con numeri diversi non spezzer`a la linea.
Per dimostrare il teorema avremo bisogno del seguente lemma.
Lemma 2.3. Ogni volta che una linea durante la sua costruzione visita un punto una seconda volta, dalla prima volta alla seconda avr`a visitato un numero pari di segmenti ammissibili.
Dimostrazione. Mettiamo che la linea passi due volte per il punto P = (x, y). Conside-riamo la sola x. Nella costruzione della linea ad ogni passo viene sommato 1 oppure −1 alla x. Per poter visitare nuovamente lo stesso punto dovremo quindi sommare lo stesso numero di 1 e −1, ottenendo un numero pari di passi e quindi di segmenti ammissibili.
Dimostrazione del Teorema 2.2. Consideriamo un punto ammissibile dove non sia pre-sente uno specchio e che sia autointersezione di una linea. La linea visiter`a questo punto due volte percorrendo tutti e quattro i segmenti ammissibili incidenti. Numeriamoli come nella dimostrazione del Teorema 2.1. Consideriamo il numero 2 e il numero 3. Essi ap-partengono al ramo della linea che viene percorso tra la prima visita al punto considerato e la seconda. Questo ramo `e composto da un numero pari di segmenti ammissibili (per il Lemma 2.3), quindi i due segmenti avranno numeri diversi nella numerazione progressiva modulo due. Stesso discorso vale per l’altro ramo e per gli altri due segmenti ammissi-bili, il numero 1 e il numero 4. Anche il numero 1 e il numero 2 devono avere numeri diversi nella numerazione progressiva modulo due essendo percorsi uno dopo l’altro. Ri-capitolando, il numero 1 e il 3 avranno uno stesso numero nella numerazione modulo 2, il 2 e il 4 avranno l’altro. Mettendo uno specchio in modo da separare i segmenti con numeri diversi nella numerazione modulo 2, ovvero posto in modo che la riflessione faccia percorrere il numero 3 dopo il numero 1 e il numero 4 dopo il numero 2, la linea rimarr`a integra, come visto nella dimostrazione del Teorema 2.1 (Figura 2-2).
Nel seguito associeremo ad ogni segmento visitato da una linea un colore, verde o rosso, a seconda che sia crescente o meno l’ordinata nella costruzione della linea.
Otteniamo un altro modo, equivalente, per decidere l’orientamento di uno specchio. Teorema 2.4. Uno specchio lascer`a integra una linea se posto orizzontalmente in un’au-tointersezione dove i quattro segmenti incidenti hanno associato lo stesso colore, verti-calmente altrimenti.
Dimostrazione. Se i quattro segmenti incidenti hanno associato lo stesso colore possie-dono tutti e quattro l’ordinata dell’incremento positiva, oppure tutti e quattro negativa. Numeriamoli come nella dimostrazione del Teorema 2.1. Sia P = (x0, y0) il punto
con-siderato. In entrambi i casi il numero 1 e il numero 3 si troveranno dalla stessa parte rispetto alla retta y = y0 e il numero 2 e il 4 dalla parte opposta. Quindi uno specchio
orizzontale mander`a il numero 1 nel numero 3 ed il numero 2 nel numero 4 e la linea rimarr`a integra, come visto nella dimostrazione del Teorema 2.1. Il caso in cui i numeri 1 e 2 abbiano associato un colore diverso rispetto al 3 e al 4, la dimostrazione `e analoga, ma occorrer`a riferirsi alla retta x = x0 (Figura 2-3).
Notiamo che i teoremi visti in questa sezione si applicano a qualunque tipo di griglia per cui una linea possa avere un’autointersezione, indipendentemente dalla forma dei
(a) Linea con punto di par-tenza in (0, 1) di R(12, 8).
(b) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio orizzontale in (3, 4).
(c) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio verticale in (3, 4).
(d) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio orizzontale in (4, 5).
(e) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio verticale in (4, 5).
Figura 2-2: Esempio. Invece di numerare i segmenti modulo due abbiamo colorato di grigio o nero i quadrati di lato uno attraversati dai segmenti.
(a) Linea con punto di par-tenza in (0, 1) di R(12, 8).
(b) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio orizzontale in (3, 4).
(c) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio verticale in (3, 4).
(d) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio verticale in (4, 5).
(e) Linea con punto di par-tenza in (0, 1) di R(12, 8) con specchio orizzontale in (4, 5).
bordi e dal numero e l’orientamento di specchi interni gi`a presenti. Infatti le uniche ipotesi usate nelle dimostrazioni sono il modo di costruzione delle linee e il fatto che in quel punto ci sia un’autointersezione.
Vediamo adesso cosa succede inserendo uno specchio in un punto diverso da un’au-tointersezione.
Teorema 2.5. Inserendo uno specchio in un punto interno alla griglia visitato da due diverse linee si otterr`a la loro fusione.
Dimostrazione. Notiamo che il teorema vale per entrambi gli orientamenti possibili dello specchio. Consideriamo una delle due linee, chiamiamola linea A. Nella sua costruzione arriveremo allo specchio. Riflettendo sullo specchio la costruzione della linea cambier`a direzione, passando dalla traiettoria della linea A alla B. Percorrer`a la traiettoria della linea B interamente tornando allo specchio, nello stesso punto quindi, ma ci arriver`a dalla parte opposta. Ritorner`a quindi dopo la successiva riflessione sulla traiettoria della linea A ma nel tratto ancora da percorrere (visto che `e quello dall’altra parte dello specchio rispetto alla prima riflessione) ritornando quindi al punto di partenza dopo aver percorso entrambe le linee interamente.
E’ da notare che sebbene entrambi gli orientamenti possibili dello specchio provochino la fusione delle linee i loro effetti nella costruzione della linea differiscono: la costruzione della linea B avviene in versi opposti (Figura 2-4).
2.2
Inserimento di uno specchio in una griglia priva
di specchi interni.
Vedremo adesso che se la griglia `e priva di specchi interni siamo in grado di sapere quali siano i segmenti con ordinata dell’incremento positiva.
Consideriamo R(2p, 2q) e chiamiamo M = mcd(p, q). La struttura delle linee evi-denziata nella Sezione 1.3 si mantiene inalterata anche per quanto riguarda il modo di costruzione.
Teorema 2.6. Le sottogriglie quadrate di R(2p, 2q) di lato 2M e lati sulle rette del tipo x = 2cM e y = 2dM , con c, d ∈ N, che abbiano lo stesso ordine di numerazione delle
(a) Due linee di R(24, 18). (b) Linea di R(24, 18) con punto di parten-za in (0, 3) e specchio orizzontale in (1, 4).
(c) Linea di R(24, 18) con punto di partenza in (0, 3) e specchio verticale in (1, 4).
linee rispetto a quelle di R(2M, 2M ) hanno anche la propriet`a che a segmenti corrispon-denti `e associato lo stesso colore. Quelle che hanno l’ordine inverso rispetto a quelle di R(2M, 2M ) hanno tra di loro lo stesso tipo di corrispondenza.
Dimostrazione. Dimostreremo il teorema analizzando la struttura della costruzione di una linea in dettaglio. La struttura delle linee (Sezione 1.3) `e tale per cui si alternano a scacchiera sottogriglie quadrate di R(2p, 2q) di lato 2M e lati sulle rette del tipo x = 2cM e y = 2dM , con c, d ∈ N, con lo stesso ordine di numerazione delle linee rispetto a quelle di R(2M, 2M ) e altre con ordine di numerazione invertito. Sappiamo che in assenza di specchi interni le riflessioni avvengono solo sui bordi che necessariamente hanno come coordinate multipli di 2M . Numeriamo come in Figura 2-5 i tratti della linea interni a questi due tipi di sottogriglie e delimitati dai bordi. Sappiamo che, seppure la Figura 2-5 si riferisce ad un caso particolare, la struttura di ogni possibile linea `e identica all’esempio negli aspetti qui considerati. Per ogni tratto della linea possiamo quindi esaminare quale pu`o essere il tratto successivo e di che colore sar`a. Verificheremo che i colori sono rispettati ad ogni passo. Il tratto numero 1, di colore verde, in assenza di riflessione orizzontale al bordo avr`a come successore il tratto 7 sempre di colore verde, altrimenti avr`a come successore il tratto 4, di colore rosso per l’avvenuta riflessione orizzontale. Il tratto 2, di colore rosso, avr`a come successori possibili i tratti 3 (verde) o 8 (rosso). Il tratto 3 (verde) avr`a come successori possibili i tratti 1 e 6 (entrambi verdi poich´e una riflessione verticale non cambia il colore nella costruzione). Il 4 (rosso) avr`a i tratti 2 e 5 (entrambi rossi). Il 5 (rosso) avr`a i tratti 4 (rosso) e 7 (verde). Il 6 (verde) avr`a i tratti 3 (verde) e 8 (rosso). Il 7 (verde) avr`a i tratti 1 e 6 (entrambi verdi). Infine il tratto numero 8 (rosso) avr`a come possibili successori i tratti 2 e 5 (entrambi rossi).
Corollario 2.7. Le autointersezioni dove tutti e quattro i segmenti incidenti hanno lo stesso colore si trovano sulle rette x = 2cM , con c ∈ N, quelle con segmenti di colori diversi sulle rette y = 2dM , con d ∈ N.
Questo corollario `e un’ovvia conseguenza del Teorema 2.6 e del fatto che uno spec-chio verticale non cambia l’ordinata dell’incremento mentre uno specspec-chio orizzontale la cambia.
Come conseguenza del Teorema 2.6 e del Corollario 2.7 sappiamo adesso come mettere uno specchio in una autointersezione di una linea in una griglia senza specchi interni in modo da lasciare integra la linea. Mettere uno specchio orizzontale in un punto ammis-sibile interno con ascissa uguale ad un multiplo di 2M lascer`a integra la linea cos`ı come
Figura 2-5: Costruzione della linea 1 su parte di R(2p, 2q) con mcd(p, q) = 4. Sono evidenziate le sottogriglie quadrate di lato 2M = 8 e lati sulle rette del tipo x = 2cM e y = 2dM , con c, d ∈ N.
metterne uno verticale se `e l’ordinata ad essere uguale ad un multiplo di 2M . Ovvia-mente nel caso M = 1 questo significa che in tutti i punti ammissibili interni con ascissa pari dovremo usare uno specchio orizzontale per mantenere integra la linea, per lo stesso scopo dovremo invece usarne uno verticale nei punti con ascissa dispari.
Ricapitolando, siamo in grado di sapere in dettaglio cosa succede inserendo uno spec-chio in una griglia R(2p, 2q) priva di specchi interni. Se lo inseriamo in un punto interno (x, y) con x oppure y multipli di 2M lo specchio si trover`a in una autointersezione di una linea. Per identificare la linea che si autointerseca in quel punto usando le sole coordi-nate (senza dover disegnare le linee) si pu`o utilizzare l’algoritmo descritto nella Sezione 1.4. Per sapere l’effetto dell’orientamento dello specchio si applicano le osservazioni fatte dopo il Corollario 2.7. Se invece n´e x n´e y fossero multipli di 2M potremmo identi-ficare le due linee che visitano quel particolare punto utilizzando l’algoritmo descritto nella Sezione 1.4. Sappiamo dal Teorema 2.5 che otterremmo la fusione delle due linee indipendentemente dall’orientamento dello specchio.
2.3
Griglie monolineari
La maggior parte dei Sona giunti fino a noi grazie al lavoro di alcuni antropologi (ad esempio [9]) sono composti da una sola linea. Gerdes ha ipotizzato che molti dei Sona composti da pi`u linee siano stati creati monolineari e la forma giunta a noi sia frutto di errori. Ha supportato questa tesi mostrando le piccole variazioni necessarie ad ognuno di questi Sona per ottenere la monolinearit`a. Gerdes ha dedotto da tutto questo che la monolinearit`a per i Chokwe dovesse avere una grande importanza.
Abbiamo visto che mettere uno specchio all’intersezione di due linee provoca la loro fusione. Partendo da R(2p, 2q) occorrono quindi mcd(p, q) − 1 specchi per ottenere la monolinearit`a.
Vediamo adesso che `e possibile scegliere gli orientamenti di questi specchi in mo-do da ricalcare la costruzione di un’unica linea in una griglia con mcd(p, q) = 1. Se mcd(p, q) = 1 in una griglia senza specchi interni i segmenti paralleli adiacenti vengono percorsi in direzioni opposte (conseguenza del Teorema 2.6) e i segmenti posti sulla stessa retta vengono percorsi tutti nello stesso verso. L’orientamento di uno specchio posto in un’autointersezione per non spezzare la linea deve essere verticale se l’ascissa del punto `
queste caratteristiche in un punto, un ramo della linea, quello percorso dopo la prima riflessione sullo specchio, verr`a percorso in verso opposto rispetto al senso di percorrenza originario (Teorema 2.1).
Se mcd(p, q) > 1, poniamo specchi orizzontali in (1, 2), (1, 4), (1, 6), ...,1, 2 mcd(p, q)− 1. Sappiamo che sono tutti punti dove si intersecano linee in successione crescente: in (1, 2k − 1), con k ∈ {1, ..., mcd(p, q)}, si incrociano infatti la linea k e la linea k + 1. Inoltre l’orientamento degli specchi scelto `e opposto rispetto a quello necessario per non spezzare una linea se ognuno di quei punti fosse un’autointersezione. Quindi se la prima linea che incontra lo specchio `e percorsa nel verso “giusto”, ricalcando la costruzione di un’unica linea in una griglia con mcd(p, q) = 1, anche l’altra linea lo sar`a. Otteniamo quindi la fusione di tutte le linee e ogni linea sar`a percorsa ricalcando la struttura di una griglia senza specchi interni e mcd(p, q) = 1: le linee dispari saranno percorse nel verso originario, quelle pari nel verso opposto. Vedremo nel prossimo teorema pi`u in dettaglio come vanno le cose (cfr. [19]).
Teorema 2.8. Supponiamo che in una griglia ci sia una sola linea. Supponiamo anche che tutti gli specchi interni siano posti con orientamento orizzontale se l’ascissa del punto `
e dispari e verticale se l’ascissa `e pari. Allora i segmenti posti sulle rette y = x + 2k + 1, con k ∈ {0, ..., q − 1}, quando k `e pari vengono percorsi con ordinata dell’incremento crescente, quando k `e dispari con ordinata dell’incremento decrescente. Analogamente, i segmenti posti sulle rette y = −x + 2j + 1 con j ∈ {0, ..., p − 1} quando j `e pari vengono percorsi con ordinata dell’incremento crescente, quando j `e dispari con ordinata dell’incremento decrescente.
Dimostrazione. Consideriamo i vari pezzi della linea tra una riflessione e la successiva considerando le riflessioni sia su specchi interni che sulle pareti. In ogni caso gli specchi dove possono avvenire le riflessioni hanno orientamento orizzontale se l’ascissa del punto `
e dispari e verticale se l’ascissa `e pari. Sappiamo che gli specchi verticali lasciano inalte-rata l’ordinata dell’incremento e invertono l’ascissa, viceversa quelli orizzontali lasciano inalterata l’ascissa dell’incremento e invertono l’ordinata. Per costruzione il primo pezzo della linea viene percorso nel verso giusto, il verso della tesi del teorema. Mostreremo che ogni pezzo della linea percorso nel verso giusto `e seguito da un pezzo ancora percorso nel verso giusto. Consideriamo il punto ammissibile dove `e presente lo specchio al termine del pezzo della linea che per ipotesi `e percorso nel verso giusto. I segmenti ammissibili che incidono su quel punto sono su rette del tipo y = x + 2k + 1 e y = −x + 2j + 1, da
cui la condizione x + k = j. Questi tre sono tutti numeri interi quindi o sono tutti pari o due di loro sono dispari. Analizziamo i vari casi. Nel caso in cui x `e dispari avremo che solo uno tra k e j `e dispari e lo specchio `e orizzontale. La riflessione sposta la costruzione da una retta all’altra, quindi da k pari si passa a j dispari o viceversa , inoltre cambia il segno dell’ordinata dell’incremento e la tesi `e provata. Nel caso in cui x `e pari avremo lo specchio verticale e k e j saranno entrambi pari o entrambi dispari. Qui la riflessione sullo specchio verticale non modifica l’ordinata dell’incremento e la costruzione si sposta da una retta all’altra provando la tesi.
Unendo il risultato del Teorema 2.8 a quello del Teorema 2.2 otteniamo quanto segue. Corollario 2.9. Supponiamo che in una griglia ci sia una sola linea e tutti gli specchi interni siano posti con orientamento orizzontale se l’ascissa del punto `e dispari e verticale se l’ascissa `e pari. Allora la numerazione modulo 2 dei segmenti ammissibili, numerati nell’ordine di visita, `e come in Figura 2-6.
Figura 2-6: R(32, 24). Abbiamo posto specchi orizzontali in (1, 2), (1, 4) e (1, 6). Invece di etichettare con uno o zero i segmenti ammissibili abbiamo colorato rispettivamente di grigio o nero i quadrati di lato uno attraversati dai segmenti ammissibili. Per i segmenti ammissibili abbiamo utilizzato i colori verde e rosso per evidenziare rispettivamente la crescenza o meno dell’ordinata nella costruzione della linea.
Capitolo 3
Curve di riflessione e grafi
In questo capitolo presenteremo un modo differente di affrontare lo studio delle curve di riflessione da quello fin qui seguito. Seguendo [5] vedremo le curve di riflessione dal punto di vista della teoria dei grafi.
3.1
Notazione essenziale
Introduciamo la notazione a cui ci atterremo in questo paragrafo.
Utilizzeremo A[2] per indicare l’insieme di tutti i sottoinsiemi di A con 2 elementi.
Utilizzeremo A(2) per indicare l’insieme delle classi di equivalenza dell’insieme A × A con
la relazione di equivalenza (a, b) ≡ (b, a) ∀(a, b) ∈ A × A.
Un grafo semplice `e una coppia di insiemi G = V, E tali che E ⊆ V[2]. Gli elementi di V sono detti vertici, mentre gli elementi di E sono detti archi. Un arco e ∈ E `e incidente su un vertice v ∈ V se v ∈ e.
Un grafo G `e una tripla VG, EG, ϕG dove VG, EG sono insiemi disgiunti (VG insieme
dei vertici, EG insieme degli archi) e ϕG : EG → V (2)
G che assegna ad ogni arco eG una
coppia di vertici. Un arco eG ∈ EG`e incidente su un vertice vG∈ VG se vG ∈ ϕG(eG). In
tal caso vG `e detto anche estremo dell’arco eG. In un grafo `e possibile quindi avere pi`u
archi incidenti sugli stessi vertici. Si possono avere anche dei loop, ovvero archi incidenti su un unico vertice.
Due grafi G = VG, EG, ϕG
e H = VH, EH, ϕH
si dicono isomorfi se esistono due funzioni biunivoche ΨGH : VG → VH e ΛGH : EG → EH tali che se eG ∈ EG e
ϕG(eG) = n v1 G, v2G o allora ϕH ΛGH eG =nΨGH vG1, ΨGH vG2 o .
Un cammino C su un grafo `e una successione non vuota che alterna vertici e archi come segue C =v0, e0, v1, e1, ..., en−1, vn , dove ek incide su vk e vk+1, con k ∈0, ..., n − 1 .
Il cammino `e chiuso se v0 = vn. Un cammino chiuso viene detto anche ciclo. Chiamiamo
D sottocammino di C se `e un cammino contenuto propriamente in C, ovvero se D 6= C e si pu`o scrivere C = v0, e0, ..., D, ..., en−1, vn oppure C = D, ej, ..., en−1, vn oppure
anche C =v0, e0, ..., ej, D .
La lunghezza del cammino C = v0, e0, v1, e1,..., en−1, vn
`e n, il numero di archi presenti nella successione. La indicheremo con l(C).
Un grafo `e piano se i vertici sono punti del piano cartesiano e gli archi sono curve continue semplici del piano non intersecantesi tra loro e con estremi i punti corrispondenti ai vertici su cui sono incidenti come archi.
Le componenti connesse del complementare di un grafo piano sono chiamate facce del grafo. La loro frontiera `e formata da archi del grafo.
Un grafo `e planare se `e isomorfo ad un grafo piano.
Il grado di un vertice di un grafo `e il numero di volte che compare come estremo di un arco.
Un grafo `e k-regolare se ogni vertice del grafo ha lo stesso grado k.
Un grafo `e detto euleriano se esiste un cammino chiuso che passa per tutti gli archi del grafo una e una sola volta (ciclo euleriano).
Per ogni vertice v di un grafo 4-regolare piano G consideriamo un opportuno intor-no aperto Uv di v tale che Uv ∩ EG\{v} ha esattamente quattro componenti connesse.
Supponiamo inoltre che Uv ∩ Uw = ∅. Chiamiamo tali componenti connesse estremit`a
degli archi incidenti su v. Se numeriamo modulo due le estremit`a degli archi incidenti su v contandole in senso orario (non importa da quale si inizia), chiameremo consecuti-ve le estremit`a degli archi che hanno lo stesso numero. Dato un cammino su un grafo,
chiameremo consecutivi due archi incidenti sullo stesso vertice v quando sono successivi e le estremit`a incidenti su v che vengono percorse sono consecutive. Un cammino senza archi ripetuti su un grafo 4-regolare `e detto trasversale se i suoi archi successivi sono consecutivi. Un grafo 4-regolare piano `e detto gaussiano un ciclo euleriano che sia anche trasversale (tale ciclo `e detto gaussiano).
I grafi planari 4 − regolari sono isomorfi a molti differenti grafi piani 4 − regolari. Si pu`o dimostrare per`o che il numero dei cicli trasversali `e invariante, cos`ı come l’esistenza di un ciclo gaussiano. La definizione di grafo gaussiano pu`o dunque essere estesa a comprendere tutti i grafi planari 4 − regolari isomorfi ad un grafo piano gaussiano.
Sia G un grafo planare gaussiano. Sia H un grafo piano isomorfo a G. Chiameremo C = nv0
G, e0G, ..., e n−1 G , vG0
o
ciclo gaussiano di G se, chiamando ei
H = ΛGH(eiG) e vHi = ΨGH(vGi ), si ha che n v0 H, e0H, ..., e n−1 H , vH0 o ` e un ciclo gaussiano di H.
3.2
Grafi Sona
Associeremo un grafo ad una linea di una curva di riflessione che abbia almeno un’au-tointersezione e lo chiameremo grafo Sona. Considereremo come vertici del grafo i soli punti ammissibili della griglia che sono autointersezione della linea, escludendo quindi i punti dove sono presenti degli specchi. Come archi del grafo considereremo ogni unione di segmenti ammissibili consecutivi nella costruzione della linea tra un vertice e il successivo (sono ammessi i loop).
Un grafo Sona gode di particolari propriet`a. • `E un grafo piano.
• Dalla costruzione della linea segue che `e un grafo euleriano.
• `E un grafo gaussiano: `e un grafo 4-regolare ed il ciclo euleriano `e anche trasversale. Consideriamo la formula di Eulero che collega il numero dei vertici (|V |), degli archi (|E|) e delle facce (|F |) di un grafo piano connesso (per due qualsiasi vertici del grafo esiste un cammino che li ha come estremi): |V | − |E| + |F | = 2. Applichiamola ad un grafo piano gaussiano G. Chiamiamo n il numero dei vertici di G. Poich´e ogni vertice
di G ha quattro archi incidenti e ogni arco incide su due vertici ricaviamo che il numero degli archi `e il doppio del numero dei vertici. Dalla formula di Eulero ricaviamo allora che G con n vertici possiede |FG| = n + 2 facce e |EG| = 2n archi.
3.3
Generazione ricorsiva di grafi gaussiani
Seguendo [23] mostreremo ora come sia possibile generare in modo ricorsivo tutti i grafi gaussiani insieme ai loro cicli gaussiani.
Definiamo l’operazione di eliminazione di un vertice per un grafo gaussiano G con |VG| > 1. Sia v un vertice di G, sia C un ciclo gaussiano di G il cui primo vertice della
successione sia diverso da v e siano e1, e2, e3, e4 gli archi di G incidenti su v numerati
nell’ordine di comparizione in C. Si ha e1 parallelo ad e2 e e3 parallelo ad e4. Possiamo
scrivere
C = nC1, e1, v, e2, C2, e3, v, e4, C3
o .
Dove C1, C2, C3 sono sottocammini eventualmente contenenti un solo vertice di C. `E
possibile che e2 = e3 sia un loop, nel qual caso C2 `e vuoto e C1 6= C3. Consideriamo un
nuovo grafo G|v ottenuto da G eliminando il vertice v nel seguente modo. Rimpiazziamo
gli archi e1 e e3con un unico arco e13definito in modo da avere come estremi gli estremi di
e1 e e3 diversi da v. Rimpiazziamo anche gli archi e2 e e4 con un unico arco e24definito in
modo da avere come estremi gli estremi di e2 e e4 diversi da v. Il grafo G|v cos`ı ottenuto
`
e gaussiano. Sia C−2 il cammino C2 preso in senso inverso. Allora su G|v abbiamo il ciclo
gaussiano C|v = n C1, e13, C−2, e24, C3 o . Nel caso e2 = e3 fosse un loop abbiamo
C|v =
n
C1, e14, C3
o .
Possiamo dunque rimuovere qualsiasi vertice di un qualsiasi grafo gaussiano G con |VG| > 1 per ottenere un grafo gaussiano con un vertice in meno.
Teorema 3.1. Ogni grafo gaussiano G pu`o essere trasformato nel grafo contenente un unico vertice e due loop ripetendo |VG|−1 volte l’operazione di eliminazione di un vertice.
Definiamo ora l’operazione inversa alla precedente, l’operazione di introduzione di un vertice per un grafo gaussiano G.
Sia H un’immersione di G sulla sfera (un grafo isomorfo a G “disegnato” sulla sfera) e C un ciclo gaussiano di G corrispondente ad un ciclo gaussiano di H. La successione degli archi ei
G in C induce un’orientazione sugli archi corrispondenti eiH di H. Sia F una
faccia di H. Diciamo che due archi e1
Ge e2G di G, corrispondenti a due archi e1H e e2H sulla
frontiera di F , sono co-orientati se e1H e e2H posseggono la stessa orientazione rispetto all’orientazione di F . Notiamo che i nuovi archi introdotti dall’operazione di eliminazione di un vertice sono sempre co-orientati tra loro.
Siano e1G e e2Guna coppia di archi co-orientati tali che ϕG(e1G) =
n vG1, vG2 o e ϕG(e2G) = n v3 G, vG4 o
(vertici e archi sono numerati in ordine di apparizione nella successione del ciclo gaussiano C). Si pu`o avere e1
G = e2G (`e un loop) nel qual caso vG1 = vG2 = vG3 = v4G e
possiamo scrivere
C =nC1, e1G, C3
o . Altrimenti possiamo scrivere
C =nC1, e1G, C2, e2G, C3 o . Dove C1 = n v0 G, e0G, ..., v1G o , C2 = n v2 G, ..., vG3 o , C3 = n v4 G, ..., v0G o sono sottocammini, eventualmente costituiti di un solo vertice di C.
Consideriamo un nuovo grafo G|e1G,e 2
G ottenuto da G aggiungendo un nuovo vertice v,
V
G|e1G,e2G = VG ∪ {v} con v /∈ VG, e sostituendo e
1
G e e2G con quattro nuovi archi ei con
i ∈ {1, 2, 3, 4}, E
G|e1G,e2G = EG∪ {e
i} con ei ∈ E/
G, i cui estremi sono definiti nel seguente
modo: ϕ G|e1G,e2G(e i) = nv, vi G o . Nel caso e1
G= e2G sia un loop sostituiamo e1G con tre nuovi archi (uno dei quali `e un loop)
ei con i ∈ {1, 2, 3}, E
G|e1G = EG∪ {e
i} con ei ∈ E/
G, i cui estremi sono definiti nel seguente
modo: ϕ G|e1G(e 1) = ϕ G|e1G(e 2) =nv, v1 G o , ϕ G|e1G(e 3) =nv, vo.
Il grafo cos`ı ottenuto `e gaussiano. Infatti anche il vertice aggiunto v ha grado quattro e troviamo un ciclo gaussiano C|e1G,e2G come segue. Sia C−
2 il cammino C2 preso in senso
C|e1G,e2G = n C1, e1, v, e3, C−2, e 2, v, e4, C 3 o . Nel caso e1
G = e2G possiamo invece scrivere
C|e1G =
n
C1, e1, v, e3, v, e2, C3
o .
Abbiamo il seguente risultato.
Teorema 3.2. Ogni grafo gaussiano G pu`o essere ottenuto dal grafo contenente un unico vertice e due loop ripetendo |VG| − 1 volte l’operazione di introduzione di un vertice.
Sia G un grafo gaussiano e sia C = {v0, e0, ..., ei−1, v0, ei, ..., v0} un suo ciclo
gaus-siano. Nella successione presente in C il vertice di partenza v0 comparir`a tre volte.
Infatti `e presente all’inizio e alla fine come estremo dell’arco iniziale e dell’arco fina-le (che sono consecutivi). `E presente anche come estremo di altri due archi consecu-tivi della successione che sono visitati dal ciclo gaussiano. Tutti gli altri vertici del grafo compariranno invece due volte nella successione presente in C. Il vertice di par-tenza non ha un significato particolare. Se G ha almeno due vertici otteniamo un’al-tro ciclo gaussiano da C prendendo un’alun’al-tro vertice del grafo come vertice di partenza nel seguente modo. Sia C = {v0, e0, C1, ej−1, vj, ej, C2, ei−1, vj, ei, C3, ek, v0}. Si ha che
Cvj = {vj, ej, C2, ei−1, vj, ei, C3, ek, v0, e0, C1, ej−1, vj} `e un’altro ciclo gaussiano. Abbiamo
quindi numerosi sottocammini chiusi di C, tutti quelli del tipo D = {vj, ej, C2, ei−1, vj}
dove vj ∈ C/ 2. Vediamo adesso cosa si pu`o dire sulla lunghezza di questi sottocammini
chiusi.
Utilizzando la costruzione ricorsiva dei grafi gaussiani vista sopra si pu`o dimostrare il seguente teorema, dovuto a Gauss.
Teorema 3.3. Sia G un grafo gaussiano e sia C un suo ciclo gaussiano. Allora ogni sottocammino chiuso di C `e di lunghezza dispari.
Dimostrazione. Senza perdita di generalit`a, consideriamo un grafo gaussiano piano. Fa-remo la dimostrazione per induzione sul numero k dei vertici del grafo.
Caso k = 1. Un grafo gaussiano con un solo vertice `e il grafo contenente un unico vertice e due loop. In questo caso C consiste in un cammino chiuso che passa una volta per ognuno dei due loop. Un sottocammino chiuso di C perci`o contiene uno solo dei due loop, quindi ha lunghezza dispari e la tesi `e provata.
Sia dunque k > 1 e la tesi verificata fino a k − 1. Dimostriamo che `e vera anche per k. Abbiamo visto che eliminando un vertice di un grafo gaussiano di k vertici si ottiene un grafo gaussiano di k − 1 vertici. Mostreremo che se per assurdo la tesi non fosse vera per un grafo gaussiano di k vertici allora non lo sarebbe nemmeno per un grafo gaussiano di k − 1 vertici contraddicendo l’ipotesi induttiva. Sia dunque G un grafo gaussiano di k vertici con un ciclo gaussiano C. Sia D un sottocammino chiuso di C di lunghezza pari (quindi k `e un intero pari maggiore di uno). Dobbiamo trovare un opportuno vertice v da eliminare, si hanno le seguenti possibilit`a.
1. Esiste un vertice v /∈ D. In questo caso eliminando v otteniamo un grafo gaussiano di k − 1 vertici con un ciclo gaussiano C|v che contiene propriamente D, ciclo di
lunghezza pari. Assurdo.
2. Esiste un vertice v ∈ D tale che tutti e quattro gli archi incidenti su v sono presenti in D. Quindi l(D) ≥ 4. Eliminando tale v otteniamo un grafo gaussiano di k − 1 vertici con un ciclo gaussiano C|v di cui D|v `e un sottocammino chiuso. Si ha che
l(D|v) = l(D) − 2. Quindi D|v `e un ciclo di lunghezza pari. Assurdo.
3. Non esiste un vertice con le propriet`a descritte nei due punti precedenti. Senza perdita di generalit`a possiamo allora prendere C = {v0, e0, ..., ej−1, v0, ej, ..., v0}
e D = {v0, e0, ..., ej−1, v0}. Abbiamo che per ogni vertice vi, due archi incidenti
su vi compaiono in D e due in C \ D. Perci`o Dc = {v0, ej, ..., v0} ha la stessa
lunghezza di D. Visto che il numero dei vertici k `e maggiore di uno ed in C compaiono 2k archi abbiamo che l(D) = k. In questo caso non `e possibile che k sia uguale a due perch´e altrimenti C non sarebbe trasversale. Infatti si avrebbe C = {v0, e0, v1, e1, v0, e2, v1, e3, v0} e D = {v0, e0, v1, e1, v0}. Quindi tutti e quattro
gli archi inciderebbero su v0 e v1 e non potrebbero intersecarsi. Otterremmo che la
frontiera di ognuna delle quattro facce del grafo sarebbe costituita da una coppia di archi. I due archi sulla frontiera di una faccia del grafo non potrebbero essere consecutivi n´e su v0 n´e su v1. Per ogni arco esisterebbe perci`o un secondo arco
consecutivo al primo sia su v0 che su v1, contraddicendo l’ipotesi di C trasversale.
Otteniamo quindi l(D) = k > 2 e in D abbiamo almeno 4 vertici distinti e 4 archi. Consideriamo il vertice v1. Si avr`a che comparir`a una volta in D e una in
Dc. Possiamo allora scrivere C = {v
0, e0, v1, e1, C1, ej−1, v0, ej, C2, ei−1, v1, ei, C3}.