Compito di Matematica Discreta I (3 settembre 2007) Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento Esercizio 1.

Compito di Matematica Discreta I (3 settembre 2007)

Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento

Esercizio 1. Si consideri il grafo semplice non orientato, in cui i vertici sono tutte le matrici booleane con 3 righe e k colonne dove 2<k<6, e in cui due vertici distinti x,y sono adiacenti se la somma del numero di colonne di x e del numero di colonne di y è uguale a 8.

a) Calcolare il numero di componenti connesse del grafo, e di ciascuna il numero dei vertici (3 p.)

b) Calcolare il numero cromatico del grafo (3 p.)

c) In ognuna delle componenti connesse, considerata come grafo a sé stante, verificare se esiste un cammino Euleriano (3 p.)

Esercizio 2.

Dimostrare che per ogni naturale n, il numero totale di parole sull’alfabeto {a,b} di lunghezza compresa fra 3 e 3+n (inclusi) è 2

-8 (5 p.)

Esercizio 3. Calcolare il numero delle funzioni f: {a,b,c,d,e,m,o} → {1,2,3,4,5,6,7,8}

tali che le immagini di almeno 2 vocali sono numeri <6 (5 p.)

Esercizio 4. Calcolare il numero degli interi positivi formati da 12 cifre non nulle (in base 10), in cui esattamente 3 delle prime 7 cifre sono pari (5 p.)

Esercizio 5. In un laboratorio chimico vi sono 6 bidoni da 10 litri contenenti ognuno una sostanza diversa. Si effettua la seguente operazione: per 10 volte si sceglie a sorte uno dei bidoni e si preleva da quel bidone un litro di sostanza, versandola in un misurino da 10 litri, ottenendo alla fine nel misurino una miscela. Quanti diversi miscele si possono ottenere, se ogni miscela non dipende dall’ordine in cui vengono mescolate le sostanze che la compongono ?

Se i 6 bidoni contengono ognuno 9 litri di sostanza, invece di 10, il numero di

possibili miscele che si possono ottenere resta inalterato ? (in caso di risposta

affermativa spiegare perché; in caso di risposta negativa calcolare il numero di

possibili miscele) (6 p.)