ESERCIZI MATEMATICA DISCRETA I (13/11/09) Soluzioni
1) La funzione f è iniettiva perché se per assurdo esistessero 2 elementi a,bN, con ab, tali che f(a)=f(b), si avrebbe (a,2)=(b,2) da cui a=b (contraddizione). La funzione f non è surgettiva perché le coppie del codominio NxN con il secondo elemento 2 non sono corrispondenti di nessun elemento del dominio N .
2) Ognuno dei numeri naturali da contare dipende da 4 variabili: x1,x2,x3,x4 (rispettivamente il valore della prima, della seconda, della terza e delle quarta cifra). La x1 ha 9 valori possibili; fissato un valore per x1, la x2 ha 9 valori possibili; fissato un valore per x1 e x2, la x3 ha 1 valore possibile;
fissato un valore per x1, per x2 e per x3, la x4 ha 8 valori possibili. Per il principio delle scelte multiple la risposta al quesito è il prodotto 9918 = 648 .
3) Ognuno dei numeri naturali da contare dipende da 4 variabili:
x1= la posizione della cifra 5;
x2,x3,x4 = rispettivamente i valori delle rimanenti 3 cifre.
La x1 ha 4 valori possibili; fissato un valore per x1, la x2 ha 5 valori possibili; fissato un valore per x1
e x2, la x3 ha 5 valori possibili; fissato un valore per x1, per x2 e per x3, la x4 ha 5 valori possibili. Per il principio delle scelte multiple la risposta al quesito è il prodotto 4555 = 500 .
4) Si deve dimostrare che il seguente predicato:
P(n) = “n2+n è pari” (dove la variabile n assume valori in N) é vero per ogni valore di n.
Per il principio di induzione basta dimostrare che 1) P(1) è vero
2) P(k) vero P(k+1) vero Ma P(1) è vero perché 12+1 è pari.
Se supponiamo vero P(k) = “k2+k è pari”, dimostriamo vero P(k+1) = “(k+1)2+(k+1) è pari”. Ma si ha:
(k+1)2+(k+1) = (k2+2k+1)+(k+1) = (k2+k)+2(k+1)
e poiché k2+k è pari per ipotesi, e 2(k+1) è pari perché multiplo di 2, anche la loro somma è pari, dunque P(k+1) è vero.
5) Ragioniamo come sopra, applicando il Principio di induzione al seguente predicato:
P(n) = “21+22+……+2n = 2n+1-2” (dove la variabile n assume valori in N)
Ma P(1) è vero perché la somma a primo membro vale 21 mentre il secondo membro vale 22-2.
Supposto vero P(k) = “21+22+……+2k = 2k+1-2”, dimostriamo vero P(k+1) = “21+22+……+2k+1= 2k+2-2”. Ma si ha:
21+22+……+2k+1 = (21+22+……+2k)+2k+1 = (2k+1-2)+2k+1 = (22k+1)-2 = 2k+2-2 dunque P(k+1) è vero.
6) Se a = (rnrn-1rn-2……r2r1r0)3 è la rappresentazione di a in base 3 (dove le cifre possono assumere i valori 0,1,2), il valore numerico di a è a=rn3n+rn-13n-1+…..+r232+r13+r0 e si tratta di stabilire quando tale valore è pari. Le cifre uguali a 0 non hanno influenza sul ragionamento, quindi possiamo ragionare sulle cifre di valore =1 e =2. Le cifre =2 rendono pari il corrispondente addendo, quindi affinché l’intera somma sia pari si deve imporre che gli addendi con cifre =1 diano somma pari. Ma gli addendi con cifra =1 sono potenze di base 3, quindi sono dispari, e affinché la loro somma sia pari, il numero di tali addendi deve essere pari (in modo che sommati a coppie diano numeri pari).
Concludendo: affinché il numero a rappresentato in base b=3 sia pari occorre che le cifre =1 siano in numero pari.
