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

Compito di Matematica Discreta I (25 febbraio 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 matrici booleane con 3 righe ed m colonne dove m assume tutti i valori interi fra 2 e 5 (inclusi) e in cui due vertici distinti x,y sono adiacenti se il numero delle colonne di x e il numero delle colonne di y sono interi consecutivi.

Calcolare il numero delle componenti connesse del grafo. (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. (3 p.)

Esercizio 2. Si consideri l’insieme B di tutti i numeri naturali 50. Calcolare il numero di coppie nel prodotto cartesiano A=BxB che non soddisfano simultaneamente nessuna delle seguenti condizioni:

a) il prodotto dei 2 elementi della coppia è dispari;

b) il primo numero della coppia è >20. (5 p.)

Esercizio 3. Si consideri la seguente matrice quadrata 2x2:

A =  

 



 1 0

2 1

e si considerino le successive potenze di base A ottenute utilizzando il prodotto righe per colonne: A

=A, A

=AA, A

=AAA etc....

Dimostrare che, per ogni numero naturale n, si ha A

=  

 



 

1 0

1) 2(n

1 (5 p.)

Esercizio 4. Dato l’insieme A={1,2,3,4,5,6,7,8,9}, calcolare il numero dei sottoinsiemi di A che contengono l’insieme {1,2,3} e fra questi sottoinsiemi calcolare poi il numero di quelli che hanno cardinalità pari (6 p.)

Esercizio 5. Calcolare il numero dei numeri naturali di 8 cifre (rappresentati in

base10) con cifre tutte diverse da 0, e in cui la cifra 4 è ripetuta un numero dispari di

volte (5 p.)