Matematica Discreta Lezione del giorno 25 marzo 2010 Teoria dei 2-disegni.

(1)

Matematica Discreta

Lezione del giorno 25 marzo 2010 Teoria dei 2-disegni.

Supponiamo che, date v squadre sportive diverse, si debbano organizzare dei tornei a ognuno dei quali partecipano solo alcune di tali squadre. Per uno svolgimento equilibrato dei tornei (in vista per esempio di una classifica finale) è ovviamente opportuno richiedere che:

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

- ogni coppia di squadre si incontri in uno stesso numero r

1

di tornei, con r

1

uguale per tutte le coppie

Esempio: sia v=8, k=4, r

1

=3 (in totale 8 squadre: si pretende che ad ogni torneo partecipino 4 squadre, ed ogni coppia di squadre si incontri esattamente 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}

Notiamo che ogni coppia di squadre si incontra effettivamente in 3 tornei: per esempio la coppia (1,2) nel 1°, 7° e 9° torneo, la coppia (1,3) nel 3°,7° e 11° torneo etc.. (si può effettuare la verifica per tutte le altre possibili coppie di squadre).

Anche in questo caso si può formalizzare il problema pervenendo alla seguente definizione.

Dati i numeri naturali v,k,r

1

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

1

) una struttura formata da:

- un insieme A di cardinalità v;

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

1

blocchi

L’esempio precedente è un esempio di 2-disegno di parametri (8,4,3).

Esaminando i blocchi in questo esempio, notiamo che ogni elemento di A appartiene esattamente a 7 blocchi (per esempio l’elemento 1 al 1°,3°,5°,7°,9°,11°,13° blocco etc…), quindi il 2-disegno di parametri (8,4,3) è nello stesso tempo un disegno di parametri (8,4,7). Ciò non è casuale:

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

1

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

1

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

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

1

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

1

(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

1

(v-1)/(k-1) (valore uguale per tutti gli elementi).

Sia A= {a

1

, a

2

, …., a

v

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

1

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

Sia r il numero dei blocchi del disegno che contengono a

1

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

1

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

1

, B

2

, ……, B

r

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

1

.

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

corrispondere ordinatamente gli elementi a

2

,…..a

v

di A (quindi gli elementi diversi da a

1

), e alle

colonne si fanno corrispondere ordinatamente i blocchi B

1

,B

2

,…B

r

(che contengono a

1

), mentre in

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

i

appartiene al blocco

B

j

, e il valore 0 in caso contrario.

(2)

Il fatto che ogni blocco B

j

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

1

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

Se a

i

è un generico elemento di A distinto da a

1

, la riga corrispondente nella matrice contiene esattamente r

1

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

1

, a

j

, ed il numero di tali blocchi è appunto r

1

, per definizione di 2-disegno); dunque, contando per righe, il numero di valori =1 è r

1

+…..+r

1

=r

1

(v-1).

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

r

1

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

da cui r = r

1

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

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

1

), dovendo essere r = r

1

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

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

1

(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

1

), sono verificate le 2 condizioni:

() k è divisore del prodotto r**

1

v(v-1)/(k-1) (perché k è divisore del prodotto vr) (*) x = r**

1

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



 



 k

v (perché x=vr/k  _



 



 k v )

ed inoltre x = r

1

v(v-1)/k(k-1) rappresenta il numero dei blocchi del 2-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

1

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

Dunque se fissiamo 3 numeri naturali (v,k,r

1

) e almeno una delle condizioni (), (), () non è verificata, non è possibile costruire il un 2-disegno di parametri (v,k,r

1

).

**Purtroppo (al contrario di quanto avviene per i disegni) le condizioni (), (), () non sono necessarie e sufficienti per l’esistenza di un 2-disegno di parametri (v,k,r**

1

) : è possibile costruire terne di numeri naturali (v,k,r

1

) che soddisfano le 3 condizioni, ma tali che non esiste un 2-disegno di parametri (v,k,r

1