KTH Matematik

Tentamen i 5B1118 Diskret Matematik 5p. Augusti, 2004

• Tillåtna hjälpmedel: Miniräknare med sifferdisplay.

• Väl motiverade svar krävs!

• För godkänt (=Betyg 3) fordras minst 18 poäng, för betyg 4 minst 23 poäng och för betyg 5 minst 30 poäng.

DEL A, 3p per uppgift.

(1) (3p) Visa med hjälp av induktion att:

n^{2} − 2n − 1 > 0 för n ≥ 3

(2) (3p) Bestäm talet x om

∑_{i=0}^{30} \binom{30}{i}7^{i} = x^{90}.

(3) (3p) Bestäm om grafer G_{1}, G_{2} med följande incidensmatriser är isomorfa.

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

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

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

σ = [3547216], τ = [1243657]

(a) Skriv σ, τ på cykelform.

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

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

(5) (3p) Skriv checkmatrisen av en kod av längd 7 som rättar precis ett fel.

DEL B, 5p per uppgift.

(6) (5p) Låt S = {a ∈ ℝ så att a ≠ −1}. Betrakta den följande operationen ∗:

a ∗ b = a + b + ab

(a) Visa att ∗ är en binära operation på S.

(b) Visa att (S, ∗) är en grupp.

(c) Bestäm lösningen av 2 ∗ x ∗ 3 = 7 i S.

(7) (5p) Bestäm antalet 6 siffriga jämna heltal om ingen siffra förekommer mer än en gång.

(8) (5p) Hur många permutationer av siffrorna 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 börjar med en trea eller slutar med an sjua?

(9) (5p) Betrakta de följande funktioner f, g : ℝ → ℝ:

f(x) = 103x + 173, g(x) = ax + b

där a, b ∈ ℤ. Bestäm alla värden på a och b för vilka:

f ∘ g = g ∘ f