MM2001 · Diskret matematik

Tenta 2024-04-17

#Uppgift 1

Uppgift 1

(a)

Skriv ned tre olika tal som ingår i mängden $ \left\{ x \in \setN : \left(\exists y \in \setN : x= y^2 \right) \right\}. $

(b)

Bestäm vilken rest som fås då $5^{31}$ delas med $26$.

(c)

Formulera rationella rotsatsen och lista alla rationella tal som enligt satsen skulle kunna vara rötter till polynomet $15 x^6-100x^4+2$.

Visa lösningDölj lösning

Mängden består av alla naturliga tal på formen $y^2$, så $\{1,4,9\}$ är tre sådana tal.
$5^{31} = 5\cdot 5^{30} = 5\cdot 25^{15}$ och eftersom $25 \equiv_{26} -1$, får vi $5 \cdot (-1)^{15} =-5$, som är kongruent med $21$ modulo $26$. Alltså är resten $21$.
En rationell rot $\frac{a}{b}$ till ett polynom med heltalskoefficienter, med ledande koefficient $c_n$ och konstantterm $c_0$ uppfyller att $a \mid c_0$ samt $b \mid c_n$. Vi söker då $a$ och $b$ så att $a \mid 2$ och $b \mid 15$. Detta leder till att de rationella rötterna $\frac{a}{b}$ (om sådana finns) är bland talen \[ \pm \frac{1}{1}, \pm \frac{1}{3}, \pm \frac{1}{5}, \pm \frac{1}{15}, \pm \frac{2}{1}, \pm \frac{2}{3}, \pm \frac{2}{5}, \pm \frac{2}{15}. \]

#Uppgift 2

Uppgift 2

För ett heltal $a$, betrakta den diofantiska ekvationen $ 170x + 289 y = a. $

(a)

Bestäm det minsta positiva heltal $a$ som gör att ekvationen har lösningar.

(b)

Bestäm två olika lösningar till ekvationen $170x + 289 y=17$.

Visa lösningDölj lösning

Den diofantiska ekvationen har en lösning om och endast om $\SGD(170,289) \mid a$, enligt utlärd sats. Vi kan med Euklides algoritm beräkna $\SGD(170,289)$: \[\begin{aligned} 289 &= 170 + 119 \\ 170 &= 119 + 51 \\ 119 &=2\cdot 51 + 17 \\ 51 &= 3\cdot 17 + 0. \end{aligned}\] Så största gemensamma delaren är $17$. Alltså finns det en lösning omm $17 \mid a$, och det minsta positiva värdet på $a$ som uppfyller detta är $a=17$.
Genom division med $17$ ser vi att ekvationen är ekvivalent med \[ 10x + 17 y = 1. \] Vi vet sedan tidigare att $17\cdot 3 = 51$, så $10(-5) + 17\cdot 3 = 1$. En lösning är då $(x,y) = (-5, 3)$. Alla andra lösningar skiljer sig från denna, enligt utlärd sats, med heltalsmultiplar av $(17,-10)$; dvs, den allmänna lösningen ges av \[ (x,y) = (-5, 3) + k(17, -10) \quad\text{där $k \in \mathbb{Z}$}. \] Alltså fås en till lösning av $(x,y) = (-5,3) + (17, -10) = (12, -7)$.

Svar: $(x,y) = (-5,3)$ eller $(12, -7)$ är två lösningar.

#Uppgift 3

Uppgift 3

Finn alla reella lösningar till olikheten $\frac{2}{x-2}+\frac{8}{(x-3)^2} \geq 0$.

Visa lösningDölj lösning

Vi skriver om på gemensam nämnare: \[ \frac{2(x-3)^2+ 8(x-2)}{(x-2)(x-3)^2} \geq 0. \] Vi utvecklar och förenklar täljaren till $2(x-1)^2$, så olikheten kan skrivas \[ \frac{2(x-1)^2}{(x-2)(x-3)^2} \geq 0. \] Uttrycket är endast definierat då $x \notin \{2, 3\}$. Alla faktorer är dessutom större eller lika med $0$ förutom $(x-2)$, som endast är positiv då $x>2$. Alltså ser vi att olikheten gäller precis när $x=1$, eller då $x>2$ men $x \neq 3$. Svar: Olikheten gäller precis när $x=1$, $2<x<3$ eller $x>3$.

#Uppgift 4

Uppgift 4

(a)

Kvadratkomplettera uttrycket $z^2-(6+4 i) z+ (5 + 10 i)$.

(b)

Lös ekvationen $z^2-(6+4 i) z+ (5+10i)=0$, för $z \in \setC$.

Visa lösningDölj lösning

