Prova in itinere di Matematica Discreta (20 febbraio 2012)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
Esercizio 1. Sia A l’insieme delle matrici 3x4 a valori in {1,2,3,4,5,6,7,8} e sia B l’insieme delle matrici di A che hanno gli elementi della prima riga non tutti pari, e gli elementi della prima colonna non tutti >2. Calcolare la cardinalità di B.
(6 p.)
Esercizio 2. Calcolare il numero delle matrici 3x7 ad elementi in {0,1,2} in cui la somma degli elementi della prima riga è 4.
(6 p.)
Esercizio 3. Si consideri il grafo semplice non orientato in cui i vertici sono i numeri naturali di 5 cifre (in base 10) con cifre scelte fra {1,3,7,9} e con le ultime 2 cifre (quella delle unità e delle decine) diverse fra loro, e in cui due vertici distinti x,y sono adiacenti se il prodotto xy ha come cifra delle unità la cifra 9.
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. Siano A l’insieme delle funzioni f: {1,2,3}{1,3,5,7,9} e B l’insieme delle matrici 3x4 ad elementi in A. Calcolare il numero delle matrici di B in cui almeno 3 caselle consecutive della prima riga contengono funzioni iniettive. (5 p.) Esercizio 5. In un’urna vi sono 6 palline, numerate da 1 a 6 (ogni pallina è numerata con un numero diverso): per 15 volte si estrae una pallina (rimettendola poi nell’urna), registrando il numero uscito nell’estrazione e ottenendo alla fine una successione di 15 numeri. Quante possibili successioni di numeri si possono ottenere se esattamente in 6 delle 15 estrazioni è uscito un numero pari ? (4 p.)