Matematica Discreta
Compitino Modulo I - BBBBBB 14 Gennaio 2013
Nome e Cognome:
Numero Matricola:
Giustificare ogni risposta.
Esercizio 1
Siano A = {a, b, c, d, e} e B = {1, 2, 3, 4, 5} insiemi. Determinare quante sono (i) le funzioni iniettive f : B → A tali che f (2) = a e f (3) = b;
(ii) le funzioni surgettivi f : B → A;
(iii) le funzioni f : B → A per cui f (1) = f (2) = e.
Soluzione
(i) Gli elementi 1, 4 e 5 sono gli elementi su cui la funzione f non e’ ancora definita. Quante possibilit`a abbiamo per f (1)? Se vogliamo che la funzione resti iniettiva, abbiamo soltanto tre possibilit`a per f (1), due per f (4) ed infine una per f (5). In totale 3! = 6 possibilit`a.
(ii) I due insiemi finiti A e B hanno la stessa cardinalit`a. Quindi una funzione da B in A e’ surgettiva se, e solo se, e’
bigettiva. Il numero di funzioni bigettive e’ uguale al numero di permutazioni di un insieme di 5 elementi, cioe’ 5!.
(iii) Gli elementi 3, 4 e 5 sono gli elementi su cui la funzione f non e’ ancora definita. Quante possibilit`a abbiamo per f (3)? Abbiamo 5 possibilit`a per f (3), 5 per f (4) ed infine 5 per f (5). In totale 53 possibilit`a.
Esercizio 2
(i) Si vuole costituire un comitato di 3 membri scelti tra 8 persone. Quanti differenti comitati si possono formare?
(ii) Si svolge una gara podistica alle olimpiadi. Quanti possibili podi si possono avere se i partecipanti alla gara sono 5?
(iii) Un’urna contiene 10 palline numerate da 1 a 10. Si eseguono 4 estrazioni. Determinare quanti sono i risultati che si possono ottenere come risultato delle 4 estrazioni supponendo di NON rimettere, dopo ogni estrazione, la pallina nell’urna e non considerando l’ordine di estrazione.
Soluzione
(i) E’ pari al numero di sottoinsiemi di cardinalit`a tre di un insieme di otto elementi. Cioe’, il coefficiente binomiale (8 su 3).
(ii) E’ pari alle stringhe di lunghezza tre senza ripetizioni: 5 × 4 × 3.
(iii) E’ pari al numero di sottoinsiemi di cardinalit`a 4 di un insieme di 10 elementi: il coefficiente binomiale (10 su 4).
Esercizio 3
Si determini qual’e’ il resto della divisione di (144)78 per 7.
Soluzione
7 e’ un numero primo. Quindi vale il teorema di Fermat: 1446 ≡ 1 modulo 7. Allora (144)78 = (144)6×13 = ((144)6)13≡ 1 modulo 11.
Esercizio 4
Si determino x e y, se esistono, tali che 8x + 47y = 1. Perche’ non esistono x e y tali che 27x + 42y = 1?
Soluzione
8 e 47 sono primi tra di loro, quindi x e y esistono: 8 × 6 + 47 × (−1) = 1. I numeri 27 e 42 non sono primi tra loro.
Se esistessero x e y tali che 27x + 42y = 1 allora il divisore comune 3 dovrebbe dividere 1, che e’ impossibile.
Esercizio 5
Si provi per induzione chePn
k=1(2k − 1) = n2.
Soluzione
Base induzione: n = 1. Allora si ha: 12= 1 =P1
k=1(2k − 1) = (2 × 1) − 1. Supponiamo per ipotesi d’induzione che l’uguaglianza sia vera per n e dimostriamola per n + 1.
n+1
X
k=1
(2k − 1) = (
n
X
k=1
(2k − 1)) + 2(n + 1) − 1 = n2+ 2n + 1 = (n + 1)2.
