Corso di Laurea in Informatica Seconda prova intermedia del 17 Dicembre 2003 – Versione A (Soluzioni a cura di M. Di Nasso)

Esercizio 1. Sia f la successione definita per ricorrenza ponendo f_{0} = 1, f_{1} = −3, f_{n+1} = −f_{n}+f_{n−1}.

1. Calcolare il valore di f_{6};

2. Dimostrare che se n è pari allora f_{n} > 0 e se n è dispari allora f_{n} < 0;

3. Dimostrare che la successione g_{n} = |f_{n}| è crescente.

Soluzione. (1) Applicando la definizione, si ricava che f_{2} = −f_{1} + f_{0} = −(−3) + 1 = 4; f_{3} = −4 + (−3) = −7; f_{4} = −(−7) + 4 = 11; f_{5} = −11 + (−7) = −18 e f_{6} = −(−18) + 11 = 29.

(2) Visto che f_{0} > 0 e f_{1} < 0, per n = 0 e n = 1 la base induttiva è verificata. Consideriamo adesso il passo induttivo f_{n+1}. Supponiamo prima n + 1 pari. In questo caso n è dispari e per ipotesi induttiva f_{n} < 0, quindi −f_{n} > 0. Inoltre, n − 1 è pari, dunque per ipotesi induttiva f_{n−1} > 0. Si conclude che f_{n+1} = −f_{n} + f_{n−1} > 0 perché somma di due numeri positivi. Se invece n + 1 è dispari, il ragionamento è analogo. Infatti in questo caso n è pari e per ipotesi induttiva f_{n} > 0, dunque −f_{n} > 0. Inoltre, ancora per ipotesi induttiva, f_{n−1} > 0 perché n − 1 è dispari. Si conclude che f_{n+1} = −f_{n} + f_{n−1} < 0 perché somma di due numeri negativi.

(3) Per dimostrare questa proprietà, è sufficiente usare la proprietà (2) appena vista, e non c’è bisogno di usare di nuovo l’induzione. Infatti, se n + 1 è pari, allora g_{n+1} = |f_{n+1}| = (poiché f_{n+1} è positivo) = f_{n+1} = −f_{n} +f_{n−1} ≥ (poichè f_{n−1} è positivo) ≥ −f_{n} = (poiché f_{n} è negativo) = |f_{n}| = g_{n}. In modo del tutto simile, anche nel caso n + 1 dispari, si dimostra che g_{n+1} ≥ g_{n}.

Non è necessario ai fini della risoluzione di questo esercizio, ma con ragionamenti analoghi a sopra, si può mostrare che g_{n+1} = g_{n} +g_{n−1} è in realtà una successione di Fibonacci, con valori iniziali g_{0} = 1 e g_{1} = 3. In particolare è crescente.

Esercizio 2.

1. Sia X = P(Y) l’insieme delle parti di Y = {1, 2, 3}.

• Quanti elementi appartengono ad X?

• Quali delle seguenti affermazioni sono vere? (a) 1 ∈ X;

(b) 1 ⊆ X;

(c) {1} ∈ X;

(d) {1} ⊆ X

2. Stabilire se la seguente implicazione è sempre vera, dandone una dimostrazione in caso affermativo, o trovando un controesempio in caso contrario:

(A ⊆ B ∧ B ∈ C) → A ⊆ C.

Soluzione. (1) In generale, un insieme finito con n elementi ha esattamente 2^{n} sottoinsiemi (questo è stato dimostrato a lezione). Poiché Y contiene 3 elementi, il suo insieme delle parti X = P(Y) contiene esattamente 2^{3} = 8 elementi. Precisamente:

X = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Si osservi che gli elementi dell’insieme X = P(X) sono a loro volta insiemi (questo fatto accade spesso in matematica). Per rispondere correttamente alle domande che seguono, è indispensabile notare che 1 ≠ {1}. Infatti 1 è un numero, mentre {1} è un insieme, precisamente l’insieme che contiene il numero 1 come suo unico elemento. A questo punto, si può verificare immediatamente che 1 ∉ X (dunque (a) è falsa), e che {1} ∈ X (dunque (c) è vera). La (d) è evidentemente falsa. Infatti {1} ⊆ X significa che ogni elemento di {1} è anche elemento di X. Ma questo è falso perché 1 ∈ {1} mentre 1 ∉ X. Infine anche la (b) è banalmente falsa perché 1 non è un insieme.

