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

Satsen är sant för n = 3: 9 − 6 − 1 > 0.

Antag att satsen gäller för varje 3 ≤ n ≤ k och visa att satsen är sant för n = k + 1.

(k + 1)^{2} − 2(k + 1) − 1 = [k^{2} − 2k − 1] + [2k − 1] > 0 + 5 > 0

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

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

Enligt binomialsatsen:

(7 + 1)^{30} = ∑_{i=0}^{30} \binom{30}{i}7^{i}

Man ska lösa 8^{30} = x^{90} = (x^{3})^{30}. Det följer att x^{3} = 8 och så x = 2.

(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} )

G_{1} har en nod med grad 3 och alla noder i G_{2} har grad 2. Grafer kan inte vara isomorfa.

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

σ = [3547216], τ = [1243657]

(a) σ = (13476)(25), τ = (34)(56).

(b) σ^{−1} = (16743)(25).

(c) τ ∘ σ^{−1} = (152673)

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

15 = 2^{4} − 1, så kan man skriva en Hamming kod med r = 4. Matrisen M har 4 rader och 15 kolumner, som består av alla ickenoll sekvenser av 4 element i ℤ_{2}:

M = [ \begin{matrix}1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \end{matrix} ]

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. Man ska visa att a ∗ b ∈ S för alla a, b ∈ S. a ∗ b ∈ ℝ och a ∗ b ≠ −1. Om a ∗ b = a + b + ab = −1 då gäller a ∗ b = a + b + ab + 1 = (b + 1)(a + 1) = 0. Det följer att a = −1 eller b = −1 som är omöjligt, a, b ∈ S.

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

• (G1)

(a ∗ b) ∗ c = (a + b + ab) + c + (a + b + ab)c = a + b + c + ab + ac + bc + abc

a ∗ (b + c) = a + (c + b + cb) + a(c + b + cb) = a + b + c + ab + ac + bc + abc • (G2) identitetet är 0:

0 ∗ a = a ∗ 0 = a + 0 + a · 0 = a

• (G3) inversen av elemntet a är ett element x så att

a ∗ x = x ∗ a = a + x + ax = 0

Det följer att x = \frac{−a}{a+1} ≠ −1, dvs x ∈ S.

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

Man ska lösa ekvationen 12x + 4 = 0. Lösningar är x = −\frac{1}{3}.

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

gång.

Jämna heltal slutar med en jämn siffra, 0, 2, 4, 6, 8. Vi ska beräkna antalet sätt att välja 6 siffror, utan upprepning när

• första siffran kan väljas bland 1, ..., 9

• följande 4 kan väljas bland 0 och 9

• sista kan väljas bland 0, 2, 4, 6, 8. Det är lättare att dela upp alternativen i två grupper:

(a) heltal som slutar med 0

(b) heltal där sista siffran är skild från 0. Enligt multiplikations principen finns det 9 · 8 · 7 · 6 · 5 = 15120 element i första gruppen.

För att beräkna antalet element i andra gruppen börjar vi på sista siffran (där vi har 4 olika alternativ) och sedan fortsätter vi från första siffran. Så det finns 4 · 8 · 8 · 7 · 6 · 5 = 53760 många alternativ.

Totalt har vi 53760 + 15120 (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?

Låt A = {σ ∈ S_{10} som börjar med en trea } och B = {σ ∈ S_{10} som slutar med an sjua }. Vi ska räkna kardilalitetet av unionen:

|A ∪ B| = |A| + |B| − |A ∩ B|

|A| = |B| = 9! och |A ∩ B| = 8! Svaret är 9! + 9! − 8! = 685440.

(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
f ∘ g = 103(ax + b) + 173 = g ∘ f = a(103x + 173) + b

Det följer att 103ax + 103b + 173 = 103ax + 173a + b, så:

173a − 102b = 173

En lösning är (a, b) = (1, 0). Den mcm(102, 173) = 173 · 102. Det följer att den allmänna lösning blir: (a, b) = (1 + 102k, 173k) där k ∈ ℤ.