Compito di Matematica Discreta I (20 febbraio 2007) Soluzioni Esercizio 1.

(1)

Compito di Matematica Discreta I (20 febbraio 2007)

Soluzioni

Esercizio 1. Due vertici distinti x,y sono adiacenti se la lunghezza è per entrambi pari o dispari. Vi sono dunque 2 componenti connesse: la prima contenente i vertici con lunghezza pari, la seconda quelli con lunghezza dispari. La prima contiene 5

⁴

+5

⁶

vertici, la seconda 5

³

+5

⁵

+5

⁷

vertici.

Ogni vertice di ogni componente è adiacente a tutti gli altri vertici della stessa componente. Quindi tutti i vertici di una componente necessitano di un colore diverso. La prima componente richiede 5

⁴

+5

⁶

colori, la seconda 5

³

+5

⁵

+5

⁷

colori (numero maggiore): dunque 5

³

+5

⁵

+5

⁷

è il numero cromatico del grafo.

Nella prima componente ogni vertice ha grado 5

⁴

+5

⁶

-1 (dispari), nella seconda ogni vertice ha grado 5

³

+5

⁵

+5

⁷

-1 (pari): nella seconda esiste un cammino ciclico Euleriano, nella prima non esiste nessun cammino Euleriano.

Esercizio 2. Si può usare il principio di inclusione-esclusione in forma negativa, costruendo i 3 sottoinsiemi X,Y,Z di A contenenti rispettivamente le matrici in cui i gruppi 1,2 3 sono interamente riempiti con valori >0. Si calcola quindi:

⏐A⏐-⏐X∪Y∪Z⏐=

⏐A⏐-{⏐X⏐+⏐Y⏐+⏐Z⏐-⏐X∩Y⏐-⏐X∩Z⏐-⏐Y∩Z⏐+⏐X∩Y∩Z⏐}

dove⏐A⏐=7

¹²

,⏐X⏐=⏐Y⏐=4

³

7

⁹

,⏐Z⏐=4

⁴

7

⁸

,⏐X∩Y⏐=4

⁵

7

⁷

,⏐X∩Z⏐=⏐Y∩Z⏐=4

⁶

7

⁶

,

⏐X∩Y∩Z⏐=4

⁷

7

⁵

.

Esercizio 3. Per ognuno dei 3 numeri pari le possibili immagini sono in numero di 7!, ma per ognuno dei 4 numeri dispari le immagini sono in numero di 7

⁷

, quindi per il principio delle scelte multiple la risposta è il prodotto (7!)

³

(7

⁷

)

⁴

.

Esercizio 4. Nel caso di combinazioni semplici, una combinazione di classe 5 in cui compare l’elemento c si ottiene aggiungendo c ad una qualunque combinazione semplice di classe 4 dei restanti 7 elementi, per un totale di ⎟⎟ combinazioni.

⎠

⎜⎜ ⎞

⎝

⎛ 4 7

Nel caso di combinazioni con ripetizione, una combinazione di classe 5 in cui compare l’elemento c si ottiene aggiungendo c ad una qualunque combinazione con ripetizione di classe 4 di tutti gli 8 elementi, per un totale di ⎟⎟ ⎠ = combinazioni.

⎜⎜ ⎞

⎝

⎛ + 1 - 8

1 - 4

8 ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 7 11

Esercizio 5. Principio di induzione applicato al predicato P(n)=”5

ⁿ⁺²

ha la cifra delle decine uguale a 2 e la cifra delle unità uguale a 5”. Per n=1 il predicato è vero perché 5

¹⁺²

=125 ha la cifra delle decine uguale a 2 e la cifra delle unità uguale a 5. Supponendo vero P(k), dimostriamo vero P(k+1).

Si ha 5

^k+1+2

=5

^k+2

5. Per ipotesi le ultime 2 cifre del numero 5

^k+2

sono 2 e 5 e moltiplicando per 5 il si ottiene un numero che ha la stessa proprietà (ricordando le regole elementari del prodotto fra numeri naturali di più cifre in base 10).

Esercizio 6. Il numero totale di matrici booleane 4x5 è 2

²⁰

. Le matrici booleane 4x5 in cui il numero di valori =1 è uguale numero di valori =0, sono quelle contenenti esattamente 10 valori =1 e 10 valori =0: esse dipendono solo dalla scelta delle 10 posizioni (fra 20) in cui porre il valore 1, dunque sono in numero di ⎟⎟ ⎠ .

