5 5

Compito di Matematica Discreta I (29 gennaio 2007)

Soluzioni

Esercizio 1. Ogni vertice con la seconda cifra 1 è adiacente ad ogni vertice con la seconda cifra 4 che a sua volta è adiacente ad ogni vertice con la seconda cifra 7; ogni vertice con la seconda cifra 2 è adiacente ad ogni vertice con la seconda cifra 5; ogni vertice con la seconda cifra 3 è adiacente ad ogni vertice con la seconda cifra 6. Vi sono dunque 3 componenti connesse, la prima componente contenente i vertici con la seconda cifra 1 o 4 o 7 (7

+7

+7

vertici), la seconda componente contenente i vertici con la seconda cifra 2 o 5 (7

+7

vertici), la terza componente contenente i vertici con la seconda cifra 2 o 5 (7

+7

vertici).

La seconda componente può essere colorata con 2 colori (uno per i vertici con la seconda cifra 2 e un altro per quelli con la seconda cifra 5). Analogo ragionamento per la terza componente. Anche la prima componente può essere colorata con 2 colori (uno per i vertici con la seconda cifra 1 o 7 e un altro per quelli con la seconda cifra 4). Dunque il numero cromatico del grafo è 2.

Nella prima componente ogni vertice con la seconda cifra 4 ha grado 7

+7

(pari), ma ogni vertice con la seconda cifra 1 o 7 ha grado 7

(dispari). Nelle altre due componenti ogni vertice ha grado 7

(dispari). Dunque in nessuna componente esiste un cammino Euleriano, perché vi sono più di 2 vertici di grado dispari.

Esercizio 2. Si può applicare il principio di inclusione-esclusione costruendo i 3 insiemi:X={ f: A  B / f(1), f(2) dispari}, Y={ f: A  B / f(1), f(3) dispari},

Z={ f: A  B / f(2), f(3) sono dispari}, e calcolando

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

dove X=Y=Z=5

10

, XY=XZ=YZ=XYZ=5

10

. Se ci si limita alle sole funzioni iniettive il calcolo diventa :

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

X=Y=Z=5487654,

XY=XZ=YZ=XYZ=5437654 Esercizio 3. Si può applicare il principio di induzione.

Per n=1 il predicato è vero perché 5

5

=5

=

5







.

Supponiamo vero il predicato per n=k e dimostriamolo per n=k+1.

Il prodotto dei termini della successione dal posto 3 al posto k+1+3=k+4 è uguale al prodotto dei termini dal posto 3 al posto k+3, moltiplicato per il termine di posto k+4, quindi è uguale a

6 4) 3)(k (k

5







5

=

6 4) 3)(k (k

5 ^{ }







=

6 5) 4)(k (k

5







il che dimostra che il predicato è vero anche per n=k+1.

Esercizio 4. I sottoinsiemi che contengono l’elemento 2 si ottengono aggiungendo il 2 ad un generico sottoinsieme di {1,3,4,5,6}, quindi sono in numero di 2

=32.

Analogamente i sottoinsiemi che contengono l’elemento 3 sono in numero di 32,

quindi i sottoinsiemi che non contengono 3 sono in numero di 2

-2

=32, lo stesso numero.

Esercizio 5. Le possibilità per f(2) sono in numero di

 



 3

5

, mentre le possibilità per

l’immagine di ognuno dei numeri 1,3,4 sono 2

. La risposta è dunque il prodotto

 



 3 5

2

2

2

, per il principio delle scelte multiple.

Esercizio 6. Si tratta di calcolare il numero di disposizioni con ripetizione delle cifre 2,3,4,5,7 prese ad 8 ad 8, ma in cui la cifra 2 è ripetuta 3 volte, la cifra 3 è ripetuta 2 volte, e ognuna delle cifre 4,5,7 è ripetuta 1 sola volta.

Le possibili scelte per la posizione della cifra 2 sono in numero di

 



 3

8

. Fissata una di

tali scelte, le possibili scelte per la posizione della cifra 3 sono in numero di

 



 2 5

. Fissate le scelte per le cifre 2 e 3, le possibili scelte per le posizioni delle 3 cifre restanti sono in numero di 3!. La risposta è dunque il prodotto

 



 3 8 

 



 2

5

3!, per il

principio delle scelte multiple.