Compito di Matematica Discreta I(3 marzo 2009)SoluzioniEsercizio 1. Si ha A=2

Compito di Matematica Discreta I (3 marzo 2009)

Soluzioni

Esercizio 1. Si ha A=2

=16, B=2

=32, da cui il numero di funzioni f: AB è (2

)

=2

, mentre il numero di funzioni f: BA è (2

)

=2

(maggiore del primo).

Poiché A<B non esistono funzioni surgettive f: AB né iniettive f: BA.

Esercizio 2. Si devono contare le parole che contengono 6 vocali e 2 consonanti, utilizzando per esempio il principio delle scelte multiple: le scelte per le 6 posizioni delle vocali sono in numero di

 



 6

8

; fissata una di tali scelte, le scelte per le 6 vocali in queste 6 posizioni sono in numero di 3

; fissata una di tali scelte, le scelte delle 2 consonanti nelle 2 posizioni rimanenti sono in numero di 4

. Dunque la risposta è il prodotto

 



 6

8

3

4

.

Esercizio 3. Si può usare il principio di induzione.

Per n=1 il numero (41

-41+56)/28=2 è intero. Supponendo vera l’affermazione per n=k, dimostriamola vera per n=k+1: sviluppando la potenza del binomio con la regola di Newton si ha:

[4(k+1)

-4(k+1)+56]/28=[4(k

+7k

+21k

+35k

+35k

+21k

+7k+1)-4(k+1)+56]/28=

=[(4k

-4k+56)/28]+k

+12k

+5k

+5k

+3k

+k E tale numero è un intero, perché somma di interi.

Esercizio 4. I vertici con seconda cifra 5 sono tutti adiacenti fra loro, mentre quelli con seconda cifra 2 sono adiacenti a quelli con seconda cifra 3, i quali, a loro volta, sono adiacenti a quelli con seconda cifra 7. Dunque esistono 2 componenti connesse:

la prima contenente i vertici con seconda cifra 5 (con 4

vertici), e la seconda quelli con seconda cifra 2,3,7 (con 34

vertici).

Nella prima componente il numero cromatico coincide con il numero dei vertici 4

; nella seconda il numero cromatico è 2 (si possono colorare con lo stesso colore i vertici con seconda cifra 2,7 e con un secondo colore quelli con seconda cifra 3).

Dunque il numero cromatico del grafo è 4

, il maggiore dei due numeri.

Nella prima componente ogni vertice ha grado 4

-1 (dispari), dunque non esiste un cammino Euleriano. Nella seconda i vertici con seconda cifra 2,7 hanno grado 4

(pari), mentre quelli con seconda cifra 3 hanno grado 2 4

(pari), dunque esiste un cammino Euleriano.

Esercizio 5. Si può usare il principio di inclusione-esclusione, costruendo gli insiemi X,Y,Z che contengono rispettivamente le parole in cui la 1

,2

lettera (la 2

,3

lettera, la 3

,4

lettera) sono vocali e calcolando la cardinalità dell’unione di X,Y,Z :

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

Utilizzando poi opportunamente il principio delle scelte multiple, si ha:

X=Y=Z=3

4

,XY=YZ=3

4,XZ=XYZ=3

.