KTH Matematik

5B1118 Diskret Matematik ExtraKontrollskrivning 19 Maj, 2004

Kontrollskrivning 1

(1) (3p) Hitta alla positiva heltal som uppfyller

21m + 66n = 30

(2) (3p) Låt M = {x ∈ ℤ så att |x| ≤ n} och P (M) vara mängden av delmängder till M. Visa att |P (M)| = 4^{n}.

(3) (3p) Hitta alla lösningar modulo 3 av ekvationer

x + y = 0

dvs alla lösningar i ℤ_{3}.

Kontrollskrivning 2

(1) (3p) Bestäm antalet heltal lösningar till ekvationen:

x_{1} + x_{2} + x_{3} + x_{4} = 28

med x_{i} > 0 för i = 1, 2, 3, och x_{4} ≥ 2.

(2) (3p) Hur många olika ord med 5 bokstäver kan man bilda med bokstäverna i ordet DISKRET?

(3) (3p) Visa att

(x + y)^{3} ≡_{3} x^{3} + y^{3}

Kontrollskrivning 3

(1) (3p)

• Rita en graf med incidensmatris:

A_{G} = ( \begin{matrix}1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \end{matrix} )

• Är G Eulersk? (Motivera ditt svaret.)

• Bestäm χ(G).

(2) (3p) Rita den bipartita grafen K_{3,6}. Hur många 3-cyklar finns i grafen?

(3) (3p) Låt G = (E, V) vara en enkel graf och G^{∗} = (E^{∗}, V^{∗}) vara den duala grafen ( samma noder där två är förbundad precis när de inte är förbundad i G). Bestäm |E| + |E^{∗}| om |V | = 7.

Kontrollskrivning 4

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

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

(a) Är f injektiv?

(b) Är f surjektiv?

(c) Är f bijektiv?

(d) (3p) Betrakta gruppen (ℤ_{7}, +) (i) Bestäm ordningen av varje element i gruppen; (ii) Beskriv alla delgrupper (alla är cykliska).

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

σ = [35472816], τ = [12436587]

(i) Bestäm (τ^{−1})^{2}. (ii) Bestäm τ^{−1} ∘ σ ∘ τ