Da ciò segue la definizione formale di disegno.

(1)

Matematica Discreta

Lezione del giorno 25 marzo 2009

Abbiamo visto come, formalizzando in modo astratto il problema di costruire un test industriale di qualità “equilibrato”, esso si trasformi nel problema di costruire, dato un insieme A di cardinalità v, alcuni suoi sottoinsiemi di cardinalità k, tali che ogni elemento di A appartenga esattamente ad r di tali sottoinsiemi.

Da ciò segue la definizione formale di disegno.

Fissati i numeri naturali v,k,r (detti parametri) si chiama disegno 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 elemento di A appartenga esattamente ad r blocchi

Esempio: L’esempio della lezione precedente, con A=a,b,c,d,e,f) e i sottoinsiemi di A {a,b,c}, {b,c,d},{d,e,f}, {e,f,a}, è un esempio di disegno di parametri (v=6,k=3,r=2).

Problema: quali condizioni si devono imporre sui parametri (v,k,r) affinché il disegno si possa costruire, e come il numero x dei blocchi è legato ai 3 parametri ?

Sia dato l’insieme A=a

1

,a

2

,…..a

v

 e si supponga che si possa costruire il disegno di parametri (v,k,r) con x blocchi; gli x blocchi B

1

,B

2

,…B

x

saranno dei sottoinsiemi di A tutti di cardinalità k; ma il numero totale di sottoinsiemi di cardinalità k di un insieme di cardinalità v è uguale al coefficiente binomiale _



 



 k

v , quindi una condizione che certamente è verificata (se il disegno si può costruire) è la seguente: numero dei blocchi x  _



 



 k v .

Sempre nell’ipotesi che si possa costruire il disegno di parametri (v,k,r) con x blocchi, costruiamo una matrice booleana con x righe, v colonne, in cui alle colonne si fanno corrispondere gli elementi a

1

,a

2

,…..a

v

di A, e alle righe i blocchi B

1

,B

2

,…B

x

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

j

(corrispondente alla colonna) appartiene al blocco B

i

(corrispondente alla riga), oppure il valore 0 in caso contrario.

Dall’ipotesi che ogni blocco abbia cardinalità k segue che ogni riga contiene esattamente k valori

=1, dunque il numero totale di 1 contato per righe è k+k+….+k = kx . Dall’ipotesi che ogni elemento a

i

appartenga esattamente ad r blocchi segue che ogni colonna contiene r valori =1, dunque il numero totale di 1 contato per colonne è r+r+….+r = rv.

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

rv=kx

ossia x=(vr)/k.

Questa eguaglianza ci dice che il numero x di blocchi di un disegno di parametri (v,k,r) dipende dai 3 parametri, quindi non può essere fissato apriori, ed inoltre (dovendo essere x un numero intero) ci fornisce una seconda condizione che certamente è verificata se il disegno di parametri (v,k,r) esiste:

k è divisore del prodotto vr.

Riassumendo, se si può costruire il disegno di parametri (v,k,r) allora valgono certamente le due condizioni seguenti:

**(*) k è divisore del prodotto vr () x = (vr)/k  _



 





k

v

(2)

ed inoltre il numero x rappresenta il numero dei blocchi del disegno.

Se, fissati i 3 parametri (v,k,r), almeno una delle 2 condizioni non è verificata, si può essere certi che il disegno di parametri (v,k,r) non esiste.

Esempio. Un disegno di parametri (10,7,4) non esiste in quanto 7 non è divisore di 40, dunque non è verificata la condizione (*).

Un disegno di parametri (5,3,9) non esiste in quanto, pur essendo verificata la condizione (*) (perché 3 è divisore di 45), non è verificata la condizione (**), essendo x=vr/k=15> _



 



 k

v = _



 



 3 5 =10.

Ma il risultato più interessante è che, viceversa:

**Teorema. Se le due condizioni (*), () sono verificate dai numeri naturali v,k,r, allora si può costruire un disegno di parametri (v,k,r).

Dimostrazione: Sia A=a

1

,a

2

,…..a

v

 l’insieme di cardinalità v; essendo vera per ipotesi la (*), il numero x=(vr)/k è intero (e sappiamo che x sarà il numero di blocchi del disegno da costruire).

Inoltre, essendo vera la (**), è possibile scegliere (in modo random) x sottoinsiemi distinti di A, ognuno di cardinalità k, e siano essi B

1

,B

2

,…B

x

. Per costruire il disegno di parametri (v,k,r) useremo il cosiddetto metodo degli “aggiustamenti successivi”

Costruiamo una matrice booleana con x righe, v colonne, con la stessa regola della matrice costruita sopra: alle colonne si fanno corrispondere gli elementi a

1

,a

2

,…..a

v

di A, e alle righe i sottoinsiemi B

1

,B

2

,…B

x

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

j

