ESERCIZI MATEMATICA DISCRETA (25/01/11) Soluzioni 1) Si può applicare il principio di inclusione-esclusione in forma positiva. Si costruiscono i 3 insiemi (uno per ognuna delle 3 proprietà): A

(1)

ESERCIZI MATEMATICA DISCRETA (25/01/11) Soluzioni

1) Si può applicare il principio di inclusione-esclusione in forma positiva. Si costruiscono i 3 insiemi (uno per ognuna delle 3 proprietà):

A

1

contenente le matrici che soddisfano la prima proprietà; A

2

contenente le matrici che soddisfano la seconda proprietà; A

3

contenente le matrici che soddisfano la terza proprietà.

La risposta al quesito è:

A

1

A

2

A

3

=A

1

+A

2

+A

3

-[A

1

A

2

+A

1

 A

3

+A

2

A

3

]+A

1

A

2

A

3

 Utilizzando il principio delle scelte multiple si ottengono poi i seguenti valori:

A

1

=2

³

5

⁶

, A

2

=2

³

5

⁶

, A

3

=5

⁷

, A

1

A

2

=2

⁵

5

⁴

, A

1

A

3

=2

³

5

⁴

, A

2

A

3

=2

³

5

⁴

,

A

1

A

2

A

3

=2

⁵

5

²

.

2) Si può applicare il principio di inclusione-esclusione in forma negativa. Si considera l’insieme A di tutti i numeri naturali di 5 cifre, con cifre tutte 0, e si costruiscono i 3 insiemi (uno per ognuna delle 3 proprietà):

A

1

contenente i numeri che soddisfano la prima proprietà; A

2

contenente i numeri che soddisfano la seconda proprietà; A

3

contenente i numeri che soddisfano la terza proprietà.

La risposta al quesito è:

A-A

1

A

2

A

3

=A-{A

1

+A

2

+A

3

-[A

1

A

2

+A

1

A

3

+A

2

A

3

]+A

1

A

2

A

3

}

Utilizzando il principio delle scelte multiple ( tenendo conto che i numeri di A

1

hanno come ultima cifra un dispari, mentre quelli di A

3

hanno come prima cifra 1 oppure 2) si ottengono poi i seguenti valori:

A=9, A

1

=5

^

9

⁴

, A

2

=9, A

3

=2

^

9

⁴

, A

1

A

2

=5, A

1

A

3

=5

^

2

^

9

³

, A

2

A

3

=2,

A

1

A

2

A

3

=1.

3) In pratica si tratta di calcolare il numero delle matrici che non soddisfano nessuna delle 2 proprietà:

- la prima e seconda riga contengono in tutte le loro caselle lo 0 - la seconda e terza riga contengono in tutte le loro caselle lo 0

quindi si può applicare il principio di inclusione-esclusione in forma negativa. Si considera l’insieme A di tutte le matrici con 3 righe e 3 colonne nelle cui caselle si possono inserire i numeri 0,1,2, e si costruiscono i 2 insiemi (uno per ognuna delle 2 proprietà):

A

1

contenente le matrici che soddisfano la prima proprietà; A

2

contenente le matrici che soddisfano la seconda proprietà.

La risposta al quesito è:

A-A

1

A

2

=A-{A

1

+A

2

-A

1

A

2

}

Utilizzando il principio delle scelte multiple si ottengono poi i seguenti valori:

A=3

⁹

, A

1

=3

³

,A

2

=3

³

, A

1

A

2

=1.

4) Calcolare il numero dei numeri naturali di 3 cifre, con cifre tutte 0, in cui almeno 2 cifre sono uguali.

In pratica si tratta di calcolare il numero dei numeri naturali di 3 cifre, con cifre tutte 0, che non soddisfano nessuna delle 2 proprietà:

- la prima e seconda cifra sono uguali - la prima e terza cifra sono uguali - la seconda e terza cifra sono uguali

quindi si può applicare il principio di inclusione-esclusione in forma positiva e si costruiscono i 3 insiemi (uno per ognuna delle 3 proprietà):

A

1

contenente i numeri che soddisfano la prima proprietà; A

2

contenente i numeri che soddisfano la seconda proprietà; A

3

contenente i numeri che soddisfano la terza proprietà.

La risposta al quesito è:

A

1

A

2

A

3

=A

1

+A

2

+A

3

-[A

1

A

2

+A

1

 A

3

+A

2

A

3

]+A

1

A

2

A

3

 Utilizzando il principio delle scelte multiple si ottengono poi i seguenti valori:

A

1

=9

²

, A

2

=9

²

, A

3

=9

²

, A

1

A

2

=9, A

1

A

3

=9, A

2

A

3

=9, A

1

A

2

A

3

=9 .