ESERCIZI MATEMATICA DISCRETA (16/01/09) Soluzioni 1) Se X è l’insieme di tutte le matrici con 3 righe e 3 colonne nelle cui caselle sono inseriti valori 0,1, costruiamo i 3 sottoinsiemi: X

(1)

ESERCIZI MATEMATICA DISCRETA (16/01/09) Soluzioni

1) Se X è l’insieme di tutte le matrici con 3 righe e 3 colonne nelle cui caselle sono inseriti valori 0,1, costruiamo i 3 sottoinsiemi: X

1

contenente le matrici con la prima riga avente tutte le caselle contenenti 0; X

2

contenente le matrici con la seconda riga avente tutte le caselle contenenti 0; X

3

contenente le matrici con la terza riga avente tutte le caselle contenenti 0. La risposta al quesito è:

X-X

1

X

2

X

3

.

Si ha poi (applicando opportunamente il principo delle scelte multiple):

X=2

⁹

; X

1

X

2

X

3

=X

1

+X

2

+X

3

-[X

1

X

2

+X

1

X

3

+X

2

X

3

]+X

1

X

2

X

3

=

= 2

⁶

+2

⁶

+2

⁶

-[2

³

+2

³

+2

³

]+1.

Quindi la risposta è 2

⁹

-{2

⁶

+2

⁶

+2

⁶

-[2

³

+2

³

+2

³

]+1}=………

2) Si può applicare il principio di induzione al predicato P(n)=”246………(2n) = n!2

ⁿ

”.

Per n=1 è vero, perché 2=1!2

¹

.

Supponiamo vero P(k)= ”246………(2k) = k!2

^k

” e dimostriamo vero:

P(k+1)= ”246………(2k)(2(k+1)) = (k+1)!2

^k+1

”.

Ma si ha (essendo vero per ipotesi P(k)):

246………(2k)(2(k+1)) = [k!2

^k

][2(k+1)]=[k!(k+1)][22

^k

]=(k+1)!2

^k+1

come si voleva dimostrare.

3) I sottoinsiemi di A che hanno intersezione vuota con B non sono altro che i sottoinsiemi del complementare A-B: poiché il complementare ha cardinalità 3, i suoi sottoinsiemi sono in numero di 2

³

. Dunque, essendo 2

⁹

il numero totale di sottoinsiemi di A, quelli che hanno intersezione non vuota con B sono in numero di 2

⁹

-2

³

.

4) Si può applicare il principio delle scelte multiple. Ogni funzione f dipende dalla scelta delle immagini dei 7 elementi del dominio: le scelte possibili per f(1) sono 4; fissata f(1), le scelte possibili per f(2) sono 3; fissate f(1), f(2) vi è 1 sola scelta possibile per f(3); fissate f(1), f(2), f(3), le scelte possibili per le immagini di ognuno degli elementi 4,5,6,7 sono di nuovo 4 (per ciascun elemento). Il numero delle funzioni f è dunque il prodotto 4

⁵

3.

5) E’ facile verificare che la relazione soddisfa le 3 proprietà:simmetrica, riflessiva e transitiva.

Se QA, la classe di equivalenza [Q] rappresentata da Q contiene tutti i punti XA tali che la

distanza di X da P è uguale alla distanza di Q da P, quindi tale classe geometricamente coincide con

la circonferenza di centro P e raggio PQ.