Esercitazione del 2 novembre 2011

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 a1,a2A tali che f(a1)=f(a2), da cui g(f(a1))=g(f(a2)) ossia (gf )(a1)=(gf)(a2), 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 4a e 6a cifra sono dispari, la 5° e 7a cifra sono uguali fra loro. Soluzione: Si può applicare il principio delle scelte multiple. Ognuno dei numeri considerati dipende da 7 variabili: x1=valore della 1a cifra, x2=valore della 2a cifra etc…, x7=valore della 7a cifra. Il numero di valori possibili di x1 è 4 (le 4 cifre pari 2,4,6,8); fissato un valore di x1, il numero di valori possibili di x2 è 3 (le 4 cifre pari 2,4,6,8 tranne quella scelta per x1); fissato un valore di x1,x2 il numero di valori possibili di x3 è 2 (le 4 cifre pari tranne quelle scelte per x1,x2); fissato un valore di x1,x2,x3 il numero di valori possibili di x4 è 5 (le 5 cifre dispari 1,3,5,7,9); fissato un valore di x1,x2,x3,x4 il numero di valori possibili di x5 è 9 (le 9 cifre 1,2,3,4,5,6,7,8,9); fissato un valore di x1,x2,x3,x4,x5 il numero di valori possibili di x6 è 5 (le 5 cifre dispari 1,3,5,7,9); fissato un valore di x1,x2,x3,x4,x5,x6 il numero di valori possibili di x7 è 1 (lo stesso valore scelto per x5). 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: x1=valore di f(1), x2=valore di f(2) etc…, x6=valore di f(6). Il numero di valori possibili di x1 è 3 (i 3 valori pari 2,4,6); fissato un valore di x1, il numero di valori possibili di x2 è 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: x1=scelta delle 2 posizioni in cui inserire le vocali, x2=valore della vocale da inserire nella 1a di queste 2 posizioni; x3=valore della vocale da inserire nella 2a di queste 2 posizioni; x4=valore della consonante da inserire nella 1a delle 2 posizioni restanti; x5=valore della consonante da inserire nella 2a delle 2 posizioni restanti. Il numero di valori possibili di x1 è 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 x1, il numero di valori possibili di x2 è 2 (le 2 vocali a,e); fissato un valore di x1,x2 il numero di valori possibili di x3 è 2 (le 2 vocali a,e); fissato un valore di x 1,x2,x3 il numero di valori possibili di x4 è 3 (le 3 consonanti b,c,d); fissato un valore di x1,x2,x3,x4 il numero di valori possibili di x5 è 3 (le 3 consonanti b,c,d). La risposta al quesito è il prodotto dei numeri trovati: 62233=216.

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, 5a, 6a estrazione la pallina estratta è rimessa nell’urna. Soluzione: Si può applicare il principio delle scelte multiple. Ognuno dei numeri considerati dipende da 6 variabili: x1=valore della 1a cifra, x2=valore della 2a cifra etc…, x6=valore della 6a cifra. Il numero di valori possibili di x1 è 4 (le 8 cifre 1,2,3,4,5,6,7,8); fissato un valore di x1, il numero di valori possibili di x2 è 7 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quella scelta per x1); fissato un valore di x1,x2 il numero di valori possibili di x3 è 6 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x1,x2); fissato un valore di x1,x2,x3 il numero di valori possibili di x4 è 5 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x1,x2,x3); fissato un valore di x1,x2,x3,x4 il numero di valori possibili di x5 è 5 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x1,x2,x3); fissato un valore di x1,x2,x3,x4,x5 il numero di valori possibili di x6 è 5 (le 8 cifre 1,2,3,4,5,6,7,8 tranne quelle scelte per x1,x2,x3). La risposta al quesito è il prodotto dei numeri trovati: 876555.