ESERCITAZIONE MATEMATICA DISCRETA

(1)

ESERCITAZIONE MATEMATICA DISCRETA (02/09/11)

1)a)Date le funzioni f: A  B, g: B  C, dimostrare che se la composizione gf : A  C è una funzione iniettiva allora f è iniettiva (suggerimento: ragionare per assurdo).

b)Se A={1,2}, B={3,4,5}, C={6,7} costruire un esempio concreto di funzioni f: A  B, g: B  C tali che la composizione gf : A  C sia una funzione iniettiva ma g non sia iniettiva.

Soluzione: a) per assurdo supponiamo gf iniettiva ma f non iniettiva. Allora esistono 2 elementi diversi a

1

,a

2

A tali che f(a

1

)=f(a

2

), da cui g(f(a

1

))=g(f(a

2

)) ossia (gf )(a

1

)=(gf)(a

2

), contraddizione perché gf è iniettiva.

b) Definendo per esempio f(1)=3,f(2)=4,g(3)=6,g(4)=7,g(5)=7, si ha g non iniettiva ma gf iniettiva perché (gf)(1), (gf)(2)=7.

2) Calcolare quanti sono i numeri naturali di 7 cifre (con cifre tutte diverse da 0) tali che le prime 3 cifre sono pari e tutte diverse fra loro, la 4

^a

e 6

^a

cifra sono dispari, la 5° e 7

^a

cifra sono uguali fra loro.

Soluzione: Si può applicare il principio delle scelte multiple. Ognuno dei numeri considerati dipende da 7 variabili: x

1

=valore della 1

^a

cifra, x

2

=valore della 2

^a

cifra etc…, x

7

=valore della 7

^a

cifra. Il numero di valori possibili di x

1

è 4 (le 4 cifre pari 2,4,6,8); fissato un valore di x

1

, il numero di valori possibili di x

2

è 3 (le 4 cifre pari 2,4,6,8 tranne quella scelta per x

1

); fissato un valore di x

1

,x

2

il numero di valori possibili di x

3

è 2 (le 4 cifre pari tranne quelle scelte per x

1

,x

2

); fissato un valore di x

1

,x

2

,x

3

il numero di valori possibili di x

4

è 5 (le 5 cifre dispari 1,3,5,7,9); fissato un valore di x

1

,x

2

,x

3

,x

4

il numero di valori possibili di x

5

è 9 (le 9 cifre 1,2,3,4,5,6,7,8,9); fissato un valore di x

1

,x

2

,x

3

,x

4

,x

5

il numero di valori possibili di x

6

è 5 (le 5 cifre dispari 1,3,5,7,9); fissato un valore di x

1

,x

2

,x

3

,x

4,

x

5

,x

6

il numero di valori possibili di x

7

è 1 (lo stesso valore scelto per x

5

).

La risposta al quesito è il prodotto dei numeri trovati: 4325951=5400.

3) Se A={1,2,3,4,5,6}, calcolare il numero di funzioni f: A  A tali che tutti i numeri dispari hanno come corrispondenti dei numeri pari.

Soluzione: Si può applicare il principio delle scelte multiple. Ognuna delle funzioni considerate dipende da 6 variabili: x

1

=valore di f(1), x

2

=valore di f(2) etc…, x

6

=valore di f(6). Il numero di valori possibili di x

1

è 3 (i 3 valori pari 2,4,6); fissato un valore di x

1

, il numero di valori possibili di x

2

è 6 (i 6 valori 1,2,3,4,5,6); etc.. (si procede come nell’esercizio precedente).

La risposta al quesito è il prodotto dei numeri trovati: 363636=5832.

4) Calcolare il numero di parole di lunghezza 4 sull’alfabeto {a,b,c,d,e} in cui esattamente 2 delle lettere sono vocali. (suggerimento: la prima delle variabili da cui dipende la parola è la scelta delle 2 posizioni in cui inserire le vocali).

Soluzione: Si può applicare il principio delle scelte multiple. Ognuna delle parole considerati dipende da 5 variabili: x

1

=scelta delle 2 posizioni in cui inserire le vocali, x

2

=valore della vocale da inserire nella 1

^a

di queste 2 posizioni; x

3

=valore della vocale da inserire nella 2

^a

di queste 2 posizioni; x

4

=valore della consonante da inserire nella 1

^a

delle 2 posizioni restanti; x

5

=valore della consonante da inserire nella 2

^a

delle 2 posizioni restanti. Il numero di valori possibili di x

1

è il coefficiente binomiale (4 2)=(43)/(2!)=6 (sono le combinazioni semplici di 4 posizioni prese a 2 a 2); fissato un valore di x

1

, il numero di valori possibili di x

2

è 2 (le 2 vocali a,e); fissato un valore di x

1

,x

2

il numero di valori possibili di x

3

è 2 (le 2 vocali a,e); fissato un valore di x

1

,x

2

,x

3

il numero di valori possibili di x

4

è 3 (le 3 consonanti b,c,d); fissato un valore di x

1

,x

2

,x

3

,x

4

il numero di valori possibili di x

5

è 3 (le 3 consonanti b,c,d).

La risposta al quesito è il prodotto dei numeri trovati: 62233=216.

(2)

5) In un’urna vi sono 8 palline numerate da 1 a 8 (ogni pallina è numerata diversamente dalle altre).

Si estraggono 6 palline e si scrivono consecutivamente le cifre delle palline, formando alla fine un numero naturale di 6 cifre. Calcolare quanti numeri diversi si possono ottenere se nelle prime 3 estrazioni, le palline estratte non sono rimesse nell’urna e vengono eliminate, ma nella 4

^a

, 5

^a

, 6

^a

estrazione la pallina estratta è rimessa nell’urna.

Soluzione: Si può applicare il principio delle scelte multiple. Ognuno dei numeri considerati dipende da 6 variabili: x

1

=valore della 1

^a

cifra, x

2

=valore della 2

^a

cifra etc…, x

6

=valore della 6

^a

cifra. Il numero di valori possibili di x

1

è 4 (le 8 cifre 1,2,3,4,5,6,7,8); fissato un valore di x

1

, il numero di valori possibili di x

2

è 7 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quella scelta per x

1

); fissato un valore di x

1

,x

2

il numero di valori possibili di x

3

è 6 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x

1

,x

2

); fissato un valore di x

1

,x

2

,x

3

il numero di valori possibili di x

4

è 5 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x

1

,x

2

,x

3

); fissato un valore di x

1

,x

2

,x

3

,x

4

il numero di valori possibili di x

5

è 5 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x

1

,x

2

,x

3

); fissato un valore di x

1

,x

2

,x

3

,x

4,

x

5

il numero di valori possibili di x

6

è 5 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x

1

,x

2

,x

3