27 Gennaio 2020

(1)

1. Dimostrare per induzione che

n

X

i=1

i ≤ nⁿ per ogni n ≥ 1.

Soluzione

Base dell’induzione n = 1: P1

i=1i = 1 ≤ 1¹ = 1.

Supponiamo per ipotesi d’induzione chePn

i=1i ≤ nⁿ, Proviamo che Pn+1

i=1 i ≤ (n + 1)ⁿ⁺¹. Pn+1

i=1 i = (Pn

i=1i) + (n + 1) ≤_{Ip Ind} nⁿ+ n + 1 ≤Pn

k=0(n su k)n^k = (n + 1)ⁿ ≤ (n + 1)ⁿ⁺¹. (n su k) `e il coefficiente binomiale

2. Nell’insieme N×N delle coppie di numeri naturali si definisca, per ogni (a, b), (c, d) ∈ N×N, la relazione seguente:

(a, b) R (c, d) ⇔ a + b + c + d = 100.

(a) Quali propriet`a verifica la relazione R?

(b) Determinare quante sono le coppie (a, b) in relazione con (50, 49).

Soluzione Non `e riflessiva : (1, 1) non `e in relazione con se stesso.

Non `e transitiva: (49, 0)R(26, 25)R(49, 0) ma (49, 0) non `e in relazione con se stesso.

E simmetrica: se a + b + c + d = 100 allora c + d + a + b = 100.`

Non `e antisimmetrica, perch´e (49, 0)R(26, 25) e (26, 25)R(49, 0) ma le due coppie sono distinte.

(0, 1) e (1, 0) sono le uniche coppie in relazione con (50, 49).

3. Si definisca S(x) ≡ x `e uno studente, P (x) ≡ x `e un professore e R(x, y) ≡ x ammira y.

Si formalizzino le seguenti frasi:

(a) Qualche professore ammira tutti gli studenti ∃x[P (x) ∧ ∀y[S(y) → xRy]]

(b) Ogni professore ammira qualche studente. ∀x[P (x) → ∃y[S(y) ∧ xRy]]

(c) Qualche professore ammira qualche studente. ∃xy[P (x) ∧ S(y) ∧ xRy]]

4. Si determini il resto della divisione di 3³⁴⁶ per 7.

Soluzione 7 non divide 3. Per Fermat 3⁶ ≡7 1. Da 346 = 57 × 6 + 4, si ha 3³⁴⁶ ≡7 3⁴ = 3²3² ≡₇ 2 × 2 = 4

1