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

Compito di Matematica Discreta I (28 gennaio 2008)

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 parole sull’alfabeto {1,2,3,4,5} di lunghezza m=1,2,3,4,5 e in cui due vertici distinti x,y sono adiacenti se la somma della lunghezza di x e della lunghezza di y è uguale a 6.

Calcolare il numero delle componenti connesse e il numero dei vertici di ciascuna componente. (3 p.)

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

Verificare se esiste in qualche componente connessa (considerata come grafo a sé stante) un cammino Euleriano ciclico. (3 p.)

Esercizio 2. Calcolare quanti sono i numeri naturali di 4 cifre (in base 10), con cifre scelte fra 1,2,3,4,5,6,7,8, e tali che non vi siano 2 cifre in posizioni consecutive che siano entrambe <6. (6 p.)

Esercizio 3. Dimostrare che per ogni numero naturale n il numero:

n

+(n+1)

+(n+2)

è multiplo di 9 (4 p.)

Esercizio 4. Siano date 20 lampadine colorate, delle quali 7 sono rosse, 5 sono blu, e le restanti sono di colori tutti diversi fra loro e diversi dal rosso e dal blu. Si vuole costruire un'insegna luminosa formata da queste 20 lampadine allineate. Calcolare in quanti modi diversi si può costruire l'insegna nei 2 casi:

- le lampadine dello stesso colore sono indistinguibili fra loro - le lampadine dello stesso colore sono diverse una dall’altra

(ovviamente le lampadine di colore diverso sono in ogni caso diverse una dall’altra) (6 p.)

Esercizio 5. Dato l’insieme A={1,2,3,4,5,6,7} e dato l’insieme B i cui elementi sono

tutti i possibili sottoinsiemi di A, calcolare il numero delle funzioni f: A  B tali che

l’immagine di ogni numero pari è un sottoinsieme di cardinalità >5. (5 p.)