Compito di Matematica Discreta I (28 gennaio 2008)
Soluzioni
Esercizio 1. I vertici di lunghezza 1 sono adiacenti a quelli di lunghezza 5, i vertici di lunghezza 2 sono adiacenti a quelli di lunghezza 4, i vertici di lunghezza 3 sono tutti adiacenti fra loro. Dunque vi sono 3 componenti connesse: la prima formata dai vertici di lunghezza 1 e 5 (51+55 vertici), la seconda dai vertici di lunghezza 2 e 4 (52+54 vertici), la terza dai vertici di lunghezza 3 (53 vertici). Per colorare i vertici della prima e seconda componente bastano 2 colori, ma nella terza componente (essendo tutti i vertici adiacenti fra loro) sono necessari tanti colori quanti sono i vertici, quindi 53 colori: dunque il numero cromatico del grafo è 53. I vertici di lunghezza 1 hanno grado 55 (dispari), quelli di lunghezza 5 grado 51 (dispari), quelli di lunghezza 2 grado 54 (dispari), quelli di lunghezza 4 grado 52 (dispari), quelli di lunghezza 3 grado 53-1 (pari): solo nella terza componente esiste un cammino Euleriano ciclico.
Esercizio 2. Si può applicare il principio di inclusione-esclusione in forma negativa.
Se X è l’insieme dei numeri naturali di 4 cifre (in base 10), con cifre scelte fra 1,2,3,4,5,6,7,8, e se Y,Z,T sono rispettivamente i sottoinsiemi di X contenenti i numeri tali che 1a e 2a cifra siano <6, 2a e 3a cifra siano <6, 3a e 4a cifra siano <6, la risposta al quesito è:
X-YZT= X-{Y+Z+T-YZ-YT-ZT+YZT}=
=84-{5282+5282+5282-538-54-538+54}=...
Esercizio 3. Si può applicare il principio di induzione al predicato P(n)=”n3+(n+1)3+ (n+2)3 è multiplo di 9”.
Per n=1 il predicato è vero: 13+(1+1)3+(1+2)3=36 è multiplo di 9.
Supponendo vero P(n) dimostriamo P(n+1)=”(n+1)3+(n+2)3+(n+3)3 è multiplo di 9”.
Si ha : (n+1)3+(n+2)3+(n+3)3=(n+1)3+(n+2)3+(n3+9n2+27n+27)=
[n3+(n+1)3+(n+2)3]+ 9n2+27n+27 (multiplo di 9 perché somma di multipli di 9).
Esercizio 4. Nel primo caso: le scelte possibili per la posizione delle 7 lampadine
rosse sono
7 20
; fissata una di tali scelte, le scelte per la posizione delle 5 blu sono
5 13
; fissata la scelta per le rosse e le blu, le scelte per la posizione delle rimanenti 8
lampadine sono 8!. La soluzione si ottiene moltiplicando i 3 numeri precedenti.
Nel secondo caso: essendo tutte le 20 lampadine diverse una dall’altra, la soluzione è 20! (il numero delle permutazioni delle 20 lampadine).
Esercizio 5.
Si può applicare il principio delle scelte multiple: per ognuno dei 3 numeri pari le
possibili immagini sono i numero di
6 7
+
7 7
=8; per ognuno dei 4 numeri dispari le
possibili immagini sono i numero di 27, dunque la risposta è il prodotto 83(27)4 .