(2) Questa implicazione non è vera in generale. Ad esempio, se A = {1}, B = {1, 2} e C = {{1, 2}, {2}}, allora A ⊆ B e B ∈ C, ma A ⊈ C perché 1 ∉ C.

Esercizio 3. Indichiamo con X_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare il numero delle funzioni iniettive f : X_{8} → X_{16};

2. Determinare il numero delle funzioni f : X_{8} → X_{16} tali che per almeno un elemento x ∈ X_{8}, f(x) è pari;

3. Determinare il numero delle funzioni f : X_{8} → X_{16} per le quali esistono esattamente 5 elementi x ∈ X_{8} tali che f(x) = 3.

4. Determinare il numero delle funzioni iniettive f : X_{8} → X_{16} tali che se x è pari, allora f(x) sia pari.

Soluzione. (1) Si tratta di contare le disposizioni D_{16,8} = 16 · 15 · 14 · 13 · 12 · 11 · 10 · 9. Infatti ci sono 16 possibili scelte per il valore f(1); per ognuna di queste scelte, ci sono 15 possibili scelte per il valore f(2) (uno qualunque dei 16 numeri in X_{16} tranne f(0), altrimenti f non è iniettiva); etc.

(2) Le funzioni che dobbiamo contare sono tutte tranne quelle che assumono solo valori dispari. Queste ultime sono tante quante le funzioni f : X_{8} → {1, 3, 5, 7, 9, 11, 13, 15}, cioè 8^{8}. Visto che tutte le funzioni f : X_{8} → X_{16} sono 16^{8}, il numero cercato è 16^{8} − 8^{8}.

(3) Le possibili scelte dei 5 elementi x ∈ X_{8} tali che f(x) = 5 sono tante quanti i sottoinsiemi di 5 elementi presi da un insieme di 8 elementi, e cioè \binom{8}{5}. Per ognuna di queste scelte, restano da attribuire i valori f(x) ai rimanenti 3 elementi. Per ciascuno di questi 3 elementi ci sono 15 possibili scelte (uno qualunque tra i 16 numeri di X_{16}, tranne il 5). Il calcolo finale è dunque: \binom{8}{5} · 15^{3}.

(4) Per ciascuno dei 4 numeri pari x ∈ X_{8}, posso scegliere come sua immagine f(x) uno qualunque tra gli 8 numeri pari di X_{16}. Visto che f deve essere iniettiva, ho in tutto 8 · 7 · 6 · 5 possibilità. Per ognuna di queste scelte, restano da attribuire i valori f(x) ai 4 numeri dispari x di X_{8}. Poiché f deve essere iniettiva, ho 12 possibili scelte per f(1) (uno qualunque degli elementi di X_{16} tranne i 4 valori già assegnati f(2), f(4), f(6) e f(8)); 11 possibili scelte per f(3), 10 possibili scelte per f(5) e 9 possibili scelte per f(7). (Si osservi che se x è pari, allora f(x) deve essere pari, ma se x è dispari, non ci sono restrizioni su f(x), che può essere sia pari che dispari). Il numero delle funzioni cercate è dunque (8 · 7 · 6 · 5) · (12 · 11 · 10 · 9).

Esercizio 4. Determinare la minima soluzione positiva dell’equazione

4250x ≡ 390 (mod 174)

Determinare inoltre il numero delle soluzioni x comprese tra 1 e 1500.

Soluzione. (1) Intanto possiamo dividere tutto per 2 ed ottenere: 2125x ≡ 195 (mod 87). Poi possiamo ridurre i coefficienti modulo 87. Visto che 2125 = 24 · 87 + 37 (dunque 2125 ≡ 37 (mod 87)), e che 195 = 2 · 87 + 21 (dunque 195 ≡ 21 (mod 87)), l’equazione di sopra è equivalente a

