Compito di Matematica Discreta I (6 giugno 2008)
Soluzioni
Esercizio 1. Le matrici che hanno il primo elemento della prima riga =0 sono adiacenti a tutte le altre, perciò, dati comunque due vertici distinti x, y, esiste un cammino che li unisce (per es. passando per una delle matrici suddette): dunque il grafo è connesso ed esiste una sola componente connessa.
Le matrici che hanno il primo elemento della prima riga =0 (che sono in numero di 53) devono essere colorate con colori tutti differenti, ma si possono usare un ulteriore colore per quelle che hanno il primo elemento della prima riga >0, e un ulteriore colore per quelle che hanno il primo elemento della prima riga <0: il numero cromatico è 53+2..
Le matrici che hanno il primo elemento della prima riga =0 sono adiacenti a tutte le altre dunque hanno grado 54-1 (pari); quelle che hanno il primo elemento della prima riga >0 sono adiacenti a quelle che hanno il primo elemento della prima riga 0 dunque hanno grado 53+253 (dispari). Analogamente quelle che hanno il primo elemento della prima riga
>0 hanno grado 53+253 (dispari). Poiché esistono più di 2 vertici di grado dispari, non esiste nel grafo un cammino Euleriano.
Esercizio 2. Si può usare il principio di inclusione-esclusione in forma negativa. Se A è l’insieme di tutte le matrici 3x3 sull’insieme {0,1,2,3,4} (sono in tutto 59), se B è l’insieme delle matrici di A che soddisfano la prima condizione, e C quello delle matrici che soddisfano la seconda condizione la risposta è:
A-BC = 59-[58+57-56]
(C ha 57 matrici perchè l’elemento costante nella terza riga si può scegliere in 5 modi, mentre in ognuna delle 6 caselle rimanenti vi è un valore a scelta fra 5 possibili).
Esercizio 3. a) Si può applicare il principio di induzione al predicato P(n)=”an=7-5n”. P(1) è vero perchè a1=7-51=2. Se è vero P(n) (quindi se an=7-5n) dimostriamo vero P(n+1)=”an=7- 5(n+1)”: il termine an+1 si ottiene dal precedente an sottraendo 5, quindi an+1=an-5=7-5n-5=7- 5(n+1).
b) Stesso ragionamento per il predicato P(n)=”a1+….+an=(9n-5n2)/2”. P(1) è vero perché a1=(91-512)/2=2. Supponendo vero P(n) dimostriamo vero anche P(n+1)=”a1+….
+an+an+1=(9(n+1)-5(n+1)2)/2”. Si ha (sviluppando i calcoli):
a1+….+an+an+1=(9n-5n2)/2+(7-5(n+1)) =(9(n+1)-5(n+1)2)/2.
Esercizio 4. Il numero dei sottoinsiemi di A che sono contenuti in B è il numero dei sottoinsiemi di un insieme di cardinalità 4, dunque è 24; i sottoinsiemi di A che contengono B si ottengono dall’unione di B con un sottoinsieme del complementare di B, dunque anch’essi sono in numero di 24.
Esercizio 5. Le matrici con 3 valori =1 sono in numero di
3
9 (si devono scegliere 3
caselle fra 9); ognuno degli elementi 1,3,5,7 ha 29 possibili immagini, mentre ognuno degli elementi 2,4,6 ne ha
3
9 : per il principio delle scelte multiple la risposta è (29)4 393
.
