Compito di Matematica Discreta I (25 febbraio 2008) Soluzioni Esercizio 1.

(1)

Compito di Matematica Discreta I (25 febbraio 2008)

Soluzioni

Esercizio 1. I vertici con 2 colonne sono adiacenti a quelli con 3 colonne che a loro volta sono adiacenti a quelli con 4 colonne e questi sono adiacenti a quelli con 5 colonne, dunque il grafo è connesso (dati 2 vertici qualunque x,y esiste un cammino che li unisce utilizzando vertici con numero di colonne consecutivi): esiste una componente connessa. Il numero cromatico è 2: basta colorare i vertici con 2 e 4 colonne con un colore, ed i vertici con 3 o 5 colonne con un altro colore. Il grado dei vertici con 2 colonne è 2

⁹

, quello dei vertici con 3 colonne è 2

⁶

+2

¹²

, quello dei vertici con 4 colonne è 2

⁹

+2

¹⁵

, quello dei vertici con 5 colonne è 2

¹²

: ogni vertice ha grado pari dunque nel grafo (connesso) esiste un cammino Euleriano ciclico.

Esercizio 2. Si può usare usa il principio di inclusione-esclusione in forma negativa:

se X,Y sono i sottoinsiemi di A formati dalle coppie che soddisfano rispettivamente a),b) la risposta al quesito é:

A-XY= A-{X+Y-XY}=50

²

-{25

²

+3050-1525}.

Esercizio 3. Si applica il principio di induzione al predicato P(n)="A

ⁿ⁺¹

=  

 



 

1 0

1) 2(n 1

".

P(1) è vero, in quanto A

²

=  

 



 1 0

2 1   

 



 1 0

2 1 =  

 



 1 0

4 1 =  

 



 

1 0

) 1 1 ( 2

1 .

Supponiamo vero P(n), e dimostriamo vero P(n+1)="A

ⁿ⁺²

=  

 



 

1 0

2) 2(n

1 ".

Si ha infatti: A

ⁿ⁺²

=A

ⁿ⁺¹

A=  

 



 

1 0

1) 2(n

1   

 



 1 0

2 1 =  

 



  

1 0

1) 2(n 2

1 =  

 



 

1 0

2) 2(n

1 .

Esercizio 4. Un sottoinsieme di A che contiene {1,2,3} si ottiene dall’unione di{1,2,3} con un qualunque sottoinsieme di {4,5,6,7,8,9}, dunque il loro numero è uguale al numero dei possibili sottoinsiemi di {4,5,6,7,8,9} cioé 2

⁶

. Fra questi sottoinsiemi, quelli di cardinalità pari si ottengono dall’unione di{1,2,3} con un qualunque sottoinsieme di cardinalità dispari di {4,5,6,7,8,9}, dunque il loro numero è uguale al numero dei possibili sottoinsiemi di cardinalità dispari di {4,5,6,7,8,9}

cioé _



 



 1

6 + _



 



 3

6 + _



 



 5 6 .

Esercizio 5. Si può usare il principio delle scelte multiple: ognuno dei numeri naturali da contare dipende dalla scelta delle posizioni della cifra 4 e (fissata tale scelta) dal contenuto delle restanti posizioni (da riempire ciascuna con una delle 8 cifre diverse da 4). Poiché la cifra 4 è ripetuta 1 o 3 o 5 o 7 volte, la risposta è: