2) Caso a): applicando il principio delle scelte multiple si ottiene che tutte le possibili insegne (senza alcuna restrizione sulle lampadine) sono in numero di 6

ESERCIZI MATEMATICA DISCRETA (01/02/2011) Soluzioni

1) Si può utilizzare il principio delle scelte multiple. Nel primo caso le scelte per la colorazione di ognuna delle prima 5 strisce sono in numero di 10; ma, fissata una di tali scelte, le scelte per la colorazione dell’ultima striscia sono in numero di 9, quindi in totale le possibili colorazioni del tessuto sono in numero di 910

. Nel secondo caso, fissata la colorazione delle prime 5 strisce, vi è una sola scelta per la colorazione della sesta, quindi il risultato è 10

.

2) Caso a): applicando il principio delle scelte multiple si ottiene che tutte le possibili insegne (senza alcuna restrizione sulle lampadine) sono in numero di 6

; da esse si deve sottrarre il numero delle insegne in cui tutte le lampadine hanno stesso colore (che sono 6 in tutto), ottenendo come risposta al quesito il numero 6

-6.

Caso b): applicando il principio delle scelte multiple si ottiene che i casi possibili per le prime 6 lampadine sono 5

; quelli per le ultime 6 lampadine si ottengono scegliendo le 2 posizioni delle gialle (con _



 



 2

6 =15 scelte possibili) e poi i colori delle altre 4 lampadine (con 5

scelte possibili).

La risposta è dunque il prodotto 5

_



 



 2

6 5

=155

.

3) Si può applicare il principio di inclusione-esclusione in forma negativa. Si costruiscono i sottoinsiemi Y, Z di X, contenenti rispettivamente le matrici che soddisfano a),b), e si calcola

X- YZ= X-{Y+Z-YZ}=2

-2

-2

+2

(dove i valori numerici sono ottenuti con il principio delle scelte multiple).

4) Si può applicare il principio delle scelte multiple: le scelte per le immagini dell’elemento 5 sono 2; fissata una di tali scelte, le scelte per le immagini dell’elemento 1 sono 4; fissata una di tali scelte, le scelte per le immagini dell’elemento 2 sono 3; fissata una di tali scelte, le scelte per le immagini dell’elemento 3 sono 2; fissata una di tali scelte, la scelta per le immagini dell’elemento 4 è 1 sola. Le funzioni biunivoche tali che f(5) è pari sono dunque in numero uguale al prodotto di tali numeri, cioè 24321=48.

5) Se 2 vertici sono entrambi pari oppure uno è pari e l’altro dispari, essi sono collegati da uno (e un solo) arco, mentre se sono entrambi dispari essi non sono collegati da nessun arco. Dunque il grafo è connesso perché presi comunque 2 vertici esiste sempre un cammino che li unisce: infatti se sono entrambi pari oppure uno è pari e l’altro dispari, allora esiste un cammino di lunghezza 1 che li unisce; se invece sono entrambi dispari, esiste un cammino di lunghezza 2 che li unisce, passando per un terzo vertice pari. I vertici pari (che sono in numero di 20) devono essere colorati con 20 colori diversi (perché sono tutti adiacenti fra loro) ma per colorare i vertici dispari basta un solo colore (diverso dai 20 usati per i pari): il numero cromatico è dunque 21. Il grado dei vertici pari è 38 (ognuno è estremo di 38 archi che lo collegano a tutti gli altri 38 vertici del grafo); il grado dei vertici dispari è invece 20 (ognuno è estremo di 20 archi che lo collegano ai 20 vertici pari):

essendo pari il grado di tutti i vertici, ed essendo connesso il grafo, per il Teorema di Eulero esiste nel grafo un cammino ciclico Euleriano.

.