Prova in itinere di Matematica Discreta - Soluzioni (20 febbraio 2012)
Esercizio 1. Si può applicare il principio di inclusione-esclusione in forma negativa, costruendo l’insieme X delle matrici di A nella cui prima riga tutti gli elementi sono pari, l’insieme Y delle matrici di A nella cui prima colonna tutti gli elementi sono >2, e calcolando:
B=A-XY=A-X-Y+XY
Con il principio delle scelte multiple si ottiene A=812, X=4488, Y=6389,
XY=4362863.
Esercizio 2. Le matrici in questione sono di 3 tipi: quelle che hanno 4 valori = 1 e 3 valori
=0 nella prima riga (in numero di 314), quelle che hanno 1 valore =2, 2 valori =1 e 4 valori =0 nella prima riga (in numero di 7 314) e quelle che hanno 2 valori =2 e 5 valori =0 nella prima riga (in numero di 314). La risposta (per il principio della somma) è la somma di tali numeri (non essendovi intersezione fra un tipo e l’altro.
Esercizio 3. I vertici con cifra delle unità 3 (in numero di 343) sono adiacenti fra loro e lo stesso vale per quelli con cifra delle unità 7 (in numero di 343); i vertici con cifra delle unità 1 (in numero di 343) sono adiacenti solo a quelli con cifra delle unità 9 (in numero di 343) . Vi sono quindi 3 componenti connesse: la prima e la seconda contenente rispettivamente i vertici con cifra delle unità 3 e 7 (ognuna con 343 vertici) e la terza contenente i vertici con cifra delle unità 1 o 9 (con 343+343 vertici). Nella terza componente il numero cromatico è 2 (un colore per i vertici con cifra delle unità 1 e un altro per i vertici con cifra delle unità 9), mentre nella prima e seconda componente il numero cromatico è 343 (ogni vertice necessita di un colore diverso): il numero cromatico del grafo è dunque 343. Nella prima e seconda componente ogni vertice ha grado 343-1 (dispari), mentre nella terza ogni vertice ha grado 343 (pari), dunque solo in quest’ultima esiste un cammino Euleriano (ciclico).
Esercizio 4. Si può applicare il principio di inclusione-esclusione in forma positiva, costruendo l’insieme X delle matrici di B nella cui prima riga le prime 3 caselle contengono funzioni iniettive, l’insieme Y delle matrici di A nella cui prima riga le ultime 3 caselle contengono funzioni iniettive, e calcolando:
XY=X+Y-XY
Tenendo conto che le funzioni di A sono in numero di 53, e quelle iniettive in numero di 543=60, con il principio delle scelte multiple si ottiene:
X=Y=603(53)9, XY=604(53)8.
Esercizio 5. Si può applicare il principio delle scelte multiple: le possibili scelte per le 6 posizioni dei numeri pari sono in numero di
6
15 ; fissata questa scelta, le possibili scelte per
inserire i 3 numeri pari 2,4,6 in queste 6 posizioni sono in numero di 36; fissate queste scelte, le possibili scelte per inserire i 3 numeri dispari 1,3,5 nelle 9 posizioni restanti sono 39. La risposta è il prodotto di questi numeri
6 15 315.
