ESERCIZI MATEMATICA DISCRETA (30/01/09)
1) Sia A l'insieme di tutte le matrici 4x4 con elementi in {-3,-2,-1,0,1,2,3}. Definiamo
"matrici di tipo 1" quelle in cui tutti gli elementi della prima riga sono 0, e "matrici di tipo 2" quelle in cui tutti gli elementi della prima riga sono 0.
Calcolare il numero delle matrici di A che non sono contemporaneamente nè di tipo 1 nè di tipo 2 (6 p.)
2) Si consideri il grafo semplice non orientato in cui i vertici sono tutte le parole sull'alfabeto {x,y,z,t} di lunghezza compresa fra 1 e 5 (inclusi), e in cui due vertici distinti x,y sono adiacenti se la somma delle lunghezza delle parole x e y è 6.
a) Calcolare quante componenti connesse ha il grafo, e indicare il numero di vertici di ogni componente. (3 p.)
b) Qual è il numero cromatico del grafo ? (3 p.)
c) In ogni componente connessa (considerata come grafo a sé stante), esiste un cammino Euleriano ? (4 p.)
3) Si consideri un'insegna luminosa con 20 lampadine , ognuna delle quali può assumere uno dei seguenti colori: giallo, rosso, verde, blu. Quante diverse configurazioni può assumere l'insegna se si pretende che esattamente 5 lampadine restino spente ? (5 p.)
4) Sia A l'insieme delle matrici 3x3 ad elementi nell'insieme {1,2,3,4}. Calcolare quante sono le matrici in A in cui almeno due righe hanno elementi tutti pari (5 p.) 5) Dimostrare che, per ogni numero naturale n, la somma dei primi (n+3) numeri naturali pari è uguale a (n+3)(n+4) (4 p.)
