ESERCIZI MATEMATICA DISCRETA (18/01/10) 1)

ESERCIZI MATEMATICA DISCRETA (18/01/10)

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 , la luce di 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.)

6) Dato l'insieme A={1,2,3,4,5,6,7,8,9,10}, e i suoi sottoinsiemi B= {7,8,9,10}, C=

{1,2,3,7,8}, D={3,5,10}, calcolare il numero dei sottoinsiemi di A che hanno intersezione vuota con almeno uno dei sottoinsiemi B,C,D. (6 p.)

7) Dimostrare che per ogni numero naturale n il numero n

+4n è multiplo di 5. (4 p.) 8) Dati gli insiemi A = {1,2,3,4,5,6,7}, B = {7,8,9,10,11,12}, calcolare il numero delle funzioni f: A  B tali che l’immagine di ogni numero dispari sia pari; calcolare poi, tra queste funzioni, il numero di quelle iniettive (5 p.)

9) Si consideri il grafo semplice non orientato, in cui i vertici sono i numeri naturali x tali che 1x30 e in cui due vertici distinti x,y sono uniti da un arco se (rappresentati come punti su una retta orientata) la loro distanza è =3.

Quante componenti connesse ha il grafo ? (3 p.) Qual è il numero cromatico del grafo ? (3 p.)

In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino

Euleriano (ciclico o non ciclico) ? (3 p.)

10) Sia dato l'insieme A={1,2,3,4,5,6,7,8,9,10,11,12} e il suo sottoinsieme

B={1,2,3,4,5,6}. Contare quanti sono i sottoinsiemi C di A tali che la cardinalità di

BC sia uguale a 3 (sugg. per costruire ognuno dei sottoinsiemi C, si deve scegliere

un sottoinsieme di B di cardinalità 3 e ...) (6 p.)