Prova scritta di Matematica Discreta (25 giugno 2012)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
Esercizio 1. Calcolare il numero di parole di lunghezza 10 sull’alfabeto A={a,b,c,d,e,m,o} nelle quali, fra le lettere che compongono la parola, il numero di vocali è uguale al numero di consonanti.
(6 p.)
Esercizio 2. Calcolare il numero di matrici 5x5 ad elementi nell’insieme {1,2,3,4,5}
nelle quali vi sono almeno 3 righe consecutive le cui caselle contengono solo numeri dispari.
(5 p.)
Esercizio 3. Sia A l’insieme delle matrici booleane 3x4 e 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 la somma dei valori della prima riga di x e dei valori della prima riga di y è uguale a 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 A l’insieme delle matrici 3x4 ad elementi nell’insieme A={1,2,3,4,5,6,7,8,9,10}. Calcolare il numero di matrici in A in cui l’ultima riga non contiene solo numeri >5 e l’ultima colonna non contiene solo numeri <8 (6 p.)
Esercizio 5. Si consideri un mazzo di carte in cui ogni carta è individuata da un valore numerico intero compreso fra 1 e 10 (inclusi) ed anche da un seme scelto fra picche, fiori, cuori, quadri. Si suppone di estrarre 10 carte dal mazzo (ogni volta inserendo di nuovo nel mazzo la carta estratta) e le si dispone in una successione ordinata sul tavolo: quante possibili successioni ordinate si possono ottenere se nelle prime 4 estrazioni le carte hanno tutte seme diverso da picche e nelle ultime 4 estrazioni le carte hanno tutte valore numerico pari ? (4 p.)
