Esercizi di Matematica Discreta (04/02/09) (Soluzioni) 1)

Esercizi di Matematica Discreta (04/02/09) (Soluzioni)

1) Si può applicare il principio di inclusione-esclusione (in forma positiva) : se X,Y,Z sono rispettivamente gli insiemi contenenti i sottoinsiemi di A che hanno intersezione vuota con B,C,D, si tratta di calcolare:

XYZ= X+Y+Z-[XY+XZ+YZ]+XYZ

Poiché X contiene i sottoinsiemi del complementare di B (complementare che ha cardinalità 6) si ha X=2

. Con ragionamenti analoghi si ha Y=2

, Z=2

. Poiché XY contiene i sottoinsiemi del complementare di {1,2,3,7,8,9,10} (complementare che ha cardinalità 3) si ha XY=2

. Con ragionamenti analoghi si haXZ=2

,

YZ=2

, XYZ=2

.

2) Si può applicare il principio d’induzione al predicato P(n)=”n

+4n è multiplo di 5”.

E’ vero P(1)=”1

+41 è multiplo di 5”, perché 1

+41=5. Supponendo vero P(k)=”k

+4k è multiplo di 5”, dimostriamo vero P(k+1)=”(k+1)

+4(k+1) è multiplo di 5”. Ma, sviluppando la potenza del binomio con la regola di Newton si ha:

(k+1)

+4(k+1)=(k

+5k

+10k

+10k

+5k+1)+(4k+4)=( k

+4k)+(5k

+10k

+10k

+5k+5) che è multiplo di 5, essendo somma di multipli di 5.

3) Si può usare il principio delle scelte multiple: ognuna delle funzioni dipende dalla scelta dell’immagine dei 7 elementi del dominio, e (considerata la condizione che l’immagine di 1,3,5,7 può essere scelta fra 8,10,12) il loro numero è 3

6

. Nel caso di funzioni iniettive si deve tener conto che la cardinalità del dominio è maggiore di quella del codominio, quindi il numero di funzioni è 0.

4) Il vertice 1 è adiacente al 4, il 4 al 7, il 7 al 10 etc.., il 25 al 28 (e questi vertici formano una componente connessa). In modo analogo si trovano altre 2 componenti (per un totale di 3 componenti): {2,5,8,….,26,29}, {3,6,9,…..,27,30}.

Ogni componente ha numero cromatico 2 (si possono “alternare” 2 colori nella successione dei vertici) quindi il grafo ha numero cromatico 2.

Nella componente {1,4,7,…..,25,28} i vertici 1, 28 hanno grado 1 (dispari), e gli altri vertici hanno grado 2 (pari), dunque esiste nella componente un cammino Euleriano non ciclico (che ha vertice iniziale e finale appunto nei vertici 1 e 28). Lo stesso vale nelle altre 2 componenti.

5) Come suggerito, per costruire ognuno dei sottoinsiemi C, si deve scegliere un sottoinsieme di B di cardinalità 3 (e tale scelta si può fare in

 



 3

6

modi diversi) e poi

costruirne l’unione con un sottoinsieme di {7,8,9,10,11,12} (che si può scegliere in 2

modi diversi): per il principio delle scelte multiple la risposta è il prodotto

 



 3 6

2

.