Matematica Discreta
Recupero Compitino Modulo I 23 Maggio 2013
Nome e Cognome:
Numero Matricola:
Giustificare ogni risposta.
Esercizio 1
Sia X un insieme. Si dimostri che per tutti i sottinsiemi A, B, C di X vale la seguente relazione:
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Soluzione: Si veda Example 2.5 negli appunti del corso.
Esercizio 2
Si consideri la seguente relazione binaria R sui numeri naturali:
nRk se, e solamente se, n + k ≤ 10.
Si verifichi se la relazione R e’ riflessiva, simmetrica, transitiva, antisimmetrica.
Soluzione:
• R non e’ riflessiva. Controesempio: 6R6 e’ falso perche’ 6 + 6 = 12 > 10.
• R e’ simmetrica: Sia xRy. Allora, per definizione di R, si ha x + y ≤ 10, da cui y + x ≤ 10, che e’ equivalente a yRx.
• R non e’ transitiva. Controesempio: 6R3, 3R5, ma 6R5 e’ falso. Infatti, 6+3 ≤ 10 e 3+5 ≤ 10 ma 6+5 = 11 > 10.
• R non e’ antisimmetrica, perche’ una relazione simmetrica non puo’ essere antisimmetrica. Controesempio: 1R2 e 2R1 ma 2 6= 1.
Esercizio 3
In quanti modi si possono lanciare 10 palline distinguibili in 4 contenitori distinti?
Soluzione: Ciascuna pallina ha quattro possibilita’. Quindi in totale abbiamo 410 possibilita’.
Esercizio 4
Si determini qual e’ il resto della divisione di (81)99per 7.
Soluzione: 7 e’ un numero primo. Quindi il teorema di Fermat ci permette di dire che 816 ≡ 1 (mod 7). Allora abbiamo:
8199= 81(6×16)+3= (816)16× (81)3≡ 116× (34)3= 312= (36)2≡ 12= 1 (mod 7).
Se non vogliamo applicare il Teorema di Fermat, calcoliamo nel modo seguente:
8199= (34)99= (32× 32)99≡ (2 × 2)99= 499= 2198= (23)66= 866≡ 166= 1 (mod 7).
Esercizio 5
Si provi per induzione che
2n− 1 = X
0≤k≤n−1
2k.
Soluzione: Caso base: n = 1. 21− 1 = 1 = 20=P
0≤k≤02k. Supponiamo vera l’uguaglianza per n, cioe’
2n− 1 = X
0≤k≤n−1
2k,
e dimostriamola per n + 1:
X
0≤k≤(n+1)−1
2k = X
0≤k≤n
2k= ( X
0≤k≤n−1
2k) + 2n=Ip.Ind.(2n− 1) + 2n = 2n+1− 1.
