Matematica Discreta
Lezione del giorno 12 aprile 2012
Nella lezione precedente abbiamo trattato il problema dei test industriali di qualità: un’industria produce un numero v di differenti varietà di uno stesso prodotto (v è un numero naturale) e vuole sottoporre tali varietà ad un test di qualità utilizzando alcuni soggetti (testers) che effettueranno il test.
Le logiche richieste per un test equilibrato sono:
- ogni tester effettua il test sullo stesso numero k di varietà del prodotto fra le v disponibili (con k numero naturale uguale per tutti i testers);
- ognuna delle v varietà del prodotto sia sottoposta al test dallo stesso numero r di testers (con r numero naturale uguale per tutte le varietà)
Abbiamo anche esaminato il seguente:
Esempio: sia v=6, k=3, r=2 (in totale 6 varietà del prodotto, ogni tester sottopone 3 varietà al test ed ogni varietà viene sottoposta al test da 2 testers). Con questi dati abbiamo visto che è possibile effettuare il test impiegando 4 testers per esempio secondo lo schema seguente:
1° tester: {a,b,c}, 2° tester: {b,c,d}, 3° tester: {d,e,f}, 4° tester: {e,f,a}
Se vogliamo formalizzare l’esempio precedente nel linguaggio della teoria degli insiemi, possiamo dire che si è partiti da un insieme con v=6 elementi (nel nostro caso A=a,b,c,d,e,f) e si sono costruiti dei sottoinsiemi di A (nel nostro caso {a,b,c},{b,c,d},{d,e,f},{e,f,a}) ognuno dei quali ha la stessa cardinalità k=3, e tali che ogni elemento dell’insieme di partenza è contenuto esattamente in r=2 di tali sottoinsiemi.
Da ciò nasce in modo naturale la definizione del concetto 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 precedente, dove A=a,b,c,d,e,f e dove i sottoinsiemi di A sono {a,b,c}, {b,c,d},{d,e,f},{e,f,a}, è un esempio di disegno di parametri (v=6,k=3,r=2).
Problemi:
1) Fissati a piacere i 3 parametri v,k,r, esiste sempre un disegno di parametri v,k,r ?
2) Se la risposta alla domanda 1) è negativa, quali condizioni si devono imporre sui parametri (v,k,r) affinché il disegno si possa costruire ?
3) Se per una certa scelta dei parametri (v,k,r) il disegno si può costruire, in quale modo il numero x dei blocchi del disegno è legato ai 3 parametri v,k,r ?
Per rispondere a tali quesiti utilizzeremo la teoria delle matrici booleane.
Sia dato l’insieme A=a1,a2,…..av di cardinalità v e supponiamo che si possa costruire il disegno di parametri (v,k,r) e che in tale disegno sia x il numero dei 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 v k
, quindi una condizione che certamente è verificata (se il disegno si può costruire) è la seguente:
il 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 la somma dei valori della matrice contata 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 la somma dei valori della matrice contata 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 x=(vr)/k, quindi non può essere fissato a priori, ed inoltre (dovendo essere x un numero naturale) ci fornisce una seconda condizione che certamente è verificata se il disegno di parametri (v,k,r) esiste:
il parametro k è divisore del prodotto vr degli altri 2 parametri
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 v
k
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> v
k
= 5 3
=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 assolutamente arbitrario) x sottoinsiemi distinti di A, tutti di cardinalità k: siano essi B1,B2,…Bx (tale
scelta è appunto possibile perché abbiamo per la (**) un numero sufficiente v k
di sottoinsiemi di A di cardinalità k tra cui scegliere x sottoinsiemi arbitrari).
Per costruire il disegno di parametri (v,k,r) useremo il cosiddetto metodo degli “aggiustamenti successivi”, modificando progressivamente 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 la somma dei valori della matrice contata per colonne è kx.
D’altronde, se chiamiamo ri il numero di 1 nella generica riga i (esso rappresenta il numero di sottoinsiemi B1,B2,…Bx a cui appartiene l’elemento ai), la somma dei valori della matrice contata per righe coincide con 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 esattamente r valori =1, allora il disegno di parametri (v,k,r) è già costruito (perché in questo caso ogni elemento di A appartiene esattamente ad r dei sottoinsiemi B1,B2,…Bx e dunque i blocchi del disegno cercato sono proprio i sottoinsiemi B1,B2,…Bx scelti arbitrariamente).
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 .
Dunque 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 (in questa situazione il sottoinsieme 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 sottoinsieme 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 il numero di 1 in una riga che ne ha in “difetto”: iterando il procedimento, dopo un numero finito di “aggiustamenti” successivi otterremo una matrice in cui ogni riga ha esattamente r valori =1, e i sottoinsiemi B1,B2,…Bx (modificati rispetto a quelli scelti arbirtrariamente 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 arbitrario 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 booleana corrispondente è:
1 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 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 (esattamente 2), la riga 2 ne contiene in eccesso (esattamente 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 una matrice tale che in ogni riga vi è 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 arbitrari della scelta iniziale.
