Compito di Matematica Discreta I (5 settembre 2008) Soluzione Esercizio 1.

Compito di Matematica Discreta I (5 settembre 2008)

Soluzione

Esercizio 1. Il grafo è connesso (dunque ha 1 sola componente connessa): infatti dati due vertici x,y essi sono sempre uniti da un cammino (se hanno le prime lettere consecutive sono uniti da un arco, mentre se hanno le prime lettere non consecutive si può costruire un cammino che li unisce passando per vertici con le prime lettere in successione). Il numero cromatico è 2: basta usare un colore per i vertici con la prima lettera a, c, ed un altro colore per i vertici con la prima lettera b, d. I vertici con la prima lettera a sono adiacenti a quelli con la prima lettera b dunque il loro grado è 4⁵; quelli con la prima lettera b sono adiacenti a quelli con la prima lettera a, c dunque il loro grado è 4⁵+4⁵; analogamente i vertici con la prima lettera c hanno grado 4⁵+4⁵, e quelli con la prima lettera d hanno grado 4⁵: poiché tutti i vertici hanno grado pari, e il grafo è connesso, esiste nel grafo un cammino Euleriano ciclico.

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

se A è l’insieme di tutte le matrici, e se X (rispettivamente Y) è l’insieme delle matrici in cui la prima diagonale (rispettivamente la seconda) contiene esclusivamente numeri maggiori di 5, la risposta è:

A-XY= A-{X+Y-[XY}= 8²⁵-{ 3⁵8²⁰+3⁵8²⁰-3⁹8¹⁶ }

Esercizio 3. Si può applicare il principio di induzione al predicato P(n)=”Il numero delle parole sull’alfabeto {0,1} di lunghezza n è 2ⁿ⁺¹-2 ”.

P(1) è vero perché le parole sull’alfabeto {0,1} di lunghezza 1 sono 0,1 e sono in numero di 2=2¹⁺¹-2. Supponiamo vero P(n) e dimostriamo vero P(n+1)=”Il numero delle parole sull’alfabeto {0,1} di lunghezza n+1 è 2ⁿ⁺²-2”.

Ma il numero delle parole sull’alfabeto {0,1} di lunghezza n+1 si ottiene sommando il numero delle parole sull’alfabeto {0,1} di lunghezza n (che per ipotesi è 2ⁿ⁺¹-2) con il numero delle parole di lunghezza n+1 (che è 2ⁿ⁺¹) e si ottiene appunto:

2ⁿ⁺¹-2+2ⁿ⁺¹ = 22ⁿ⁺¹-2 = 2ⁿ⁺²-2 .

Esercizio 4. Ogni sottoinsieme C del quesito si ottiene dall’unione di un insieme di 2 vocali ( 

 



 2

4 scelte possibili) con un sottoinsieme di cardinalità 4 di {b,c,d,f,g,h} ( 

 



 4 6

scelte possibili) , quindi il numero di tali sottoinsiemi è il prodotto di questi 2 valori, per il principio delle scelte multiple.

Esercizio 5. Le combinazioni richieste sono tante quante le combinazioni con ripetizione degli elementi {1,3,4,6,7} presi a 15 a 15, in numero di 

 



 4 19