Matematica Discreta BBBB (6 crediti)
14 Gennaio 2019
Cognome e nome:
Matricola:
1. Si determini il resto della divisione di 6118 per 13.
Soluzione: Possiamo applicare il teorema di Fermat perch´e 13 `e primo e 6 non `e divisibile per 13. Quindi 612 ≡131. Dividiamo 118 per 12: 118 = 12 × 9 + 10. Quindi si ha:
6118 = 612×9+10= 612×9610 = (612)9610 ≡1319610= 610 = (62)5 ≡13 (−3)5 =
= (−3)3× (−3)2 ≡13 (−1) × 9 = −9 ≡134
2. (a) In quanti modi si possono disporre 8 palline indistinguibili in 16 contenitori distinti in maniera tale che ogni contenitore contenga al pi`u una pallina?
Soluzione: Le palline sono indistinguibili. Quindi, NON le possiamo numerare. I contenitori sono distinti: quindi, li possiamo chiamare con nomi diversi c1, c2, . . . , c16. Porre le 8 palline in 8 contenitori diversi (al pi`u una pallina in un contenitore) corrisponde a prendere un sottoinsieme di cardinalit`a 8 di un insieme di sedici elementi (combinazioni senza ripetizioni).
Considerando che n = 12 e k = 8, in totale abbiamo 128 possibilit`a.
(b) In quanti modi si possono disporre 12 palline distinguibili in 10 contenitori distinti?
Soluzione: Le palline sono distinguibili. Quindi le possiamo numerare da 1 a 12. I contenitori sono distinti: quindi, li possiamo chiamare con nomi diversi c1, c2, . . . , c9, c10. Ogni disposizio- ne delle palline nei contenitori corrisponde ad una funzione dall’insieme {1, 2, . . . , 10, 11, 12}
nell’insieme {c1, c2, . . . , c9, c10} dei dieci contenitori. Si tratta quindi di disposizioni con ripetizione di un insieme di dieci elementi di ordine 12: D0n,k = 1012.
3. Dimostrare per induzione che, per ogni n ≥ 1, il numero n3+ 2n `e divisibile per 3.
Soluzione: Per n = 1 (base dell’induzione) `e vero. Supponiamo per ipotesi d’induzione che n3 + 2n sia divisibile per 3. Proviamo che anche (n + 1)3 + 2(n + 1) `e divisibile per 3:
(n + 1)3+ 2(n + 1) = n3+ 3n2 + 3n + 1 + 2n + 2 = (n3+ 2n) + 3n2+ 3n + 3.
1
Ora si usa l’ipotesi induttiva per cui n3+ 2n = 3h per un certo h ∈ N e si conclude:
(n + 1)3+ 2(n + 1) = (n3+ 2n) + 3n2+ 3n + 3 = 3h + 3n2+ 3n + 3 = 3(h + n2+ n + 1) che `e un multiplo di 3.
4. Si consideri la seguente relazione binaria R sull’insieme dei numeri naturali: xRy se, e solamente se, x e y hanno la stessa cifra pi`u a destra nella loro rappresentazione decimale e x ≤ y nell’usuale ordine sui numeri naturali.
Quali propriet`a verifica la relazione R?
Soluzione: Indichiamo con c(x) la cifra pi`u a destra nella rappresentazione decimale del numero x. Allora la relazione R si pu`o scrivere come segue:
xRy ⇔ c(x) = c(y) ∧ x ≤ y.
Prop. Riflessiva ∀x(xRx): Vale perch´e c(x) = c(x) e x ≤ x.
Prop. Simmetrica ∀xy(xRy → yRx): Non vale. Controesempio: Sappiamo che 10R100, ma 100R10 `e falso perch´e 100 6≤ 10.
Prop. Transitiva ∀xyz(xRy ∧ yRz → xRz): Vale. Supponiamo che xRy e yRz. Questo significa che c(x) = c(y), x ≤ y, c(y) = c(z) e y ≤ z. Allora c(x) = c(y) = c(z) e x ≤ y ≤ z.
Per la propriet`a transitiva dell’uguaglianza e degli ordinamenti parziali, ricaviamo c(x) = c(z) e x ≤ z, cio´e xRz.
Prop. Antisimmetrica ∀xy(xRy ∧ yRx → x = y): Vale. Supponiamo che xRy e yRx, cio´e c(x) = c(y), x ≤ y, c(y) = c(x), y ≤ x. Dalla propriet`a antisimmetrica di ≤ si ricava x = y.