37x ≡ 21 (mod 87).

Si osservi che 37 è un numero primo, mentre 87 = 3 · 29 dove 29 è primo. Dunque il massimo comun divisore (37, 87) = 1 e perciò l’equazione 37x ≡ 21 (mod 87) ammette ed unica soluzione modulo 87. Con successive divisioni euclidee, si ricava l’identità di Bezout: 1 = 37 · 40 − 87 · 17. Moltiplicando tutto per 21 si ottiene: 21 = 37 · (40 · 21) − 87 · (17 · 21). Allora x = 40 · 21 = 840 è una soluzione della nostra equazione. Visto che 840 = 9 · 87 + 57, e quindi 840 ≡ 57 (mod 87), si conclude che x = 57 è la minima soluzione positiva della congruenza proposta.

(2) Tutte le soluzioni positive della congruenza sono della forma x = 57 + 87k dove k = 0, 1, 2, . . .. Visto che per k = 16 si ha x = 57 + 87 · 16 = 1449 < 1500 mentre per k = 17 si ha x = 57 + 87 · 17 = 1536 > 1500, si conclude che ci sono esattamente 17 soluzioni positive comprese tra 1 e 1500 (tante quanti i valori di k = 0, 1, …, 16).

Corso di Laurea in Informatica Seconda prova intermedia del 17 Dicembre 2003 – Versione B (Soluzioni a cura di M. Di Nasso)

Esercizio 1. Determinare la minima soluzione positiva dell’equazione

4174x ≡ 406 (mod 186)

Determinare inoltre il numero delle soluzioni x comprese tra 1 e 1400.

Soluzione. (1) Intanto possiamo dividere tutto per 2 ed ottenere: 2087x ≡ 203 (mod 93). Poi possiamo ridurre i coefficienti modulo 93. Visto che 2087 = 22 · 93 + 41 (dunque 2087 ≡ 41 (mod 93)), e che 203 = 2 · 93 + 17 (dunque 203 ≡ 17 (mod 93)), l’equazione di sopra è equivalente a

41x ≡ 17 (mod 93).

Si osservi che 41 è un numero primo, mentre 93 = 3 · 31 dove 31 è primo. Dunque il massimo comun divisore (41, 93) = 1 e perciò l’equazione 41x ≡ 17 (mod 93) ammette ed unica soluzione modulo 93. Con successive divisioni euclidee, si ricava l’identità di Bezout: 1 = 41 · (−34) + 93 · 15. Moltiplicando tutto per 17 si ottiene: 17 = 41 · (−34 · 17) + 93 · (15 · 17). Allora x = −34 · 17 = −578 è una soluzione della nostra equazione. Visto che −578 = −7 · 93 + 73, e quindi −578 ≡ 73 (mod 93), si conclude che x = 73 è la minima soluzione positiva della congruenza proposta.

(2) Tutte le soluzioni positive della congruenza sono della forma x = 73 + 93k dove k = 0, 1, 2, . . .. Visto che per k = 14 si ha x = 73 + 93 · 14 = 1375 < 1400 mentre per k = 15 si ha x = 73 + 93 · 15 = 1468 > 1400, si conclude che ci sono esattamente 15 soluzioni positive comprese tra 1 e 1400 (tante quanti i valori di k = 0, 1, …, 14).

Esercizio 2. Indichiamo con A_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare il numero delle funzioni iniettive f : A_{10} → A_{14};

2. Determinare il numero delle funzioni f : A_{10} → A_{14} tali che per almeno un elemento x ∈ A_{10}, f(x) è dispari;

3. Determinare il numero delle funzioni f : A_{10} → A_{14} per le quali esistono esattamente 3 elementi x ∈ A_{10} tali che f(x) = 7.

4. Determinare il numero delle funzioni iniettive f : A_{10} → A_{14} tali che se x è pari, allora f(x) sia dispari.

Soluzione. Per le motivazioni, si rimanda all’analogo esercizio della versione A.

