Esercitazione di Matematica Discreta (7 dicembre 2011)
1) Sia B l’insieme di tutti i numeri naturali di 5 cifre, con tutte le cifre scelte nell'insieme A={1,2,3,4,5,6,7}. Calcolare quante sono le funzioni f:A→B che hanno la seguente proprietà: per ogni numero pari y∈A l’immagine f(y)∈B è un numero che ha y come seconda cifra.
Soluzione: Si può usare il principio delle scelte multiple. La cardinalità di B è 75, ma gli elementi di B in cui fissiamo la seconda cifra y sono in numero di 74. Per ognuno dei numeri dispari 1,3,5,7 il numero delle immagini possibili è 75 (tutti gli elementi di B); ma per ognuno dei numeri pari 2,4,6 il numero delle immagini possibili è 74. Quindi la risposta al quesito è il prodotto 75757575747474=732.
2) Dimostrare che per ogni numero naturale n il numero (3n3-3n+18)/9 è un numero intero.
Soluzione: Si può usare il principio di induzione. Per n=1 l’affermazione è vera perché il numero (3-3+18)/9 = 2 è intero. Supponendola vera per n=k (quindi supponendo che il numero (3k3-3k+18)/9 è intero) dimostriamola vera per n=k+1, cioè dimostriamo che il numero [3(k+1)3-3(k+1)+18]/9 è intero. Ma facendo i calcoli si ha:
[3(k+1)3-3(k+1)+18]/9 = (3k3+9k2+9k+3-3k-3+18)/9 = [(3k3-3k+18)/9] + k2+k e questo numero è in effetti un intero perché somma di numeri interi.
3) Si consideri il grafo semplice non orientato in cui i vertici sono i numeri interi x tali che -11≤x≤+11, e in cui due vertici distinti x,y sono collegati da un arco se il prodotto xy è ≤0.
Il grafo è connesso ?
Qual è il numero cromatico del grafo ?
Esiste nel grafo un cammino Euleriano (ciclico o non ciclico) ?
Soluzione: Il vertice 0 è adiacente a tutti gli altri vertici, mentre ogni vertice >0 è adiacente ad ogni vertice <0, ma vertici >0 non sono adiacenti fra loro e vertici <0 non sono adiacenti fra loro. Due vertici qualunque x,y sono sempre uniti da un cammino (passando per esempio per il vertice 0) quindi il grafo è connesso. Il numero cromatico è 3: basta colorare tutti i vertici >0 con un colore, tutti i vertici <0 con un secondo colore, e il vertice 0 con un terzo colore. Ogni vertice >0 ha grado 12 e lo stesso vale per ogni vertice <0; il vertice 0 ha grado 22. Poiché ogni vertice ha grado pari, nel grafo esiste un cammino Euleriano ciclico.
4) Si consideri il grafo semplice non orientato in cui i vertici sono i numeri interi x tali che 1≤x≤60, e in cui due vertici distinti x,y sono collegati da un arco se la differenza fra il maggiore e il minore dei numeri x,y è <3.
Il grafo è connesso ?
Qual è il numero cromatico del grafo ?
Esiste nel grafo un cammino Euleriano (ciclico o non ciclico) ?
Soluzione: Poiché ogni vertice x è adiacente al suo successivo x+1, dati 2 vertici distinti qualunque x,y esiste sempre un cammino che li unisce (se x<y basta passare di seguito su x+1, x+2 etc… fino ad arrivare al vertice y; se y<x basta passare di seguito su y+1, y+2 etc… fino ad arrivare al vertice x): il grafo è dunque connesso.
Il numero cromatico non è 2: infatti 2 colori non bastano a colorare il grafo perché per esempio i vertici 1,2,3 (tutti fra loro adiacenti) richiedono 3 colori diversi; ma 3 colori bastano per colorare il grafo: se i colori sono a,b,c basta colorare il vertice 1 con a, il 2 con b, il 3 con c, il 4 con a, il 5 con b, il 6 con c etc…. Quindi il numero cromatico del grafo è 3.
Il vertice 1 è adiacente ai vertici 2,3; il vertice 2 è adiacente ai vertici 1,3,4; tutti i vertici da 3 a 58 sono adiacenti ai 2 vertici che li precedono e ai 2 vertici che li seguono; il vertice 59 è adiacente ai vertici 57,58,60; il vertice 60 è adiacente ai vertici 58,59: tutti i vertici hanno grado pari (2 o 4) tranne i vertici 2 e 59 che hanno grado dispari 3, dunque esiste nel grafo un cammino ciclico Euleriano, per il Teorema di Eulero.
5) Si consideri l’insieme B di tutti i numeri naturali ≤100, ed il prodotto cartesiano A=BxB. Contare il numero di coppie in A che non soddisfano nessuna delle seguenti condizioni: a) il prodotto dei 2 elementi della coppia è dispari; b) il primo numero della coppia è <10.
Soluzione: Si può usare il principio di inclusione-esclusione in forma negativa: se X,Y sono i sottoinsiemi di A formati dalle coppie che soddisfano rispettivamente a),b) si ha:
X∪Y=X+Y-X∩Y=502+9⋅100-5⋅50. La soluzione si ottiene sottraendo tale numero dalla cardinalità di A che è 1002.
