Esercitazione di Matematica Discreta (17 gennaio 2012)
Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento
1) Calcolare quante diverse matrici 6x6 a valori nell’insieme {0,1,2,3} si possono costruire con la condizione che ognuna contenga esattamente 8 valori =0 ed esattamente 4 valori uguali a 2.
Soluzione: Principio delle scelte multiple: si devono scegliere 8 caselle in cui inserire
il valore 0 fra 36 caselle possibili (
8 36
possibili scelte); fissata tale scelta si devono
scegliere 4 caselle in cui inserire il valore 2 fra 28 caselle possibili (
4 28
possibili
scelte); fissata tale scelta, le restanti 24 caselle si devono riempire con valori 1 o 3 (224 possibili scelte). La soluzione è il prodotto di questi 3 numeri.
2) Dato A={1,2,3,4,5,6,7}, contare il numero delle funzioni f: A A tali che f(5) è pari, e fra queste contare quelle surgettive.
Soluzione: Principio delle scelte multiple: la scelta di f(5) si può effettuare in 3 modi possibili, la scelta di f(1),f(2),f(3),f(4),f(6),f(7) in 7 modi (per ciascuna immagine), dunque la prima risposta è il prodotto 376. Nel caso in questione una funzione è surgettiva se e solo se è iniettiva: per contare le iniettive si usa come sopra il proncipio delle scelte multiple, ottenendo il prodotto 3654321 (ad ogni passo il numero delle scelte per le immagini diminuisce).
3) Si consideri il grafo semplice non orientato in cui i vertici sono i numeri naturali di 6 cifre (in base 10) con cifre scelte fra 2,4,7, e in cui due vertici distinti x,y sono adiacenti (cioè collegati da un arco) se differiscono per un multiplo di 10. Quante componenti connesse ha il grafo ? Qual è il suo numero cromatico ? Esiste in qualche componente (considerata come grafo a sé stante) un cammino Euleriano ?
Soluzione: Due vertici distinti x,y sono adiacenti se hanno la stessa ultima cifra, quindi vi sono 3 componenti connesse, una per ogni possibilità dell’ultima cifra. In ogni componente tutti i vertici sono adiacenti fra loro quindi il numero cromatico di ogni componente coincide con il numero dei vertici (che è 35) e questo è anche il numero cromatico del grafo. In ogni componente ogni vertice è adiacente a tutti gli
altri, quindi ha grado 35-1 (pari) cioè esiste in ogni componente un cammino Euleriano (ciclico).
4) Svolgere l’Esercizio 3 ma con la regola di adiacenza espressa da: due vertici distinti x,y sono adiacenti (cioè collegati da un arco) se hanno l’ultima cifra differente.
Soluzione: Dati 2 vertici distinti x,y essi sono collegati da un arco (se hanno l’ultima cifra differente) o da un cammino di lunghezza 2 (se hanno l’ultima cifra uguale) quindi il grafo è connesso ed ha 1 componente connessa. Il numero cromatico è 3:
basta colorare con lo stesso colore i vertici che hanno la stessa ultima cifra. Ogni vertice è adiacente a quelli che hanno l’ultima cifra differente dalla sua, quindi ha grado 235 (pari): nel grafo (unica componente connessa) esiste un cammino Euleriano (ciclico).
5) Dimostrare che, per ogni naturale n, la somma di tutti i numeri naturali consecutivi da 3 ad n+3 (inclusi) coincide con il numero il numero (n2+7n+6)/2.
Soluzione: Si può usare il principio di induzione. Per n=1 si deve verificare che è vera l’affermazione “la somma di tutti i numeri naturali consecutivi da 3 ad 1+3 (inclusi) coincide con il numero il numero (12+7+6)/2”: in effetti 3+4=7=(12+7+6)/2.
Supponendo vera l’affermazione per n=k, dimostriamola vera per n=k+1, cioè dimostriamo che “la somma di tutti i numeri naturali consecutivi da 3 ad (k+1)+3 (inclusi) coincide con il numero il numero ((k+1)2+7(k+1)+6)/2”. In effetti la somma di tutti i numeri naturali consecutivi da 3 ad (k+1)+3 si ottiene sommando la somma di tutti i numeri naturali consecutivi da 3 ad k+3 (che per ipotesi è (k2+7k+6)/2) con l’ulteriore numero k+4: con facili calcoli algebrici si ottiene appunto ((k+1)2+7(k+1)+6)/2, come si voleva.
6) Dato l’insieme A={1,2,3,4,5,6,7,8,9} e i sottoinsiemi B={1,2,3,4}, C={3,4,5,6,7}, D={1,3,4,6,7,8}, calcolare il numero di funzioni f: A A tali che almeno 2 fra B,C,D abbiano gli elementi della loro intersezione che hanno immagini tutte pari.
Soluzione: Si può usare il principio di inclusione-esclusione in forma positiva.
Essendo BC={3,4}, BD={1,3,4}, CD={3,4,6,7}, basta costruire i 3 insiemi X,Y,Z seguenti:
X={funzioni f tali che f(3),f(4) sono pari}
Y={funzioni f tali che f(1),f(3),f(4) sono pari}
Z={funzioni f tali che f(3),f(4),f(6),f(7) sono pari}
e calcolare la cardinalità dell’unione BCD con la formula:
BCD=B+C+D-{BC+BD+ CD}+BCD=
=4297+4396+4495-{4396+4495+4594}+4594=4297
(dove i valori numerici si ottengono dal principio delle scelte multiple).
7) Calcolare il numero delle matrici booleane con 3 righe e 4 colonne tali che nella prima colonna non vi sono due caselle adiacenti contenenti entrambe il valore 0.
Soluzione: Si può usare il principio inclusione-esclusione in forma negativa. Se A è l’insieme delle matrici booleane 3x4, e se X,Y sono rispettivamente i sottoinsiemi di A formati dalle matrici in cui la 1a e la 2a casella, la 2a e la 3a casella della prima colonna contengono entrambe il valore 0, si calcola
A-XY, con A=212,XY=X+Y-XY=210+210-29
(dove i valori numerici si ottengono dal principio delle scelte multiple).
8) Si consideri il grafo semplice non orientato, in cui i vertici sono tutti i numeri naturali di 8 cifre (in base 10) con cifre scelte fra 1,2,4,5,7 e in cui due vertici distinti x,y sono collegati da un arco se la seconda cifra di x e la seconda cifra di y differiscono di 3 unità. Calcolare il numero di componenti connesse del grafo, e il numero di vertici di ogni componente. Calcolare il numero cromatico del grafo. In ogni componente connessa (considerata come grafo a sé stante) dire se esiste un cammino Euleriano ciclico o non ciclico.
Soluzione: Ogni vertice con la seconda cifra 1 è adiacente ad ogni vertice con la seconda cifra 4 che a sua volta è adiacente ad ogni vertice con la seconda cifra 7; ogni vertice con la seconda cifra 2 è adiacente ad ogni vertice con la seconda cifra 5. Vi sono dunque 2 componenti connesse, la prima componente contenente i vertici con la seconda cifra 1 o 4 o 7 (57+57+57 vertici), la seconda componente contenente i vertici con la seconda cifra 2 o 5 (57+57 vertici).
La seconda componente ha numero cromatico 2 (un colore per i vertici con la seconda cifra 2 e un altro per quelli con la seconda cifra 5). Anche la prima componente ha numero cromatico 2 (un colore per i vertici con la seconda cifra 1 o 7 e un altro per quelli con la seconda cifra 4). Dunque il numero cromatico del grafo è 2.
Nella prima componente ogni vertice con la seconda cifra 4 ha grado 57+57 (pari), ma ogni vertice con la seconda cifra 1 o 7 ha grado 57 (dispari). Nelle seconda componente ogni vertice ha grado 57 (dispari). Dunque in nessuna componente esiste un cammino Euleriano (né ciclico né non ciclico), perché vi sono più di 2 vertici di grado dispari.
9) Sia dato un grafo non orientato con un numero 10 di vertici, e in cui ogni vertice ha grado 5. Se fissiamo un vertice v, quanti cammini diversi di lunghezza 6 e con vertice iniziale v esistono nel grafo ? Quanti cammini diversi di lunghezza 6 esistono in tutto nel grafo ?
Soluzione: Partendo dal vertice v, la scelta del primo arco da percorrere nel cammino si può effettuare in 5 modi diversi (perché v ha grado 5); fissata tale scelta e percorso il primo arco, si arriva su un secondo vertice w, e la scelta del secondo arco da percorrere nel cammino si può effettuare di nuovo in 5 modi diversi (perché w ha grado 5). Così procedendo, essendo 6 gli archi da percorrere, per il principio delle scelte multiple si ottengono in tutto 56 cammini diversi di lunghezza 6 e con vertice iniziale v. Se consideriamo tutti i cammini di lunghezza 6 nel grafo, la scelta del vertice iniziale si può effettuare in 10 modi diversi, e, fissata tale scelta per il vertice inziale, abbiamo già dimostrato che il numero di cammini è 56: per il principio delle scelte multiple il numero di cammini diversi di lunghezza 6 nel grafo è il prodotto 1056.