Compito di Matematica Discreta I (20 febbraio 2007) Soluzioni Esercizio 1.

Compito di Matematica Discreta I (20 febbraio 2007)

Soluzioni

Esercizio 1. Due vertici distinti x,y sono adiacenti se la lunghezza è per entrambi pari o dispari. Vi sono dunque 2 componenti connesse: la prima contenente i vertici con lunghezza pari, la seconda quelli con lunghezza dispari. La prima contiene 5

+5

vertici, la seconda 5

+5

+5

vertici.

Ogni vertice di ogni componente è adiacente a tutti gli altri vertici della stessa componente. Quindi tutti i vertici di una componente necessitano di un colore diverso. La prima componente richiede 5

+5

colori, la seconda 5

+5

+5

colori (numero maggiore): dunque 5

+5

+5

è il numero cromatico del grafo.

Nella prima componente ogni vertice ha grado 5

+5

-1 (dispari), nella seconda ogni vertice ha grado 5

+5

+5

-1 (pari): nella seconda esiste un cammino ciclico Euleriano, nella prima non esiste nessun cammino Euleriano.

Esercizio 2. Si può usare il principio di inclusione-esclusione in forma negativa, costruendo i 3 sottoinsiemi X,Y,Z di A contenenti rispettivamente le matrici in cui i gruppi 1,2 3 sono interamente riempiti con valori >0. Si calcola quindi:

⏐A⏐-⏐X∪Y∪Z⏐=

⏐A⏐-{⏐X⏐+⏐Y⏐+⏐Z⏐-⏐X∩Y⏐-⏐X∩Z⏐-⏐Y∩Z⏐+⏐X∩Y∩Z⏐}

dove⏐A⏐=7

,⏐X⏐=⏐Y⏐=4

7

,⏐Z⏐=4

7

,⏐X∩Y⏐=4

7

,⏐X∩Z⏐=⏐Y∩Z⏐=4

7

,

⏐X∩Y∩Z⏐=4

7

.

Esercizio 3. Per ognuno dei 3 numeri pari le possibili immagini sono in numero di 7!, ma per ognuno dei 4 numeri dispari le immagini sono in numero di 7

, quindi per il principio delle scelte multiple la risposta è il prodotto (7!)

(7

)

.

Esercizio 4. Nel caso di combinazioni semplici, una combinazione di classe 5 in cui compare l’elemento c si ottiene aggiungendo c ad una qualunque combinazione semplice di classe 4 dei restanti 7 elementi, per un totale di ⎟⎟ combinazioni.

⎠

⎜⎜ ⎞

⎝

⎛ 4 7

Nel caso di combinazioni con ripetizione, una combinazione di classe 5 in cui compare l’elemento c si ottiene aggiungendo c ad una qualunque combinazione con ripetizione di classe 4 di tutti gli 8 elementi, per un totale di ⎟⎟ ⎠ = combinazioni.

⎜⎜ ⎞

⎝

⎛ + 1 - 8

1 - 4

8 ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 7 11

Esercizio 5. Principio di induzione applicato al predicato P(n)=”5

ha la cifra delle decine uguale a 2 e la cifra delle unità uguale a 5”. Per n=1 il predicato è vero perché 5

=125 ha la cifra delle decine uguale a 2 e la cifra delle unità uguale a 5. Supponendo vero P(k), dimostriamo vero P(k+1).

Si ha 5

=5

5. Per ipotesi le ultime 2 cifre del numero 5

sono 2 e 5 e moltiplicando per 5 il si ottiene un numero che ha la stessa proprietà (ricordando le regole elementari del prodotto fra numeri naturali di più cifre in base 10).

Esercizio 6. Il numero totale di matrici booleane 4x5 è 2

. Le matrici booleane 4x5 in cui il numero di valori =1 è uguale numero di valori =0, sono quelle contenenti esattamente 10 valori =1 e 10 valori =0: esse dipendono solo dalla scelta delle 10 posizioni (fra 20) in cui porre il valore 1, dunque sono in numero di ⎟⎟ ⎠ .

⎜⎜ ⎞

⎝

⎛ 10 20

La risposta è dunque la differenza 2

- ⎟⎟ ⎠ .

⎜⎜ ⎞

⎝

⎛

10

20