Matematica Discreta Lezione del giorno 27 marzo 2009 Teoria dei 2-disegni.

Matematica Discreta

Lezione del giorno 27 marzo 2009 Teoria dei 2-disegni.

Supponiamo che, date v squadre sportive diverse, si vogliano organizzare alcuni tornei a ognuno dei quali partecipano alcune di tali squadre, ed al termine stilare una classifica. Per equilibrare i tornei è ovviamente opportuno richiedere che:

- ad ogni torneo partecipi un numero k di squadre, con k uguale per tutti i tornei;

- ogni coppia di squadre si incontri in un numero r

di tornei, con r

uguale per tutte le coppie Esempio: sia v=8, k=4, r

=3 (in totale 8 squadre, ad ogni torneo partecipano 4 squadre, ed ogni coppia di squadre si incontra in 3 tornei). È possibile, con questi dati, organizzare i tornei? E quanti tornei? Con i dati precedenti la risposta è positiva; infatti, se l’insieme delle 8 squadre è A=1,2,3,4,5,6,7,8 si possono organizzare 14 tornei per esempio secondo lo schema seguente:

{1,2,5,6} {3,4,7,8} {1,3,5,7} {2,4,6,8} {1,4,5,8} {2,3,6,7} {1,2,3,4} {5,6,7,8}{1,2,7,8} {3,4,5,6}

{1,3,6,8} {2,4,5,7} {1,4,6,7} {2,3,5,8}

Si può verificare che ogni coppia di squadre si incontra esattamente in 3 tornei: per esempio la coppia (1,2) nel 1°, 7° e 9° torneo (si può effettuare la verifica per le altre 27 coppie……..).

Anche in questo caso si può formalizzare il problema pervenendo alla seguente definizione: fissati i numeri naturali v,k,r

si chiama 2-disegno a blocchi di parametri (v,k,r

) una struttura formata da:

- un insieme A di cardinalità v;

- alcuni sottoinsiemi non vuoti di A (detti blocchi del disegno), tutti della stessa cardinalità k e tali che ogni coppia di elementi di A appartenga esattamente ad r

blocchi

L’esempio precedente è un esempio di 2-disegno di parametri (8,4,3). Esaminando i blocchi in questo esempio, si può notare che ogni elemento di A appartiene a 7 blocchi, quindi si tratta nello stesso tempo di un disegno di parametri (8,4,7). Ciò non è casuale:

Teorema. Un 2-disegno di parametri (v,k,r

) è anche un disegno di parametri (v,k,r) dove il parametro r= ha il valore r=r

(v-1)/(k-1).

Dimostrazione: Supponiamo dato un 2-disegno di parametri (v,k,r

): la tesi è che esso è anche un disegno di parametri (v,k,r=r

(v-1)/(k-1)), quindi per dimostrare la tesi dobbiamo verificare che ogni elemento appare in un numero costante r di blocchi, dove r=r

(v-1)/(k-1).

Sia A= {a

, a

, …., a

} l’insieme di cardinalità v, e fissiamo per esempio l’elemento a

(per gli altri elementi si ragiona in modo analogo).

Sia r il numero dei blocchi del disegno che contengono a

come elemento: la tesi, come detto, è che r=r

(v-1)/(k-1). Siano B

, B

, ……, B

i blocchi del 2-disegno che contengono l’elemento a

.

Costruiamo una matrice booleana con r righe e con (v-1) colonne, in cui alle colonne si fanno corrispondere gli elementi a

,…..a

di A (quindi gli elementi diversi da a

), e alle righe si fanno corrispondere i blocchi B

,B

,…B

(che contengono a

), mentre in ogni casella all’incrocio fra riga i e colonna j si pone il valore 1 se l’elemento a

appartiene al blocco B

, il valore 0 altrimenti.

Il fatto che ogni blocco B

abbia in origine cardinalità k dice che ogni riga della matrice contiene esattamente (k-1) valori =1 (tenendo conto che già l’elemento a

appartiene al blocco); dunque contando per righe il numero di valori =1 è (k-1)+….+(k-1)=(k-1)r.

Se a

è un generico elemento di A distinto da a

, la colonna corrispondente nella matrice contiene

esattamente r

valori =1 (ognuno di tali valori corrisponde ad un blocco che contiene la coppia a

, a

,

ed il numero di tali blocchi è appunto r

, per definizione di 2-disegno); dunque contando per

colonne il numero di valori =1 è r

+…..+r

=r

(v-1).

Per il principio del contare per righe e per colonne si ha l’eguaglianza:

r

(v-1) = r(k-1)

da cui r = r

(v-1)/(k-1) (cioè la tesi).