(corrispondente alla colonna) appartiene al sottoinsieme B

i

(corrispondente alla riga), oppure il valore 0 in caso contrario.

Osserviamo di nuovo che in ogni riga vi sono k valori =1 (perché ogni sottoinsieme B

i

contiene k elementi), dunque il numero di 1 contato per righe è kx.

D’altronde, se chiamiamo r

i

il numero di 1 nella generica colonna i (esso rappresenta il numero di sottoinsiemi a cui appartiene l’elemento a

i

), il numero di 1 contato per colonne è la somma r

1

+r

2

+

…..+r

v

.

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

r

1

+r

2

+…..+r

v

=kx .

Se ogni riga della matrice contiene r valori =1, allora il disegno di parametri (v,k,r) è già costruito (i blocchi del disegno sono proprio i sottoinsiemi B

1

,B

2

,…B

x

scelti random).

Dunque supponiamo che qualcuno fra i numeri r

1

, r

2

, ….., r

v

sia  r.

Per tutti questi indici i per cui r

i

r non si può avere sempre r

i

>r: se così fosse sarebbe kx=r

1

+r

2

+…..

+r

v

>vr, contro l’ipotesi x=(vr)/k. Analogamente per gli stessi indici i per cui r

i

r non si può avere sempre r

i

<r .

Esisteranno allora almeno 2 indici distinti i, j tali che r

i

<r<r

j

. Poiché nella riga i il numero di valori

=1 è maggiore di quello nella riga j, vi sarà almeno una riga di indice h in cui nella casella della riga

j vi è il valore 1 mentre nella casella della riga i vi è il valore 0 (dunque il blocco B

h

contiene

l’elemento a

j

ma non l’elemento a

i

). Modifichiamo allora la matrice, scambiando fra loro questi

valori 0 ed 1 nella stessa riga: dal punto di vista insiemistico modifichiamo il blocco B

h

togliendo

l’elemento a

j

e inserendo l’elemento a

i

(in particolare non cambia la cardinalità k del sottoinsieme

B

h

). Questo “aggiustamento” porta ad una situazione in cui abbiamo diminuito il numero di 1 in una

riga che ne ha in “eccesso” (rispetto al valore r) e abbiamo aumentato il numero di 1 in una riga che

ne ha in “difetto”: iterando il procedimento, dopo un numero finito di aggiustamenti otterremo una

matrice in cui ogni riga ha esattamente r valori =1, e i sottoinsiemi B

1

,B

2

,…B

x

(modificati rispetto a

quelli scelti random all’inizio) saranno i blocchi del disegno cercato.

(3)

**Esempio. Costruiamo un disegno di parametri (5,3,3): sono verificate le condizioni (*), () ed il numero di blocchi è x=15/3=5. Scegliamo in modo random 5 sottoinsiemi di A={a

1

,a

2

,a

3

,a

4,

a

5

} tutti di cardinalità k=5, per esempio:

B

1

={a

1

,a

2

,a

3

}, B

2

={a

2

,a

3

,a

4

}, B

3

={a

3

,a

4

,a

5

}, B

4

={a

1

,a

2

,a

4

}, B

5

={a

2

,a

4

,a

5

} La matrice corrispondente è:

 





 





1 1 0 1 0

0 1 0 1 1

1 1 1 0 0

0 1 1 1 0

0 0 1 1 1

L’obiettivo è quello di trasformare i blocchi in modo che ogni colonna contenga un numero di valori 1 che coincida con r=3..

La colonna 1 ne contiene in difetto (il numero di valori 1 è 2), la riga 2 ne contiene in eccesso (il numero di valori 1 è 4): poiché nella riga 2 vi è un 1 nella colonna 2 ed uno 0 nella riga 1, li scambiamo fra loro ottenendo:

 





 





1 1 0 1 0

0 1 0 1 1

1 1 1 0 0

0 1 1 0 1

0 0 1 1 1

Analogamente la colonna 4 contiene valori 1 in eccesso, la colonna 4 contiene valori 1 in difetto:

poiché nella riga 2 vi è un 1 nella colonna 4 ed uno 0 nella colonna 5, li scambiamo fra loro ottenendo:

 





 





1 1 0 1 0

0 1 0 1 1

1 1 1 0 0

1 0 1 0 1

0 0 1 1 1

Abbiamo ottenuto in ogni riga un numero di valori 1 che è esattamente uguale ad r=3, dunque abbiamo costruito un disegno di parametri (5,5,3), con i seguenti blocchi:

B

1

={a

1

,a

2

,a

3

}, B

2

={a

1

,a

3

,a

5

}, B

3

={a

3

,a

4

,a

5

}, B

4

={a

1

,a

2

,a

4

}, B

5

={a

2

,a

4

,a

5

}.

Da ciò segue la definizione formale di disegno.

Matematica Discreta

Lezione del giorno 25 marzo 2009