Matematica Discreta
Lezione del giorno 24 marzo 2010 Teoria dei disegni.
Partendo dai problemi legati ai test industriali di qualità, siamo pervenuti alla seguente 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
Problemi: Fissati ad arbitrio i 3 parametri v,k,r, esiste sempre un disegno di parametri v,k,r ?
Se la risposta è negativa, quali condizioni si devono imporre sui parametri (v,k,r) affinché il disegno si possa costruire ? Se il disegno si può costruire, come il numero x dei blocchi del disegno è legato ai 3 parametri v,k,r ?
Sia dato l’insieme A=a1,a2,…..av e si supponga che si possa costruire il disegno di parametri (v,k,r) con x blocchi; gli x blocchi B1,B2,…Bx 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 v righe, x colonne, in cui alle righe si fanno corrispondere gli elementi a1,a2,…..av di A, e alle colonne i blocchi B1,B2,…Bx , mentre in ogni casella all’incrocio fra riga i e colonna j si pone il valore 1 se l’elemento ai (corrispondente alla riga) appartiene al blocco Bj
(corrispondente alla colonna), oppure il valore 0 in caso contrario.
Dall’ipotesi che ogni blocco abbia cardinalità k segue che ogni colonna contiene esattamente k valori =1, dunque il numero totale di 1 contato per colonne è k+k+….+k = kx . Dall’ipotesi che ogni elemento appartenga esattamente ad r blocchi segue che ogni riga contiene r valori =1, dunque il numero totale di 1 contato per righe è 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 secondo l’equazione precedente, quindi non può essere fissato a priori, 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
ed inoltre il numero x rappresenta il numero dei blocchi del disegno.
Deduciamo da ciò che, fissati i 3 parametri (v,k,r), se 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=a1,a2,…..av l’insieme di cardinalità v su cui dobbiamo costruire il disegno;
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 B1,B2,…Bx (tale scelta è appunto possibile perché abbiamo per la (**) un numero sufficiente
k
v di sottoinsiemi di A di cardinalità k tra cui scegliere i k blocchi random).
Per costruire il disegno di parametri (v,k,r) useremo il cosiddetto metodo degli “aggiustamenti successivi”, modificando a poco a poco i blocchi inizialmente scelti.
Costruiamo una matrice booleana con v righe, x colonne, con la stessa regola della matrice costruita sopra: alle righe si fanno corrispondere gli elementi a1,a2,…..av di A, e alle colonne i sottoinsiemi B1,B2,…Bx , mentre in ogni casella all’incrocio fra riga i e colonna j si pone il valore 1 se l’elemento ai (corrispondente alla riga) appartiene al sottoinsieme Bj (corrispondente alla colonna), oppure il valore 0 in caso contrario.
Osserviamo di nuovo che in ogni colonna vi sono k valori =1 (perché ogni sottoinsieme Bi contiene k elementi), dunque il numero di 1 contato per colonne è kx.
D’altronde, se chiamiamo ri il numero di 1 nella generica riga i (esso rappresenta il numero di sottoinsiemi a cui appartiene l’elemento ai), il numero di 1 contato per righe è la somma r1+r2+…..
+rv.
Per il principio del contare per righe e per colonne si ha:
r1+r2+…..+rv=kx .
Se ogni riga della matrice contiene r valori =1, allora il disegno di parametri (v,k,r) è già costruito (in questo caso ogni elemento di A appartiene esattamente ad r dei sottoinsiemi B1,B2,…Bx e dunque blocchi del disegno cercato sono proprio i sottoinsiemi B1,B2,…Bx scelti random).
Dunque supponiamo che qualcuno fra i numeri r1, r2, ….., rv sia r.
Per tutti gli indici i per cui rir non si può avere sempre ri>r: se così fosse sarebbe kx=r1+r2+…..
+rv>vr, contro l’ipotesi x=(vr)/k. Con ragionamento analogo si deduce che per gli indici i per cui rir non si può avere sempre ri<r .
Esisteranno allora almeno 2 indici distinti i, j tali che ri<r<rj. Poiché nella riga j il numero di valori
=1 è maggiore di quello nella riga i, vi sarà almeno una colonna 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 Bh contiene l’elemento aj ma non l’elemento ai). Modifichiamo allora la matrice, scambiando fra loro questi valori 0 ed 1 nella stessa colonna h: dal punto di vista insiemistico modifichiamo il blocco Bh
togliendo l’elemento aj e inserendo l’elemento ai (in particolare non cambia la cardinalità k del sottoinsieme Bh). 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 di 1 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 B1,B2,…Bx (modificati rispetto a quelli scelti random all’inizio) saranno i blocchi del disegno cercato.
Esempio. Costruiamo un disegno di parametri (5,3,3): il disegno si può costruire perché sono verificate le condizioni (*), (**). In particolare il numero di blocchi del disegno da costruire è x=15/3=5. Scegliamo in modo random 5 sottoinsiemi di A={a1,a2,a3,a4,a5} tutti di cardinalità k=5, per esempio:
B1={a1,a2,a3}, B2={a2,a3,a4}, B3={a3,a4,a5}, B4={a1,a2,a4}, B5={a2,a4,a5} La matrice corrispondente è:
1 0 1 0 0
1 1 1 1 0
0 0 1 1 1
1 1 0 1 1
0 1 0 0 1
L’obiettivo è quello di trasformare i blocchi in modo che ogni riga contenga un numero di valori 1 che coincida con r=3..
La riga 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 colonna 2 vi è un 1 nella riga 2 ed uno 0 nella riga 1, li scambiamo fra loro ottenendo:
1 0 1 0 0
1 1 1 1 0
0 0 1 1 1
1 1 0 0 1
0 1 0 1 1
Analogamente la riga 4 contiene valori 1 in eccesso, la riga 5 contiene valori 1 in difetto: poiché nella colonna 4 vi è un 1 nella riga 4 ed uno 0 nella riga 5, li scambiamo fra loro ottenendo:
1 1 1 0 0
1 0 1 1 0
0 0 1 1 1
1 1 0 0 1
0 1 0 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:
B1={a1,a2,a3}, B2={a1,a3,a4}, B3={a3,a4,a5}, B4={a1,a2,a5}, B5={a2,a4,a5}.
Notiamo che i blocchi B2 e B4 (corrispondenti alle colonne 2 e 4) sono stati modificati rispetto a quelli random della scelta iniziale.
