Prova scritta di Matematica Discreta - Soluzioni (25 giugno 2012)

Prova scritta di Matematica Discreta - Soluzioni (25 giugno 2012)

Esercizio 1. Le parole cercate sono quelle che contengono esattamente 5 consonanti e 5 vocali e il loro numero si può calcolare utilizzando il principio delle scelte multiple: si devono scegliere le 5 posizioni delle consonanti (con (10 5) possibili scelte) e poi inserire una consonante in ognuna di queste 5 posizioni (con 4

scelte possibili); infine in ognuna delle 5 posizioni restanti (scelta obbligata) si deve inserire una vocale (con 3

scelte possibili). La risposta è il prodotto (10 5)4

3

. Esercizio 2. Si può applicare il principio di inclusione-esclusione in forma positiva, costruendo l’insieme X delle matrici in cui la prima, seconda e terza riga ha tutte le caselle contenenti numeri dispari, l’insieme Y delle matrici in cui la seconda, terza e quarta riga ha tutte le caselle contenenti numeri dispari, l’insieme Z delle matrici in cui la terza, quarta e quinta riga ha tutte le caselle contenenti numeri dispari e calcolando:

XYZ=X+Y+Z-{XY+XZ+YZ}+XYZ

Con il principio delle scelte multiple si ottiene:

X=Y=Z=3

5

, XY=YZ=3

5

, XZ=XYZ=3

Esercizio 3. I vertici con 0 valori =1 nella prima riga (in numero di 2

) sono adiacenti a quelli con 4 valori =1 nella prima riga (in numero di 2

); i vertici con 1 valore =1 nella prima riga (in numero di (4 1)2

=42

) sono adiacenti a quelli con 3 valori =1 nella prima riga (in numero di (4 3)2

=42

);

infine i vertici con 2 valori =1 nella prima riga (in numero di (4 2)2

=62

) sono tutti adiacenti fra loro. Vi sono quindi 3 componenti connesse: la prima contenente i vertici con 0 o 4 valori =1 nella prima riga (con 2

+2

vertici), la seconda contenente i vertici con 1 o 3 valori =1 nella prima riga (con 42

+42

vertici), la terza contenente i vertici con 2 valori =1 nella prima riga (con 62

). Nella prima componente il numero cromatico è 2 (un colore per i vertici con 0 valori=1 nella prima riga e un altro per i vertici con 4 valori =1 nella prima riga); analogamente nella seconda componente il numero cromatico è 2; nella terza componente il numero cromatico è 62

(perché ogni vertice deve essere colorato con un colore diverso): il numero cromatico del grafo è dunque 62

. Nella prima componente vertici con 0 valori =1 nella prima riga hanno grado 2

(pari) e i vertici con 4 valori =1 nella prima riga hanno grado 2

(pari); nella seconda componente vertici con 1 valore =1 nella prima riga hanno grado 42

(pari) e i vertici con 3 valori =1 nella prima riga hanno grado 42

(pari); nella terza componente ogni vertice ha grado 62

-1 (dispari). Dunque solo nelle prime 2 componenti esiste un cammino Euleriano (ciclico).

Esercizio 4. Si può applicare il principio di inclusione-esclusione in forma negativa, costruendo l’insieme X delle matrici di A in cui l’ultima riga contiene solo numeri >5, l’insieme Y in cui l’ultima colonna contiene solo numeri <8, e calcolando:

A-XY=A-X-Y+XY

Con il principio delle scelte multiple si ottiene A=10

, X=5

10

, Y=7

10

,

XY=5

7

210

.

Esercizio 5. Si può applicare il principio delle scelte multiple: le possibili scelte per le prime 4 carte

sono in numero di (103)

=30

(per ogni carta 10 scelte per il valore numerico e 3 scelte per il

seme); per la quinta e sesta carta sono in numero di (104)

=40

(per ogni carta 10 scelte per il valore

numerico e 4 scelte per il seme; per le ultime 4 carte sono in numero di (54)

=20

(per ogni carta 5

scelte per il valore numerico e 4 scelte per il seme). La risposta è il prodotto 30

40

20

.