Prova scritta di Matematica Discreta (11 giugno 2012)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
Esercizio 1. Sia A l’insieme delle funzioni f: {a,b,c,d,m,o}{1,2,3,4,5,6,7,8,9} e sia B l’insieme delle funzioni di A che soddisfano la proprietà che non tutte le vocali hanno corrispondente pari e non tutte le consonanti hanno corrispondente dispari.
Calcolare la cardinalità di B.
(5 p.)
Esercizio 2. Sia A l’insieme dei numeri naturali di 8 cifre (in base 10), con cifre scelte fra 1,2,8. Calcolare il numero degli xA tali che moltiplicando fra loro tutte le cifre di x si ottiene come risultato 8.
(5 p.)
Esercizio 3. Sia A l’insieme dei numeri naturali di 6 cifre (in base 10), con cifre scelte fra 1,2,3,4,5,6,7 e nei quali non vi sono più di 4 cifre =7. Si consideri il grafo semplice non orientato in cui i vertici sono gli elementi di A, e in cui due vertici distinti x,y sono adiacenti se sommando il numero di cifre =7 di x e il numero di cifre =7 di y si ottiene come risultato 4 .
Quante componenti connesse ha il grafo e quanti vertici ha ogni componente? (3 p.) Qual è il numero cromatico del grafo ? (3 p.)
Verificare se in ogni componente (considerata come grafo a sé stante) esiste un cammino Euleriano (specificando, in caso di esistenza, se ciclico o non ciclico) (3 p.) Esercizio 4. Sia B un insieme di cardinalità 4 e sia A l’insieme delle matrici 5x5 nelle cui caselle vi sono funzioni che hanno l’insieme B sia come dominio che come codominio. Calcolare il numero delle matrici di A in cui almeno una delle 2 diagonali ha tutte le caselle contenenti funzioni biunivoche (5 p.)
Esercizio 5. Si vogliono costruire parole di lunghezza 9 sull’alfabeto {a,b,c,d,e,f,o}, in cui ogni lettera è colorata con un colore scelto fra giallo, rosso e verde. Se per distinguere 2 parole si tiene conto anche del colore delle lettere:
a) quante parole diverse in tutto si possono costruire ? (2 p.)
b) quante parole diverse si possono costruire se si impone la condizione che esattamente 4 delle lettere della parola sono vocali ? (4 p.)