Compito di Matematica Discreta I (29 gennaio 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 tutti i numeri naturali di 8 cifre (in base 10) con cifre scelte fra 1,2,3,4,5,6,7 e in cui due vertici distinti x,y sono collegati da un arco se la differenza in valore assoluto della seconda cifra di x e della seconda cifra di y è 3.
Calcolare il numero di componenti connesse del grafo, e il numero di vertici di ogni componente. (3 p.)
Calcolare il numero cromatico del grafo (3 p.)
In ogni componente connessa (considerata come grafo a sé stante) dire se esiste un cammino Euleriano ciclico o non ciclico. (2 p.)
Esercizio 2. Si considerino l’insieme A di tutti i numeri naturali da 1 a 7 e l’insieme B di tutti i numeri naturali da 1 a 10. Calcolare il numero delle funzioni f: A → B tali che almeno 2 fra gli elementi 1,2,3 di A hanno immagine dispari in B. (4 p.)
Calcolare poi il numero delle funzioni iniettive f: A → B tali che almeno 2 fra gli elementi 1,2,3 di A hanno immagine dispari in B. (3 p.)
Esercizio 3. Considerata la successione delle potenze di base 5 ad esponente naturale:
5
1, 5
2, 5
3, ………..
dimostrare che, per ogni naturale n, il prodotto dei termini della successione dal posto 3 al posto n+3 (inclusi) è uguale a
26 4) 3)(n (n
5
− + +
(3 p.)
Esercizio 4. Dato l’insieme A={1,2,3,4,5,6} dire se è più grande il numero dei sottoinsiemi di A che contengono l’elemento 2 o il numero dei sottoinsiemi di A che non contengono l’elemento 3. (4 p.)
Esercizio 5. Dati gli insiemi A={1,2,3,4}, B={a,b,c,d,e}, e considerato l’insieme C di tutti i sottoinsiemi di B, calcolare il numero di tutte le funzioni f: A → C tali che l’immagine f(2) dell’elemento 2 di A è un sottoinsieme di B cardinalità 3. (4 p.) Esercizio 6. Date le seguenti 8 pedine, ognuna delle quali porta stampata una cifra:
2 3 7 3 2 4 5 2
