Matematica Discreta (6 crediti)
8 giugno 2015
Cognome e nome:
Matricola:
1. Dimostrare per induzione che
n! ≥ n2 per ogni n ≥ 4
Soluzione: caso base n = 4. 4! = 24 ≥ 16 = 42. Verificato.
Vogliamo ora dimostrare che (n+1)! ≥ (n+1)2, supposta vera la relazione n! ≥ n2. Abbiamo che (n + 1)! = (n + 1)n!. Per ipotesi induttiva abbiamo (n + 1)n! ≥ (n + 1)n2. Volendo mostrare che (n + 1)! ≥ (n + 1)2, basta mostrare che n2 ≥ (n + 1) per ogni n ≥ 4. Usiamo di nuovo l’induzione, e dopo il caso base 42 = 16 ≥ 5 = 4 + 1 abbiamo che (n + 1)2 = n2 + 2n + 1 ≥ n + 1 + 2n + 1 = 3n + 2 ≥ n + 2 = (n + 1) + 1.
2. Formalizzare nel linguaggio matematico i seguenti enunciati.
• “Non tutti gli studenti amano la combinatoria”.
• “Esiste uno studente che ama tutte le materie”.
Soluzione: Definiamo le relazioni
• “S(x)” se e solo se x `e uno studente.
• “A(x, y)” se e solo se x ama y.
• “M (x)” se e solo se x `e una materia scolastica.
Quindi le frasi si traducono
• ¬∀x(S(x) → A(x, C))
• ∃x(S(x) ∧ ∀y(M (y) → A(x, y)))
dove C `e una costante che rappresenta la Combinatoria.
1
3. Nel torneo di calcetto del quartiere si sono iscritti 10 giocatori. Bisogna formare due squadre, la squadra rossa e la squadra blu, scegliendo 5 giocatori per squadra. Quante sono le possibili partite “squadra rossa contro squadra blu”, considerando diverse le partite in cui i giocatori delle due squadre sono diversi? Quante sono le partite fra due squadre senza nome formate con le stesse regole?
Soluzione: il numero di possibili formazioni che pu`o avere la squadra rossa `e 105. La formazione della squadra blu `e determinato univocamente dalla formazione della squadra rossa, quindi le possibili partite “squadra rossa contro squadra blu” sono 105.
Se invece consideriamo due squadre “senza nome”, allora le possibili partite sono solo 12 105, perch´e non c’`e distinzione fra due partite con formazioni uguali.
4. Si risolva l’equazione
4x ≡ 7 mod 9.
Soluzione: 4 `e relativamente primo con 9, e quindi sicuramente ne esiste l’inverso. Consi- derando che 4 · 7 = 28 ≡ 1 mod 9, 7 `e l’inverso di 4. Quindi per risolvere l’equzione basta moltiplicare ambo i membri per 7, ed ottenere x ≡ 7 · 7 mod 9, e quindi x ≡ 4.
5. Sia X l’insieme delle funzioni aventi dominio l’insieme {a, b, c} e codominio l’insieme {0, 1, 2}.
Determinare quali propriet`a soddisfa la relazione binaria R su X cos`ı definita:
f Rg se e solo se f (b) = g(b)
Nel caso R sia una relazione di equivalenza, fornire esplicitamente un rappresentante per le classi di equivalenza.
Soluzione:
Propriet`a riflessiva. Vale perch´e per ogni f ∈ X, f (b) = f (b).
Propriet`a simmetrica: Se per due funzioni f, g abbiamo che f (b) = g(b), allora anche g(b) = f (b). Quindi la propriet`a vale.
Propriet`a transitiva. Date f, g, h ∈ X, se f (b) = g(b) e g(b) = h(b), allora anche f (b) = h(b).
Anche questa propriet`a vale.
Propriet`a antisimmetrica. Siano le funzioni f, g ∈ X tali che f (a) = 1, f (b) = f (c) = 0 e g(a) = g(b) = g(c) = 0. Abbiamo che f Rg e gRf , ma f e g sono distinti elementi di X.
Quindi questa propriet`a non vale.
La relazione R `e quindi un’equivalenza. Ci sono numerose scelte per i rappresentanti delle classi di equivalenza. La scelta pi`u semplice `e data dalle tre funzioni costanti f, g, h (se definite esplicitamente, risulta f (a) = f (b) = f (c) = 0, g(a) = g(b) = g(c) = 1 e h(a) = h(b) = h(c) = 2).
