Prova scritta di Matematica Discreta - Soluzioni (11 giugno 2012)
Esercizio 1. Si può applicare il principio di inclusione-esclusione in forma negativa, costruendo l’insieme X delle funzioni di A tali che tutte le vocali hanno corrispondente pari, l’insieme Y delle funzioni di A tali che tutte consonanti hanno corrispondente dispari, e calcolando:
B=A-XY=A-X-Y+XY
Con il principio delle scelte multiple si ottiene A=96, X=4294, Y=5492, XY=4254. Esercizio 2. Gli elementi x cercati sono di 2 tipi: quelli che hanno una cifra =8 e tutte le altre =1 (in numero di 8 perché 8 sono le possibilità di scegliere la posizione della cifra 8) e quelli che hanno 3 cifre =2 e tutte le altre =1 (in numero di (8 3) perché (8 3) sono le possibilità di scegliere le 3 posizioni della cifra 2). La risposta (per il principio della somma) è la somma 8+(8 3) (non essendovi intersezione fra un tipo e l’altro).
Esercizio 3. I vertici con 0 cifre =7 (in numero di 66) sono adiacenti a quelli con 4 cifre =7 (in numero di (6 4)62); i vertici con 1 cifra =7 (in numero di 665) sono adiacenti a quelli con 3 cifre =7 (in numero di (6 3)63); i vertici con 2 cifre =7 (in numero di (6 2)64) sono tutti adiacenti fra loro. Vi sono quindi 3 componenti connesse: la prima contenente i vertici con 0 o 4 cifre =7, la seconda contenente i vertici con 1 o 3 cifre =7, la terza contenente i vertici con 2 cifre =7. Nella prima componente il numero cromatico è 2 (un colore per i vertici 0 cifre =7 e un altro per i vertici con 4 cifre =7); analogamente nella seconda componente il numero cromatico è 2; nella terza componente il numero cromatico è (6 2)64 (ogni vertice necessita di un colore diverso): il numero cromatico del grafo è (6 2)64. Nella prima componente i vertici con 0 cifre =7 hanno grado (6 4)62 (pari) e i vertici con 4 cifre
=7 hanno grado 66 (pari); nella seconda componente i vertici con 1 cifra =7 hanno ha grado (6 3)63 (pari) e i vertici con 3 cifre =7 hanno grado 665 (pari); mentre nella terza ogni vertice ha grado (6 2)64-1 (dispari), Solo nelle prime 2 componenti 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 A in cui la prima delle 2 diagonali ha tutte le caselle contenenti funzioni biunivoche, e l’insieme Y delle matrici di A in cui la seconda delle 2 diagonali ha tutte le caselle contenenti funzioni biunivoche, e calcolando:
XY=A-{X+Y-XY}
Tenendo conto che le funzioni di A sono in numero di 44, e quelle biunivoche in numero di 4!, con il principio delle scelte multiple si ottiene:
X=Y=(4!)5(44)20, XY=(4!)9(44)16.
Esercizio 5. Si può applicare il principio delle scelte multiple:
a) Per ognuna delle 9 posizioni si deve scegliere la lettera (con 7 scelte possibili) e il colore (con 3 scelte possibili), dunque si possono costruire (73)9 parole diverse b) Si devono scegliere le 4 posizioni delle vocali (con (9 4) scelte possibili); fissata tale
scelta si devono inserire le vocali in queste 4 posizioni (con 34 scelte possibili);
fissate queste scelte si devono inserire le consonanti nelle rimanenti 5 posizioni (con 45 scelte possibili); infine si devono scegliere i colori per ognuna delle lettere (con 39 scelte possibili). La risposta è il prodotto (9 4)344539.