(1) D_{14,10} = 14 · 13 · 12 · 11 · 10 · 9 · 8 · 7 · 6 · 5.

(2) 14^{10} − 7^{10}.

(3) \binom{10}{3} · 13^{7}.

(4) (7 · 6 · 5 · 4 · 3) · (9 · 8 · 7 · 6 · 5).

Esercizio 3.

1. Sia Y = P(X) l’insieme delle parti di X = {a, b, c, d}.

• Quanti elementi appartengono ad Y?

• Quali delle seguenti affermazioni sono vere? (a) a ⊆ Y;

(b) {a} ⊆ Y;

(c) {a} ∈ Y;

(d) a ∈ Y.

2. Stabilire se la seguente implicazione è sempre vera, dandone una dimostrazione in caso afferma-

tivo, o trovando un controesempio in caso contrario: (D ⊆ E ∧ E ∈ F) → D ⊆ F.

Soluzione. Per le motivazioni, si rimanda all’analogo esercizio della versione A.

(1) Y contiene 2^{4} = 16 elementi. Precisamente Y è l’insieme:

{∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}.

(c) è vera. Le altre sono false.

(2) Questa implicazione non è vera in generale. Ad esempio, se D = {1}, E = {1, 2} e F = {{1, 2}, {2}}, allora D ⊆ E e E ∈ F, ma D ⊈ F perché 1 ∉ F.

Esercizio 4. Sia g la successione definita per ricorrenza ponendo g_{0} = 2, g_{1} = −3, g_{n+1} = −g_{n}+g_{n−1}. 1. Calcolare il valore di g_{6};

2. Dimostrare che se n è pari allora g_{n} > 0 e se n è dispari allora g_{n} < 0;

3. Dimostrare che la successione f_{n} = |g_{n}| è crescente.

Soluzione. (1) Applicando la definizione, si ricava che g_{2} = −g_{1} + g_{0} = −(−3) + 2 = 5; g_{3} = −5 + (−3) = −8; g_{4} = −(−8) + 5 = 13; g_{5} = −13 + (−8) = −21 e g_{6} = −(−21) + 13 = 34.

(2) e (3). Le Le dimostrazioni sono le stesse degli analoghi esercizi della versione A.

Corso di Laurea in Informatica Seconda prova intermedia del 17 Dicembre 2003 – Versione C (Soluzioni a cura di M. Di Nasso)

Esercizio 1. Indichiamo con X_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare il numero delle funzioni iniettive f : X_{12} → X_{18};

2. Determinare il numero delle funzioni f : X_{12} → X_{18} tali che per almeno un elemento x ∈ X_{12}, f(x) è pari;

3. Determinare il numero delle funzioni iniettive f : X_{12} → X_{18} tali che se x è dispari, allora f(x) sia dispari.

4. Determinare il numero delle funzioni f : X_{12} → X_{18} per le quali esistono esattamente 6 elementi x ∈ X_{12} tali che f(x) = 5.

Soluzione. Per le motivazioni, si rimanda all’analogo esercizio della versione A.

(1) D_{18,12} = 18 · 17 · 16 · 15 · 14 · 13 · 12 · 11 · 10 · 9 · 8 · 7.

(2) 18^{12} − 9^{12}.

(3) (9 · 8 · 7 · 6 · 5 · 4) · (12 · 11 · 10 · 9 · 8 · 7).

(4) \binom{12}{6} · 17^{6}.

Esercizio 2. Determinare la minima soluzione positiva dell’equazione

3826x ≡ 378 (mod 170)

Determinare inoltre il numero delle soluzioni x comprese tra 1 e 1600.

Soluzione. (1) Intanto possiamo dividere tutto per 2 ed ottenere: 1913x ≡ 189 (mod 85). Poi possiamo ridurre i coefficienti modulo 85. Visto che 1913 = 22 · 85 + 43 (dunque 1913 ≡ 43 (mod 85)), e che 189 = 2 · 85 + 19 (dunque 189 ≡ 19 (mod 85)), l’equazione di sopra è equivalente a

43x ≡ 19 (mod 85).

