Matematica Discreta
Compitino Modulo I AAAAAAA 9 Gennaio 2013
Nome e Cognome:
Numero Matricola:
Giustificare ogni risposta.
Esercizio 1
Si consideri la seguente relazione binaria R sull’insieme degli studenti del corso di laurea in informatica: xRy se, e solamente se, x e y hanno la stessa et`a e x ha superato un numero di esami strettamente inferiore al numero di esami superati da y. Quali propriet`a verifica la relazione R?
Soluzione
Per semplificare i ragionamenti indichiamo con Et(x) l’et`a dello studente x e con N e(x) il numero di esami superati da x.
1. La relazione binaria R verifica la propriet`a riflessiva se e solo se xRx per ogni studente x del corso di laurea in informatica. Troviamo un controesempio alla propriet`a riflessiva. Sia Pinco uno studente di informatica.
Allora Pinco ha banalmente la stessa et`a di Pinco, ma il numero di esami superati N e(P inco) non pu`o essere strettamente inferiore (`e uguale!) al numero di esami superati da LUI stesso.
2. Propriet`a Simmetrica: ∀xy(xRy → yRx). La propriet`a simmetrica non vale. Ecco un controesempi o. Siano Pinco e Pallino due studenti tali che Pinco R Pallino. Da quest’ultima condizione segue che Et(P inco) = Et(P allino) e N e(P inco) < N e(P allino). Se valesse la condizione inversa Pallino R Pinco, allora N e(P allino) <
N e(P inco), che `e impossibile.
3. Propriet`a Transitiva: ∀xyz(xRy ∧ yRz → xRz). La propriet`a transitiva vale. Dobbiamo quindi fare un ra- gionamento generale. Siano x, y, z tre studenti tali che xRy e yRz. Allora Et(x) = Et(y) e Et(y) = Et(z), da cui segue Et(x) = Et(z), cio`e x e z hanno la stessa et`a. Inoltre sempre dall’ipotesi xRy e yRz segue che N e(x) < N e(y) e N e(y) < N e(z). Per la propriet`a transitiva dell’ordinamento < sui numeri naturali si ha che N e(x) < N e(z). In conclusione, Et(x) = Et(z) e N e(x) < N e(z), cio`e xRz.
4. Propriet`a antisimmetrica: ∀xy(xRy ∧ yRx → x = y). La propriet`a antisimmetrica vale. Proveremo che la premessa dell’implicazione `e sempre falsa comunque scegliamo x e y tra gli studenti. Infatti, se x, y sono due studenti tali che xRy e yRx, allora Et(x) = Et(y), N e(x) < N e(y) e N e(y) < N e(x). Queste due ultime condizioni sono impossibili tra di loro. Non esistono due numeri naturali n, k tali che n < k e k < n.
Un’implicazione con premessa falsa `e vera. Basta controllare la tavola di verit`a dell’implicazione,
Esercizio 2
In quanti modi si possono lanciare 10 palline distinguibili in 4 contenitori distinti?
Soluzione
Le dieci palline sono distinguibili, quindi possiamo supporre che siano numerate da 1 a 10. Ciascuna pallina ha quattro possibilit`a. Quindi in totale abbiamo 410 possibilit`a per il principio moltiplicativo.
Esercizio 3
Dimostrare per induzione che la somma dei primi n numeri dispari `e n2.
Soluzione
Un numero x `e dispari se e solo se esiste un numero naturale k tale che y = 2k + 1. Quindi, per considerare i primi n numeri dispari, bisogna far variare l’indice k nel termine 2k + 1 nell’intervallo [0, n − 1]. Dobbiamo quindi provare che
X
0≤k≤n−1
(2k + 1) = n2.
Caso base: n = 1: Allora 1 = 12. Vero.
Supponiamo per ipotesi d’induzione che la somma dei primi n numeri dispari sia uguale ad n2, cio`eP
0≤k≤n−1(2k+1) = n2. Allora dimostriamo la stessa relazione per la somma dei primi n + 1 numeri dispari:
X
0≤k≤n
(2k + 1) = X
0≤k≤n−1
(2k + 1) + (2n + 1) = n2+ 2n + 1 = (n + 1)2.
Esercizio 4
Si calcolino tutte le soluzioni del seguente sistema di equazioni lineari:
1 2 2 2 5 3 3 8 4
x y z
=
1 2 3
Soluzione
Consideriamo la matrice estesa A:
1 2 2 1
2 5 3 2
3 8 4 3
Il nostro primo scopo `e di ottenere a partire da A una matrice B in cui B21= B31= 0. Sottraiamo alla seconda riga di A la prima riga moltiplicata per due. Otteniamo:
1 2 2 1
0 1 −1 0
3 8 4 3
A questo punto sottraiamo alla terza riga la prima moltiplicata per tre. Otteniamo la matrice B:
B =
1 2 2 1
0 1 −1 0 0 2 −2 0
Il nostro prossimo scopo `e di ottenere a partire da B una matrice C in cui B32 = 0. Sottraiamo alla terza riga di B la seconda moltiplicata per 2. Otteniamo la matrice C:
C =
1 2 2 1
0 1 −1 0
0 0 0 0
Quindi, scelto un arbitrario z, otteniamo dalla seconda riga y − z = 0, da cui segue y = z. Infine dalla prima riga si ricava: x + 2z + 2z = 1, che implica x = 1 − 4z. In conclusione, abbiamo infinite soluzioni date dai vettori
C =
1 − 4z
z z
Esercizio 5
Si determini il resto della divisione di 875 per 11.
Soluzione
Ricordiamo il teorema di Fermat: se p `e un numero primo e x non `e divisibile per p, allora xp−1 ≡ 1 (mod p).
Applicando il teorema di Fermat al numero primo 11, otteniamo 810 ≡ 1 (mod 11). Quindi 875 = (23)75 = 2225 = 210×22+5= 210×22× 25= (210)22× 25≡11122× 25= 25= 32 ≡11−1 ≡1110.