Dal Teorema precedente segue che se esiste un 2-disegno di parametri (v,k,r

), dovendo essere r = r

(v-1)/(k-1) intero, è verificata la condizione:

(*) (k-1) è divisore di r

(v-1)

Ricordando poi le condizioni per l’esistenza di un disegno di parametri (v,k,r) si ottiene (sempre dal Teorema precedente) che, se esiste un 2-disegno di parametri (v,k,r

), sono verificate le 2 condizioni:

(**) k è divisore del prodotto r

v(v-1)/(k-1) (***) x = r

v(v-1)/k(k-1)  _



 



 k v

ed inoltre x = r

v(v-1)/k(k-1) rappresenta il numero dei blocchi del disegno.

Nell’esempio precedente di un 2-disegno di parametri (8,4,3), si può notare che il numero di blocchi (cioè dei tornei) è 14 proprio perché in questo caso 14 = r

v(v-1)/k(k-1) come si calcola facilmente.

Nel caso dei 2-disegni (al contrario di quanto avviene per i disegni) si è visto con degli esempi che il verificarsi delle condizioni (*), (**), (***) non garantisce l’esistenza di un 2-disegno di parametri (v,k,r

), (e non sono state ancora trovate condizioni necessarie e sufficienti per tale esistenza).

Piani proiettivi.

Diamo qualche cenno alla teoria della cosiddetta geometria proiettiva nel piano.

Nel piano euclideo “ordinario” vi sono le rette e i punti, e sono soddisfatte (fra le altre) le seguenti proprietà:

1) per due punti distinti passa una sola retta

2) due rette distinte si intersecano in un solo punto se non sono parallele.

All’eccezione rappresentata dalle rette parallele si può ovviare creando una nuova struttura di piano più “ampio” di quello ordinario (detto piano proiettivo): si aggiungono in pratica ai punti

“ordinari” dei punti “particolari” (detti punti all’infinito: ne esiste uno per ogni fascio di rette parallele) e oltre alle rette “ordinarie” si considera una retta “particolare” (detta retta all’infinito) i cui punti sono i punti all’infinito.

In tale piano proiettivo sono allora verificate le seguenti proprietà:

1) per due punti distinti passa una sola retta

2) due rette distinte si intersecano in un solo punto (senza eccezioni).

Torniamo alla teoria dei 2-disegni.

Studieremo un particolare tipo di 2-disegni di parametri (v,k,r

), precisamente quelli in cui:

1) r

=1 (quindi ogni coppia di elementi è contenuta in 1 solo blocco) 2) l’intersezione di 2 qualunque blocchi distinti contiene un solo elemento.

Poiché in un tale 2-disegno i blocchi si comportano come le rette del piano proiettivo, e gli elementi come i punti del piano proiettivo (per 2 elementi “passa” un solo blocco e due blocchi distinti si intersecano in un solo elemento) si è deciso di chiamare piano proiettivo di parametri (v,k,1) un qualunque 2-disegno che soddisfi le proprietà 1),2) suddette, ed inoltre di chiamare rette i blocchi di tale 2-disegno, e punti gli elementi.

Dimostriamo una importante proprietà dei piani proiettivi:

Esempio. Costruiamo un piano proiettivo di parametri (7,3,1) (quindi vi sono 7 punti; ogni retta

contiene 3 punti; per 2 punti passa una sola retta; due rette distinte si incontrano in un solo punto).

Un modo per costruirlo potrebbe essere il seguente: numeriamo i 7 punti con 0,1,2,3,4,5,6 e costruiamo i seguenti blocchi (rette)

{1,2,4}, {0,4,5}, {1,5,6}, {2,3,5}, {3,4,6}, {0,1,3}, {0,2,6}.

Una rappresentazione grafica di tale piano proiettivo potrebbe essere la seguente:

In tale rappresentazione i 7 punti sono i 3 vertici del triangolo, i 3 punti medi dei lati e il centro;

invece le rette sono i 3 lati del triangolo, le 3 mediane e la circonferenza inscritta.

Anche graficamente si può verificare facilmente che per 2 punti passa una sola retta e che due rette distinte si incontrano in un solo punto.

Possiamo anche dare una rappresentazione grafica di un piano proiettivo di parametri (13,4,1), in cui si devono individuare opportunamente le “rette”:

Per lo stesso piano proiettivo esiste una rappresentazione più “simmetrica”:

(in questa però gli 8 punti sulla circonferenza esterna devono essere identificati a coppie

“fondendo” insieme i punti simmetrici rispetto al centro)

Ecco una rappresentazione grafica per un piano proiettivo di parametri (21,5,1) (anche in questa in

cui si devono individuare opportunamente le “rette”):