Si osservi che 43 è un numero primo, mentre 85 = 5 · 17 dove 17 è primo. Dunque il massimo comun divisore (43, 85) = 1 e perciò l’equazione 43x ≡ 19 (mod 85) ammette ed unica soluzione modulo 85. Con successive divisioni euclidee, si ricava l’identità di Bezout: 1 = 43 · 2 − 85 · 1. Moltiplicando tutto per 19 si ottiene: 19 = 43 · (2 · 19) − 85 · (1 · 19). Allora x = 2 · 19 = 38 è una soluzione ed è chiaramente la minima soluzione positiva della congruenza proposta.

(2) Tutte le soluzioni positive della congruenza sono della forma x = 38 + 85k dove k = 0, 1, 2, . . .. Visto che per k = 18 si ha x = 38 + 85 · 18 = 1568 < 1600 mentre per k = 19 si ha x = 38 + 85 · 19 = 1653 > 1600, si conclude che ci sono esattamente 19 soluzioni positive comprese tra 1 e 1600 (tante quanti i valori di k = 0, 1, …, 18).

Esercizio 3. Sia g la successione definita per ricorrenza ponendo g_{0} = −2, g_{1} = 3, g_{n+1} = −g_{n}+g_{n−1}.

1. Calcolare il valore di g_{6};

2. Dimostrare che se n è pari allora g_{n} < 0 e se n è dispari allora g_{n} > 0; 3. Dimostrare che la successione f_{n} = |g_{n}| è crescente.

Soluzione. (1) Applicando la definizione, si ricava che g_{2} = −g_{1} + g_{0} = −3 + (−2) = −5; g_{3} = −(−5) + 3 = 8; g_{4} = −8 + (−5) = −13; g_{5} = −(−13) + 8 = 21 e g_{6} = −21 + (−13) = −34.

(2) e (3). Le Le dimostrazioni sono pressoché le stesse degli analoghi esercizi della versione A (basta scambiare i casi “pari” e “dispari”).

Esercizio 4.

1. Sia A = P(B) l’insieme delle parti di B = {1, 2, 3, 4}.

• Quanti elementi appartengono ad A?

• Quali delle seguenti affermazioni sono vere?

(a) {4} ∈ A;

(b) 4 ∈ A;

(c) {4} ⊆ A;

(d) 4 ⊆ A.

2. Stabilire se la seguente implicazione è sempre vera, dandone una dimostrazione in caso affermativo, o trovando un controesempio in caso contrario:

(X ⊆ Y ∧ Y ∈ Z) → X ⊆ Z.

Soluzione. Per le motivazioni, si rimanda all’analogo esercizio della versione A.

(1) A contiene 2^{4} = 16 elementi. Precisamente A è l’insieme:

{∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}.

(a) è vera. Le altre sono false.

(2) Questa implicazione non è vera in generale. Ad esempio, se X = {1}, Y = {1, 2} e Z = {{1, 2}, {2}}, allora X ⊆ Y e Y ∈ Z, ma X ⊈ Z perché 1 ∉ Z.

Corso di Laurea in Informatica Seconda prova intermedia del 17 Dicembre 2003 – Versione D (Soluzioni a cura di M. Di Nasso)

Esercizio 1.

1. Sia Y = P(X) l’insieme delle parti di X = {a, b, c}.

• Quanti elementi appartengono ad Y?

• Quali delle seguenti affermazioni sono vere? (a) {c} ⊆ Y;

(b) c ⊆ Y;

(c) {c} ∈ Y;

(d) c ∈ Y.

2. Stabilire se la seguente implicazione è sempre vera, dandone una dimostrazione in caso affermativo, o trovando un controesempio in caso contrario:

(G ⊆ H ∧ H ∈ K) → G ⊆ K.

Soluzione. Per le motivazioni, si rimanda all’analogo esercizio della versione A.

(1) Y contiene 2^{3} = 8 elementi. Precisamente:

Y = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

(c) è vera. Le altre sono false.

