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

Compito di Matematica Discreta I (13 febbraio 2009)

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 i numeri naturali di 4 cifre (in base 10) con cifre scelte fra 1,2,3,4,6, e in cui due vertici distinti x,y sono adiacenti se il prodotto della seconda cifra di x e della seconda cifra di y è un multiplo di 3.

Quante componenti connesse ha il grafo ? (3 p.) Qual è il numero cromatico del grafo ? (3 p.)

In ogni componente (considerata come grafo a sé stante) esiste un cammino Euleriano ? (3 p.)

Esercizio 2. Calcolare quante diverse matrici 6x6 ad elementi nell’insieme {0,1,2,3,4} si possono costruire, con la condizione che ognuna contenga esattamente 6 valori =0 e 8 valori =1. (5 p.)

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

(n+3)(n+4)(n+5) è multiplo di 3.

5 p.)

Esercizio 4. Un’insegna luminosa è formata da 14 lampadine colorate allineate.

Utilizzando solo i colori giallo, verde, rosso, arancione, blu, marrone , quante diverse insegne si possono ottenere separatamente nei due casi:

a) non è permesso avere un’insegna con tutte e 14 le lampadine dello stesso colore

b) nessuna delle prime 8 lampadine è verde ed esattamente 2 delle ultime 6 lampadine sono gialle (5 p)

Esercizio 5. Dati gli insiemi A={a,b,c}, B={xZ / -5  x  +5}, calcolare il numero di tutte le funzioni f: A  B che non soddisfano nessuna delle seguenti condizioni:

a) sono iniettive;

b) le immagini di tutti gli elementi di A sono numeri 1;

c) le immagini di tutti gli elementi di A sono numeri 3 (6 p.)