KTH Matematik

5B1118 Diskret Matematik Lösningar till Kontrollskrivning 4 Mondag den 3 May, 2004

(1) (3p) Betrakta följande funktion:

f : ℕ → ℕ f(n) = n + (−1)^{n}

(a) Är f injektiv?

(b) Är f surjektiv?

(c) Är f bijektiv?

Man kan skriva f som:

f(n) = \{ \begin{matrix}n + 1 & om n är jämn; \\ n − 1 & om n är odd \end{matrix}

f(0) = 1 och 0 är det enda tal så att f(0) = 1.

(a) Antag att det finns n_{1}, n_{2} ∈ ℕ så att f(n_{1}) − f(n_{2}). Vi ska visa att n_{1} = n_{2}.

• Om n_{1} är jämn och n_{2} är odd (eller viceversa) då f(n_{1}) − f(n_{2}) betyder att n_{1} + 1 = n_{2} − 1, dvs n_{1} = n_{2} − 2. Men detta är omojligt när n_{1} är jämn och n_{2} är odd. Man avslutar då att om f(n_{1}) − f(n_{2}) så måste båda n_{1}, n_{2} vara jämna eller odda.

• Om n_{1}, n_{2} är jämna då f(n_{1}) − f(n_{2}) ger n_{1} + 1 = n_{2} + 1 och då är n_{1} = n_{2}.

• Om n_{1}, n_{2} är odda då f(n_{1}) − f(n_{2}) ger n_{1} − 1 = n_{2} − 1 och då är

n_{1} = n_{2}.

(b) Vi måste visa att varje m ∈ ℕ kan skrivas som m = n + (−1)^{n} för någon

n ∈ ℕ.

• Om m är jämn då är m+1 odd och f(m+1) = (m+1)+(−1)^{m+1} = m. Så n = m + 1.

• Om m är odd då är m−1 jämn och f(m−1) = (m−1)+(−1)^{m−1} = m.Så n = m − 1

• f är bijektiv.

(2) (3p) Betrakta följande mängd:

F (ℝ) = {f : ℝ → ℝ}

och följande binära operation:

+ : F (ℝ) × F (ℝ) → F (ℝ)

där f + g defineras som funktionen (f + g)(x) = f(x) + g(x) för varje (f, g) ∈ F (ℝ) × F (ℝ) och för varje x ∈ ℝ.

Visa att (F (ℝ), +) är en grupp.

(G1) Vi ska visa att operationen är associativ: Det är sant eftersom additionen är

associativ på ℝ. (G2) Vi ska hitta ett Identiteselemnt. Det är functionen

0 : ℝ → ℝ 0(x) = 0

Man ser att (0 + f)(x) = (f + 0)(x) = f(x) + 0(x) = f(x) + 0 = f(x) för varje f ∈ F (ℝ).

(G3) Låt f ∈ F (ℝ), vi ska hitta det inverselemnt (f)^{−1}. Definera

(f)^{−1}(x) = −f(x) för varje x ∈ ℝ

Denna är inverelemnt till f eftersom

(f + (f)^{−1})(x) = ((f)^{−1} + f)(x) = f(x) − f(x) = 0

(3) (3p) Betrakta följande permutationer σ, τ ∈ 𝕊_{8}:

σ = [35472816], τ = [12436587]

(a) Skriv σ, τ på cykelform.

(b) Bestäm σ^{−1}.

(c) Bestäm τ ∘ σ^{−1}

(a) σ = (1347)(25)(68), π = (1)(2)(34)(56)(78)

(b) σ^{−1} = (1743)(52)(86).

(c) på enradform är σ^{−1} = [75132846]. Det följer att, under τ ∘ σ^{−1} går

1 → 7 → 8, 2 → 5 → 6, ...
τ ∘ σ^{−1} = [86142735] = (1852673)(4)