Matematica Discreta (6 crediti) AAAAA

Matematica Discreta (6 crediti) AAAAA

21 Gennaio 2016

Cognome e nome:

Matricola:

1. Dimostrare per induzione che

n! ≥ 2ⁿ⁻¹ per ogni n ≥ 1.

Soluzione: Base induzione n = 1: 1! = 1 = 2⁰. Supponiamo per ipotesi d’induzione che n! ≥ 2ⁿ⁻¹ e dimostriamo che (n + 1)! ≥ 2^(n+1)−1= 2ⁿ.

(n + 1)! = (n + 1)n! ≥_Ip.Ind. (n + 1)2ⁿ⁻¹ ≥_(n≥1)(1 + 1)2ⁿ⁻¹ = 2 ∗ 2ⁿ⁻¹= 2ⁿ.

Quindi il principio di induzione ci permette di concludere che il seguente enunciato `e vero:

∀n(n ≥ 1 → n! ≥ 2ⁿ⁻¹).

2. Dieci amici prima giocano a carte e poi partecipano ad una cena.

(a) In quanti modi possiamo distribuire 40 carte tutte uguali tra i dieci amici immaginando che ogni amico abbia almeno una carta?

(b) Alla fine della cena ogni amico, salutando, stringe la mano a tutti gli altri amici. Quante strette di mano abbiamo in totale?

Soluzione: (a) Prima di dare una qualsiasi risposta, bisogna rappresentare il problema in maniera da farlo rientrare in una delle figure combinatorie. Le carte sono indistin- guibili. Bisogna distribuire solo 30 carte tra i dieci amici. La rappresentazione corret- ta `e quella dei multinsiemi di cardinalit`a 3 di un insieme di 10 elementi. Per esempio, A, A, A, A, A, A, B, B, B, C, C, C, C, C, C, C, C, C, .... significa che A ha sei carte (+1), B ha tre carte (+1), C ha nove carte (+1), e cos`ı via. In conclusione abbiamo combinazioni con ripetizione di un insieme di 10 elementi di ordine 30: il coefficiente binomiale 10 + 30 − 1 = 39 su 30.

(b) La stretta di mano dell’amico A e dell’amico B coincide con la stretta di mano dell’amico B e dell’amico A. L’ordine tra i due non `e importante. Quindi il numero di strette di mano

`e pari al numero di sottoinsiemi di cardinalit`a 2 di un insieme di 10 elementi. Combinazioni semplici: coefficiente binomiale 10 su 2.

1

3. Sia f : N → N una funzione definita come segue:

f (x) = (x + 3)(x²+ 1).

Verificare se la funzione `e iniettiva, surgettiva oppure bigettiva.

Soluzione: La funzione f `e iniettiva se ∀xy(x 6= y → f (x) 6= f (y)). Per provarlo verifichiamo che la funzione `e strettamente monotona: x < y implica f (x) < f (y). Infatti, x < y implica x + 3 < y + 3 e x² = x ∗ x < x ∗ y < y ∗ y = y², da cui x + 3 < y + 3 e x²+ 1 < y²+ 1. In conclusione,

f (x) = (x + 3)(x²+ 1) < (y + 3)(x²+ 1) < (y + 3)(y²+ 1) = f (y).

Quindi se x 6= y abbiamo x < y oppure y < x e possiamo applicare la monotonia per provare l’iniettivit`a.

La funzione f `e surgettiva se ∀y∃x(f (x) = y). La funzione non `e surgettiva. Controesempio:

y = 0. Non esiste alcun x tale che f (x) = 0. Altrimenti (x + 3)(x² + 1) = 0 implica che x + 3 = 0 oppure x²+ 1 = 0. Ma x + 3 ≥ 3 e x²+ 1 ≥ 1.

La funzione `e iniettiva ma non surgettiva. Quindi non `e bigettiva.

4. Si determini qual `e il resto della divisione di 9⁷⁷ per 11.

Soluzione: 11 `e un numero primo e non divide 9. Quindi possiamo applichiamo il piccolo teorema di Fermat 9¹⁰ ≡ 1 (mod 11).

9⁷⁷= 9^10∗7+7= (9¹⁰)⁷∗9⁷ ≡11 1⁷∗∗9⁷ = 9⁷ ≡11(−2)⁷ = −2⁷ = −2⁵∗2² = −4∗32 ≡11 −4∗(−1) = 4