Uttrycket kvadratkompletteras till \[\begin{aligned} \bigl(z - (3+2i) \bigr)^2 - \bigl(3+2i \bigr)^2 + (5+10i) &= \bigl(z - (3+2i) \bigr)^2 - (5+12i) + (5+10i) \\ &= \bigl(z - (3+2i) \bigr)^2 - 2i. \end{aligned}\]
Vi kan enligt del (a) skriva om ekvationen som \[ \bigl(z - (3+2i) \bigr)^2 = 2i \iff w^2 = 2i \] där $w = z - (3+2i)$.

Vi kan lösa $w^2 = 2i$ via polär form eller via direkt beräkning i rektangulär form. I polär form: \[ w^2 = 2i \iff w^2 = 2 e^{\pi i/2} \iff w = \sqrt{2} e^{i \left(\tfrac{\pi}{4} + k\pi\right)} \text{ för $k \in \{ 0, 1 \}$} \iff w = \pm(1+i), \] eftersom $e^{\pi i/4} = \cos(\pi/4) + i \sin(\pi/4) = \tfrac{1}{\sqrt{2}} + \tfrac{1}{\sqrt{2}}i$.

I rektangulär form: om vi skriver $w=a+ib$ så är $w^2 = (a^2 - b^2) + 2abi$, så $w^2 = 2i$ gäller om och endast om $a^2-b^2=0$, $ab=1$, samt $a^2+b^2=2$ (genom att titta på absolutbelopp). Detta är ekvivalent med att $a^2=1$ och $a=b$, så $a=b=\pm 1$. Alltså, $w = \pm (1+i)$.

Alltså gäller ekvationen om och endast om \[ z= (3+2i)\pm (1+i), \] så lösningarna är $z = 4+3i$ och $z = 2+i$.

#Uppgift 5

Uppgift 5

(a)

Bestäm ett uttryck för summan $k + 2k + 3k + \dotsb + mk$, där $m$ och $k$ är positiva heltal.

(b)

Bestäm summan av alla tal i tabellen nedan: \[ \begin{array}{cccccc} 1 & 2 & 3 & 4 & \dots & 20 \\ 2 & 4 & 6 & 8 & \dots & 40 \\ 3 & 6 & 9 & 12 &\dots & 60 \\ \vdots & \vdots & \vdots & \vdots &\ddots & \vdots \\ 20 & 40 & 60 & 80 & \dots & 400. \end{array} \] Varje rad och kolonn i tabellen utgör en aritmetisk talföljd.

Visa lösningDölj lösning

Enligt satsen om summan av en aritmetisk talföljd är summan \[ k(1+2+3+\dotsb+m) = k\cdot \frac{m(m+1)}{2}.\]
Rad nummer $k$ i tabellen har summan $k(1+2+3+\dotsb+20) = k \cdot 210$. Om vi summerar detta från rad $k=1$ till rad $k=20$ får vi \[ 1\cdot 210 + 2\cdot 210 + \dotsb + 20\cdot 210 = 210(1+2+3+\dotsb + 20) = 210^2 = 44100. \]

#Uppgift 6

Uppgift 6

I denna fråga ska samtliga svar anges som heltal eller produkter av heltal. Inget svar är större än 1500. Alla svar ska motiveras. Vi har sju personer. Tre av dessa ska få en rolig hatt. Fyra av dessa ska få en rolig halsduk. Samma person kan få både hatt och halsduk och det är ingen skillnad på hattarna, och ingen skillnad på halsdukarna.

(a)

På hur många sätt kan de tre personerna med rolig hatt utses?

(b)

På hur många sätt kan både hattar och halsdukar fördelas?

(c)

Om exakt två personer ska få både hatt och halsduk när accessoarerna fördelas, på hur många sätt kan då alla hattar och halsdukar fördelas?

Visa lösningDölj lösning

Bland de 7 ska tre hatt-personer väljas: $\binom{7}{3} = \frac{7\cdot 6 \cdot 5}{3!} = 35$ sätt.
Vi delar ut halsdukarna oberoende av hatt-utdelningen, så multiplikationsprincipen ger $\binom{7}{3} \binom{7}{4} = 35^2 = 1225$ antal sätt.
Vi väljer först 2 personer som får båda accessoarerna: $\binom{7}{2} = 21$ sätt. Bland de $5$ som är kvar, ska en till få hatt, vilket går på $\binom{5}{1} = 5$ sätt. Slutligen ska två av de $4$ kvarvarande personerna få halsdukar, och det finns $\binom{4}{2}=6$ val för dessa. Eftersom antalet val vid varje steg är oberoende av valen dessförinnan, så finns det enligt multiplikationsprincipen totalt $21\cdot 5\cdot 6 = 630$ olika sätt.