KTH Matematik

Tentamen i 5B1118 Diskret Matematik 5p. 24 Maj, 2004

• Skrivtid: 8:00-13:00.

• 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) Hitta alla positiva heltal m, n som uppfyller

15m + 30n = 45

(2) (3p) Hur många arrangemang av bokstäverna i ordet MATEMATIK finns det? Hur många av dessa innehåller inte sekvensen “AA”?

(3) (3p) Låt G = (V, E) vara en enkel graf. Bestäm |V | om G har 12 kanter och varje nod har grad 4. Rita en geometrisk representation av G.

(4) (3p) Betrakta funktionen:

f : ℤ_{+} × ℤ_{+} → ℚ_{+}; f(m, n) = \frac{m}{n}

(a) Är f surjektiv?

(b) Är f bijektiv?

(5) (3p) Givet ett RSA-system med krypteringsnyckel n = 77 och e = 7. Dekryptera meddelandet 3.

DEL B, 5p per uppgift.

(6) (5p) Betrakta den fullständiga bipartita grafen K_{m,n}.^{1} (a) For vilka värden på m och n är K_{m,n} en Eulergraf?

(b) Välj att par m, n sådan att K_{m,n} är en Eulergraf och rita en Eulerkrets.

(c) Finns det något par m, n sådan att K_{m,n} inte är en Eulergraf, men har en Eulerväg?

(7) (5p)

(a) Visa att om a, b ∈ ℤ_{n} är inverterbara^{2} då är ab och b^{−1} inverterbara. ( b^{−1} betecknar multiplikativa inversen av b).

(b) Låt G = {a ∈ ℤ_{32} sådan att a är inverterbart}. Bestämm alla elementerna i G.

(c) Är (G, ·) en grupp? (multiplicationen · är multiplicationen modulo 32).

(8) (5p) Visa att grupperna (ℤ_{4}, +) och (ℤ_{2} × ℤ_{2}, +) är inte isomorfa.

(9) (5p) Bestäm antalet permutationer σ ∈ 𝕊_{5} som uppfyller:

σ ≠ id och σ^{2} = id.

1Grafen har m + n noder, uppdelad i två mängder V_{1}, V_{2} med m respektive n element, där kanter förbinder varje nod i V_{1} med varje nod i V_{2}, men inga kanter går mellan två noder i V_{1} och inga mellan två noder i V_{2}

2Med avseende på multiplicationen.