812  612  612 

Prova in itinere di Matematica Discreta (Soluzioni) (14 marzo 2011)

Esercizio 1. Si può utilizzare il principio delle scelte multiple: ogni funzione dipende dalla scelta delle immagini degli elementi di A. Il numero delle scelte possibili per le immagini (fissando ad ogni passo le scelte precedenti) è: 10 per f(1); 9 per f(2),f(3),f(4); 10 per f(8); 9 per f(9),f(10); 10 per f(14); 9 per f(15),f(16). Il numero totale di funzioni è dunque il prodotto 10

9

. Poiché tutte le funzioni iniettive soddisfano la proprietà suddetta, la risposta al secondo quesito è semplicemente il numero delle funzioni iniettive (che poi sono biunivoche) ossia 10! .

Esercizio 2. I vertici con ultima cifra 2 sono adiacenti ai vertici con ultima cifra 3; i vertici con ultima cifra 4 sono adiacenti a quelli con ultima cifra 9; i vertici con ultima cifra uguale non sono adiacenti fra loro tranne che nel caso di ultima cifra 4: esistono quindi 2 componenti connesse, la prima contenente i vertici con ultima cifra 2,3 e la seconda quelli con ultima cifra 4,9. Nella prima componente il numero cromatico è 2: basta colorare con un colore i vertici con ultima cifra 2 e con un secondo colore quelli con ultima cifra 3. Nella seconda componente i vertici con ultima cifra 4 (che sono in numero di 4

) devono essere colorati con 4

colori diversi, ma un ulteriore colore basta per colorare quelli con ultima cifra 9, dunque il numero cromatico della seconda componente (ed anche del grafo) è 4

+1.

I vertici con ultima cifra 2 (adiacenti a quelli con ultima cifra 3) hanno grado 4

(pari); quelli con ultima cifra 3 (adiacenti a quelli con ultima cifra 2) hanno grado 4

(pari): nella prima componente esiste un cammino Euleriano ciclico. I vertici con ultima cifra 9 (adiacenti a quelli con ultima cifra 4) hanno grado 4

(pari); quelli con ultima cifra 4 (adiacenti a tutti gli altri con ultima cifra 4 e a quelli con ultima cifra 9) hanno grado 4

+4

-1 (dispari): poiché nella seconda componente esistono più di 2 vertici di grado dispari, non esiste in essa un cammino Euleriano.

Esercizio 3. Si può applicare il principio di induzione. L’affermazione è vera per n=1 perché in questo caso la somma si riduce al solo addendo f(1)=(1+4)/(1+3)=5/4 ed in effetti 5/4=(1+4)/4.

Supponendola vera per un generico valore n (cioè supponendo che il prodotto delle immagini dei primi n numeri naturali 1,2,….,n sia uguale al numero (n+4)/4 ), dimostriamola vero per n+1:

dunque la tesi da dimostrare è che il prodotto delle immagini dei primi n+1 numeri naturali 1,2,

….,n,n+1 è uguale al numero (n+5)/4. Ma tale prodotto si ottiene moltiplicando il prodotto delle immagini dei primi n numeri naturali 1,2,….,n (che per ipotesi é uguale al numero (n+4)/4) per l’immagine del numero (n+1) (che è f(n+1)=(n+5)/(n+4)) ottenendo:

[(n+4)/4][(n+5)/(n+4)] = (n+5)/4 cioè la tesi.

Esercizio 4. Il numero totale di parole in A è 2

mentre quelle che contengono lo stesso numero di lettere x e y sono in numero di _



 



 6

12 (si devono solo scegliere le 6 posizioni della lettera x): dunque

le parole in A nella quali il numero di lettere x è diverso dal numero di lettere y sono in numero di 2

- _



 



 6

12 . Le parole in A che contengono un numero di x doppio del numero di y sono in numero di

 

 



 8

12 (si devono solo scegliere le 8 posizioni della lettera x).

Esercizio 5. Si può usare il principio di inclusione-esclusione in forma positiva.

Se X,Y,Z sono rispettivamente gli insiemi delle funzioni tali che f(6),f(7) sono sottoinsiemi non vuoti, f(7),f(8) sono sottoinsiemi non vuoti, f(7),f(9) sono sottoinsiemi non vuoti, la risposta al quesito è :

XYZ=X+Y+Z-{XY+XZ+YZ}+XYZ.

Applicando il principio delle scelte multiple si ha X=(2

-1)

(2

)

(le immagini possibili di 6,7 sono i sottoinsiemi non vuoti di A, in numero di 2

-1, mentre le immagini possibili di 1,2,3,4,5,8 sono i sottoinsiemi di A, in numero di 2

). Con ragionamenti analoghi si ha :

X=Y=Z=(2

-1)

(2

)

, XY=YZ=XZ=XYZ=(2

-1)

(2

)

.