Compito di Matematica Discreta I (3 luglio 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 luglio 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 le matrici booleane 2x2 e in cui due vertici distinti x,y sono adiacenti se il numero di 1 presenti nella matrice x coincide con il numero di 1 presenti nella matrice y.

Calcolare il numero di componenti connesse del grafo, e il numero di vertici di ogni componente. (3 p.)

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

Nella componente connessa con il maggior numero di vertici, considerata come grafo a sé stante, dire se esiste un cammino ciclico Euleriano. (2 p.)

Esercizio 2. Calcolare il numero dei naturali composti da 8 cifre non nulle (in base 10) in cui una delle cifre è ripetuta esattamente 3 volte e tutte le altre cifre sono distinte fra loro (e diverse dalla cifra ripetuta 3 volte). (5 p.)

Esercizio 3.

Siano A={1,2,3,4,5,6,7} e B l’insieme delle matrici booleane 5x5.

Calcolare il numero delle funzioni f: A → B tali che le immagini di tutti i numeri pari di A sono matrici che contengono esattamente 3 valori uguali a 1. (5 p.)

Esercizio 4.

Dimostrare che la seguente congruenza:

2

≡2 (mod 7)

è vera per ogni naturale n. (4 p.)

Esercizio 5.

Dato un insieme A di cardinalità n e un suo sottoinsieme B di cardinalità m, calcolare il numero dei sottoinsiemi di A che hanno intersezione non vuota con B. (4 p.)

Esercizio 6.

Si consideri la seguente successione di 10 caselle numerate da 1 a 10:

1 2 3 4 5 6 7 8 9 10

e si definisca “zona A” quella formata dalle caselle numerate da 1 a 7 (inclusi) e

“zona B” quella formata dalle caselle numerate da 4 a 10 (inclusi).

Se si inserisce in ogni casella una lettera scelta fra {a,b,c} oppure si lascia vuota la

casella, quante sono le possibili configurazioni in cui né la zona A né la zona B sono

del tutto vuote ? (5 p.)