Matematica Discreta (6 crediti) BBBBB
21 Gennaio 2016
Cognome e nome:
Matricola:
1. Dimostrare per induzione che 2n> n2 per ogni intero n ≥ 5.
Soluzione: Base Induzione: 25 = 32 > 25 = 52. OK
Supponiamo per ipotesi d’induzione che 2n > n2. Proviamo che 2n+1> (n+1)2 = n2+2n+1.
2n+1 = 2n∗ 2 = 2n+ 2n >Ip.Ind.n2+ 2n>Ip.Ind.n2+ n2 =
= n2+ 2n + (n − 2)n >(n≥5)n2+ 2n + 3 ∗ 5 > n2+ 2n + 1 = (n + 1)2. Il principio di induzione ci permette di concludere che 2n> n2 per ogni intero n ≥ 5.
2. In una societ`a vi sono 50 soci tra i quali bisogna scegliere il segretario, il presidente e il vice-presidente. Presidente e segretario possono essere la stessa persona. Quante possibilit`a di scelta abbiamo? Non appena eletto presidente il Signor Pinco elargisce 500 biglietti da 10 euro tra i rimanenti soci. In quanti possibili modi pu`o distribuire i biglietti?
Soluzione: Abbiamo tre posti distinti. Il primo etichettato “vice-presidente”, il secondo etichettato “presidente” ed il terzo etichettato “segretario”. Applichiamo il principio molti- plicativo. Iniziamo con la scelta del vice-presidente. Abbiamo 50 possibilit`a. Non appena scelto il vice-presidente, scegliamo il presidente. Rimangono, per ciascuna delle scelte del vice-presidente, 49 possibilit`a. In totale 50 ∗ 49. Infine scegliamo il segretario. Anche per il segretario abbiamo 49 possibilit`a perch´e il segretario pu`o coincidere con il presidente. In totale 50 ∗ 49 ∗ 49.
I 500 biglietti sono indistinguibili. Pinco li deve elargire tra 49 soci, tutti i soci escluso il presidente Pinco stesso. Sia A = {s1, . . . , s49} l’insieme dei 49 soci. Una suddivisione delle banconote corrisponde ad una funzione f : A → N tale che f (s1) + · · · + f (s49) = 500. In altre parole f `e un multinsieme di un insieme di 49 elementi di ordine 500. Il numero totale
`e: 49+500−1500−1 = 548499.
3. Sia Z l’insieme dei numeri interi e sia g : Z → Z una funzione definita come segue:
g(x) = (x + 5)(x2− 1).
Si determini se la funzione g `e iniettiva, surgettiva oppure bigettiva.
1
Soluzione: La funzione g `e iniettiva se ∀x∀y(x 6= y → g(x) 6= g(y)). Per falsificare l’enunciato precedente `e sufficiente trovare un controesempio:
g(1) = (1 + 5)(12− 1) = 0; g(−1) = (−1 + 5)((−1)2− 1) = 0.
La funzione g non essendo iniettiva non `e neanche bigettiva.
La funzione g `e surgettiva se ∀y∃x(y = g(x)). g non `e surgettiva perch´e, per esempio, il numero 1 6= g(x) per ogni intero x. Ricordiamo che il prodotto di due interi a e b `e uguale ad 1 sse a = b = 1 oppure a = b = −1. Se per assurdo 1 = g(x) = (x + 5)(x2− 1), allora abbiamo due casi:
(a) x + 5 = 1 e x2− 1 = 1, che non ammette soluzione nei numeri interi.
(b) x + 5 = −1 e x2− 1 = −1, che non ammette soluzione nei numeri interi.
4. Si provi che esistono infiniti numeri primi.
Soluzione: Supponiamo per assurdo che esistano un numero finito di numeri primi, e siano p1, p2, . . . , pk. Allora si consideri il numero (p1∗p2∗· · ·∗pk)+1. Questo numero `e relativamente primo con ciascuno dei numeri primi pi (1 ≤ i ≤ k), perch´e altrimenti pi dividerebbe 1. Dal teorema fondamentale dell’aritmetica ogni numero naturale maggiore di 1 `e scomponibile in fattori primi. Quindi si ottiene una contraddizione.
