Compito di Matematica Discreta I (4 luglio 2008) Soluzione Esercizio 1.

Compito di Matematica Discreta I (4 luglio 2008)

Soluzione

Esercizio 1. Ogni vertice x con la prima cifra pari è adiacente ad ogni vertice y con la prima cifra dispari, ma vertici con le prime cifre entrambe pari o dispari non sono adiacenti. Il grafo è connesso (dunque ha 1 sola componente connessa): infatti dati due vertici x,y essi sono sempre uniti da un cammino (se hanno per es. le prime cifre entrambe pari, basta costruire un cammino di lunghezza 2 passante per un vertice con la prima cifra dispari etc…). Il numero cromatico è 2: basta usare un colore per i vertici con la prima cifra pari e un altro colore per i vertici con la prima cifra dispari.

I vertici con la prima cifra pari sono in numero di 37⁵, quelli con la prima cifra dispari sono in numero di 47⁵, quindi i primi hanno grado 47⁵ (pari) e i secondi grado 37⁵ (dispari): poiché esistono più di 2 vertici di grado dispari, non esiste nel grafo un cammino Euleriano.

Esercizio 2. Si può applicare il principio di inclusione-esclusione: se X (rispettivamente Y oppure Z) è l’insieme delle matrici in cui 1^a,2^a,3^a casella della prima riga (rispettivamente 2^a,3^a,4^a oppure 3^a,4^a,5^a) contengono tutte numeri pari, la risposta è:

XYZ= X+Y+Z-[XY+XZ+YZ]+XYZ=

=2³5¹²+2³5¹²+2³5¹²-[2⁴5¹¹+2⁴5¹¹+2⁵5¹⁰]+2⁵5¹⁰

Esercizio 3. Si può applicare il principio di induzione al predicato P(n)=”n⁷-n+21 è multiplo di 7”.

P(1) è vero perché 1⁷-1+21=21 è multiplo di 7. Supponiamo vero P(n) e dimostriamo vero P(n+1)=”(n+1)⁷-(n+1)+21 è multiplo di 7”.

Si ha, sviluppando con la regola di Newton:

(n+1)⁷-(n+1)+21=(n⁷+7n⁶+21n⁵+35n⁴+35n³+21n²+7n+1)-(n+1)+21=

=(n⁷-n+21)+7n⁶+21n⁵+35n⁴+35n³+21n²+7n

e quest’ultimo numero è multiplo di 7, essendo somma di multipli di 7.

Esercizio 4. Ogni sottoinsieme C di A tale che CB={a,b,c} si ottiene dall’unione di {a,b.c} con un sottoinsieme di {f,g,h,i,l}, quindi il numero di tali sottoinsiemi C è 2⁵. Esercizio 5. Si devono costruire in successione 6 archi, a partire da v, e per ognuno di essi vi sono 9 possibili scelte (perché ogni vertice del grafo ha grado 9 per ipotesi): per il principio delle scelte multiple la risposta è 9⁶.