Prova scritta di Matematica Discreta (4 settembre 2012)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
Esercizio 1. Sia A l’insieme {1,2,3,4,5,6,7} e sia B l’insieme dei numeri naturali di 8 cifre (in base 10) con cifre scelte in A. Calcolare il numero delle funzioni f con dominio A e codominio B tali che per ogni numero dispari xA il numero f(x) ha la seconda cifra uguale ad x.
(6 p.)
Esercizio 2. Sia A l’insieme dei numeri naturali di 6 cifre (in base 10), con cifre scelte fra 1,2,3,4,6. Calcolare il numero degli xA tali che moltiplicando fra loro le prime 4 cifre si ottiene come risultato 12.
(5 p.)
Esercizio 3. Sia A l’insieme delle parole di lunghezza 5 sull’alfabeto {0,1,2,3}, e si consideri il grafo semplice non orientato in cui i vertici sono gli elementi di A, e due vertici distinti x,y sono adiacenti se il prodotto della prima cifra di x e della prima cifra di y è <4.
Quante componenti connesse ha il grafo e quanti vertici ha ogni componente? (2 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à 14 e sia A un suo sottoinsieme di cardinalità 7. Verificare se sono in maggior numero:
i sottoinsiemi di B che contengono il sottoinsieme A e la cui cardinalità è pari oppure:
i sottoinsiemi di cardinalità dispari dell’insieme A (5 p.)
Esercizio 5. Sia A l’insieme delle matrici 3x3 che in ogni casella contengono una coppia in cui il primo elemento è una lettera scelta fra a,b,c,d,e,f, mentre il secondo elemento è un numero scelto fra 1,2,3,4,5,6,7,8.
a) Quante sono le matrici di A ? (2 p.)
b) Quante sono le matrici di A in cui almeno una delle 2 diagonali contiene solo coppie il cui secondo elemento è >5 ? (4 p.)
