In ogni componente i vertici hanno tutti grado dispari (nella prima 1079, nella seconda 1439), dunque in nessuna componente esiste un cammino Euleriano.

Compito di Matematica Discreta I (1 giugno 2007)

Soluzioni

Esercizio 1. Due disposizioni x,y sono collegate da un arco se entrambe hanno il primo elemento pari o dispari: vi sono dunque 2 componenti connesse, una formata dalle disposizioni con il primo elemento pari (con 3⋅6⋅5⋅4⋅3=1080 vertici), l’altra da quelle con il primo elemento dispari (con 4⋅6⋅5⋅4⋅3=1440 vertici).

In ogni componente ogni vertice è adiacente a tutti gli altri, quindi il numero cromatico di ogni componente coincide con il numero di vertici: il numero cromatico del grafo è allora il numero dei vertici della componente con più vertici, cioè 1440.

In ogni componente i vertici hanno tutti grado dispari (nella prima 1079, nella seconda 1439), dunque in nessuna componente esiste un cammino Euleriano.

Esercizio 2. Si può usare il principio di inclusione-esclusione, costruendo i 3 insiemi X,Y,Z contenenti rispettivamente le parole in cui la 1

^a

, 3

^a

lettera, la 1

^a

, 5

^a

lettera, la 3

^a

, 5

^a

lettera sono vocali, e calcolando:

⎪X∪Y∪Z⎪={⎪X⎪+⎪Y⎪+⎪Z⎪}-{⎪X∩Y⎪+⎪X∩Z⎪+⎪Y∩Z⎪}+⎪X∩Y∩Z⎪=

=3⋅(3

²

9

³

)-3⋅(3

³

9

²

)+ 3

³

9

²

.

Esercizio 3. Le possibili scelte per f(6) sono tante quante i sottoinsiemi di cardinalità dispari di A,

quindi in numero di =5+10+1=16. Fissata la scelta per f(6), le possibilità per f(2) sono in numero di 2

⎟⎟ ⎠

⎜⎜ ⎞

⎝ + ⎛

⎟⎟ ⎠

⎜⎜ ⎞

⎝ + ⎛

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

5 5 3 5 1 5

5

-1 (perché 2

⁵

è il numero dei sottoinsiemi di A, ma si deve escludere la scelta già fatta per f(6)); fissata la scelta per f(6),f(2), le possibilità per f(4) sono in numero di 2

⁵

-2 etc…

Per il principio delle scelte multiple, il numero totale di funzioni f è il prodotto:

16⋅(2

⁵

-1)⋅(2

⁵

-2)⋅(2

⁵

-3)⋅(2

⁵

-4).

Esercizio 4.

Si ha (g o ^f)(x)=g( ⎟⎟ ^{)=x+2, (f} o ^{g)( )=f(ab)=}

⎠

⎜⎜ ⎞

⎝

⎛ + 1 0

1 2

x ⎟⎟

⎠

⎜⎜ ⎞

⎝

⎛ d c

b

a ⎟⎟

⎠

⎜⎜ ⎞

⎝

⎛ +

1 0

1 2 ab

Si verifica facilmente che g o f è iniettiva e surgettiva, mentre f o g non è iniettiva: per esempio (f g)( o _⎟⎟ )= =(f o ^{g)( ) .}

⎠

⎜⎜ ⎞

⎝

⎛ 0 0

0

1 ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 1 0

1

2 ⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 0 0

0 0

Esercizio 5. Sia S

n

la somma dei primi n termini della successione. La tesi è che S

n

= 2 n

1 n

+

+ per ogni

naturale n. Si può usare il principio di induzione.

Per n=1, si ha S

1

= 2 1 =

1 1

1

+ . Supponiamo che S

k

= 1 k

k

+ e dimostriamo che S

k+1

= 2 k

1 k

+

+ : ma si ha

S

k+1

=S

k

+a

k+1

= 1 k

k + +

2) 1)(k (k

1 +

+ =

2) 1)(k (k

1 1) k(k

+ +

+

+ =

2) 1)(k (k

1)

(k

²

+ +

+ =

2 k

1 k

+ +

Esercizio 6. Si deve calcolare il numero di matrici in cui vi sono esattamente 2 valori=1 nella prima riga.

Le scelte possibili delle posizioni dei 2 valori=1 nella prima riga sono in numero di =10; fissata una di tali scelte, le scelte possibili del contenuto 0,1 delle rimanenti 10 caselle della seconda e terza riga sono in numero di 2

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ 2 5

10

. Per il principio delle scelte multiple la risposta è il prodotto 10⋅2

¹⁰

.