(2) Questa implicazione non è vera in generale. Ad esempio, se G = {1}, H = {1, 2} e K = {{1, 2}, {2}}, allora G ⊆ H e H ∈ K, ma G ⊈ K perché 1 ∉ K.

Esercizio 2. Sia f la successione definita per ricorrenza ponendo f_{0} = −1, f_{1} = 3, f_{n+1} = −f_{n}+f_{n−1}.

1. Calcolare il valore di f_{6};

2. Dimostrare che se n è pari allora f_{n} < 0 e se n è dispari allora f_{n} > 0;

3. Dimostrare che la successione g_{n} = |f_{n}| è crescente.

Soluzione. (1) Applicando la definizione, si ricava che f_{2} = −f_{1} + f_{0} = −3 + (−1) = −4; f_{3} = −(−4) + 3 = 7; f_{4} = −7 + (−4) = −11; f_{5} = −(−11) + 7 = 18 e f_{6} = −18 + (−11) = −29.

(2) e (3). Le Le dimostrazioni sono pressoché le stesse degli analoghi esercizi della versione A (basta scambiare i casi “pari” e “dispari”).

Esercizio 3. Determinare la minima soluzione positiva dell’equazione

4254x ≡ 406 (mod 190)

Determinare inoltre il numero delle soluzioni x comprese tra 1 e 1300.

4254x=406 (190) 37x=13 (95) 18*37-7*95=1 x=44 (95)

Soluzione. (1) Intanto possiamo dividere tutto per 2 ed ottenere: 2127x ≡ 203 (mod 95). Poi possiamo ridurre i coefficienti modulo 95. Visto che 2127 = 22 · 95 + 37 (dunque 2127 ≡ 37 (mod 95)), e che 203 = 2 · 95 + 13 (dunque 203 ≡ 13 (mod 95)), l’equazione di sopra è equivalente a

37x ≡ 13 (mod 95).

Si osservi che 37 è un numero primo, mentre 95 = 5 · 19 dove 19 è primo. Dunque il massimo comun divisore (37, 95) = 1 e perciò l’equazione 37x ≡ 13 (mod 95) ammette ed unica soluzione modulo 95. Con successive divisioni euclidee, si ricava l’identità di Bezout: 1 = 37 · 18 − 95 · 7. Moltiplicando tutto per 13 si ottiene: 13 = 37 · (18 · 13) − 95 · (7 · 13). Allora x = 18 · 13 = 234 è una soluzione della nostra equazione. Visto che 234 = 2 · 95 + 44, e quindi 234 ≡ 44 (mod 95), si conclude che x = 44 è la minima soluzione positiva della congruenza proposta.

(2) Tutte le soluzioni positive della congruenza sono della forma x = 44 + 95k dove k = 0, 1, 2, . . .. Visto che per k = 13 si ha x = 44 + 95 · 13 = 1279 < 1300 mentre per k = 14 si ha x = 44 + 95 · 14 = 1374 > 1300, si conclude che ci sono esattamente 14 soluzioni positive comprese tra 1 e 1300 (tante quanti i valori di k = 0, 1, …, 13).

Esercizio 4. Indichiamo con A_{n} = {1, 2, …, n} l’insieme dei numeri naturali da 1 ad n.

1. Determinare il numero delle funzioni iniettive f : A_{8} → A_{18};

2. Determinare il numero delle funzioni f : A_{8} → A_{18} tali che per almeno un elemento x ∈ A_{8}, f(x) è dispari;

3. Determinare il numero delle funzioni iniettive f : A_{8} → A_{18} tali che se x è dispari, allora f(x) sia pari.

4. Determinare il numero delle funzioni f : A_{8} → A_{18} per le quali esistono esattamente 4 elementi x ∈ A_{8} tali che f(x) = 9.

Soluzione. Per le motivazioni, si rimanda all’analogo esercizio della versione A.

(1) D_{18,8} = 18 · 17 · 16 · 15 · 14 · 13 · 12 · 11.

(2) 18^{8} − 9^{8}.

(3) (9 · 8 · 7 · 6) · (14 · 13 · 12 · 11).

(4) \binom{8}{4} · 17^{4}.