Prova scritta di Matematica Discreta (17 settembre 2012)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
Esercizio 1. Sia A l’insieme delle parole sull’alfabeto binario {0,1} di lunghezza compresa fra 3 e 6 (inclusi) e sia B l’insieme delle matrici 3x4 ad elementi in A.
Calcolare quante sono le matrici in B in cui le ultime 3 caselle della prima riga non contengono solo parole di lunghezza pari e nello stesso tempo le prime 2 caselle della quarta colonna non contengono solo parole di lunghezza <6. (6 p.)
Esercizio 2. Siano A, B gli insiemi dell’Esercizio 1. Calcolare quante sono le matrici in B in cui l’ultima colonna ha almeno 2 caselle che contengono entrambe parole di lunghezza <5. (6 p.)
Esercizio 3. Sia A l’insieme delle parole di lunghezza 4 sull’alfabeto {a,b,c,d,e,f} tra le cui lettere vi è almeno una vocale e non vi sono più di 3 vocali. 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 la somma del numero lettere di x che sono vocali e del numero di lettere di y che sono vocali è 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. Una insegna rettangolare è suddivisa in 10 sezioni:
In ogni sezione vengono inseriti 2 elementi grafici: una lettera scelta fra A,B,C,D,E,I,O ed un numero scelto fra 2,3,4,5,6,7,8; inoltre ogni sezione viene poi colorata con un colore scelto fra 5 giallo, verde, rosso, nero, viola. Calcolare quante diverse insegne si possono ottenere se nelle prime 6 sezioni le lettere sono tutte consonanti e nelle ultime 7 sezioni i numeri sono tutti dispari. (5 p.)
Esercizio 5. Si consideri un dado a 6 facce in cui ogni faccia contiene un numero diverso compreso fra 1,2,3,4,5,6. Si effettuano 12 tiri consecutivi del dado e ogni volta si segna il numero uscito nella faccia superiore, ottenendo alla fine un numero naturale di 12 cifre. Calcolare quanti numeri diversi possibili si possono ottenere se nei tiri di posto pari (secondo, quarto, sesto etc...) è uscito esattamente per 4 volte un numero pari e nei tiri di posto dispari (primo, terzo, quinto etc...) è uscito sempre il numero 5. (4 p.)
