MM2001 · Diskret matematik

Tenta 2025-05-07

Per Alexandersson5 uppgifter

#Uppgift 1

Uppgift 1

(a)

Ge exempel på ett tal som tillhör mängden $\{ x \in \setR : x^2 < x \} \cap \left( \setR \setminus \setQ \right)$.

(b)

Bestäm ett andragradspolynom med reella koefficienter och som har $z = \sqrt{2}-2i$ som ett nollställe.

(c)

Polynomet $P(x) = \sum_{k=0}^{30} 2^k x^{30-k}$ delas med $x-1$. Vad blir resten?

Visa lösningDölj lösning

Första mängden är alla tal mellan $0$ och $1$. Andra mängden är icke-rationella reella tal. Vi vet från kursen att $\sqrt{2}$ inte är rationellt. Vi kan då ta talet $\sqrt{2}/2$ då detta ligger mellan $0$ och $1$ och är ej rationellt. Andra exempel man kan ta är $\pi/4$ och $1/e$.
Vi kan ta $ \left(z-(\sqrt{2}-2i)\right)\left(z-(\sqrt{2}+2i)\right) = z^2 - 2\sqrt{2} + 6. $
Polynomet $P(x)$ är en geometrisk summa, och kan skrivas som \[ P(x) = \sum_{k=0}^{30} x^{30} \left(\frac{2}{x}\right)^k = x^{30} \frac{1-(2/x)^{31}}{1-2/x} = \frac{x^{31}-2^{31}}{x-2}. \] Eftersom $x-1$ har grad 1, är resten en konstant, $a$. Om vi skriver $P(x) = K(x)(x-1) + a$ så gäller det att $P(1)=a$. Formeln ovan ger att \[ a = P(1) = \frac{1-2^{31}}{(1-2)} = 2^{31}-1. \]

#Uppgift 2

Uppgift 2

Chad behöver ägg för att göra årets matlådor. Lokala äggbonden säljer paket med $12$ ägg i varje. Chad vill ha exakt $5$ ägg per matlåda eftersom han går till gymmet varje dag. Han har redan $2$ ägg hemma. Hur många paket ägg ska Chad köpa för att få så många matlådor som möjligt, men antalet matlådor ska inte överstiga $365$? Chad vill inte ha några ägg över efter storkoket. Tips: Modellera problemet som en Diofantisk ekvation.

Visa lösningDölj lösning

Vi vill lösa den diofantiska ekvationen $2+12p = 5m$, där $p$ är antalet paket som Chad vill köpa och $m$ är antalet matlådor. Omskrivning ger oss \[ 12p-5m = -2, \] och vi ser att $p=-1$, $m=-2$ är en lösning. Eftersom $\SGD(12,5)=1$, så är då den allmänna lösningen \[ \begin{cases} p = -1 + 5k \\ m = -2 + 12k \end{cases} \qquad k \in \setZ. \] Slutligen vill vi välja $k$ så stort som möjligt, men med villkoret $-2+12k \leq 365$. Detta ger $k \leq 365/12$ så $k \leq 30$. Detta ger oss $p=149$ och Chad får $m=358$ matlådor.

#Uppgift 3

Uppgift 3

Låt $P(z) = (z-11)(z+9)$ och $Q(z)=z^3 + z^2 + 9 z$. Lös ekvationen $Q(z)=11$ för $z \in \setC$. Finn därefter alla lösningar till polynomekvationen $P(Q(z)) = 0$.

Visa lösningDölj lösning

Ekvationen $Q(z)=11$ leder till \[ z^3 + z^2 + 9 z - 11 =0. \] Rationella rotsatsen säger att rationella rötterna kan vara $\pm 1$ och $\pm 11$. Testar vi $z=1$, har vi en lösning så $(z-1)$ är en faktor. Polynomdivision ger oss \[ z^3 + z^2 + 9 z - 11 = (z-1)(z^2+2z+11). \] Den sista faktorn har nollställena $z = -1 \pm \sqrt{-10}$, så totalt har vi rötterna \[ z_1 = 1, \quad z_2 = -1 + i \sqrt{10}, \quad z_3 = -1 - i \sqrt{10}. \]

För att lösa $P(Q(z)) = 0$ måste vi lösa $(Q(z)-11)(Q(z)+9)=0$. Den första faktorn är noll då $Q(z)=11$, vilket vi redan löst. Vi vill nu lösa \[ z^3 + z^2 + 9 z + 9 = 0. \] Rationella rotsatsen igen leder till att $z = -1$ är en rot. Polynomdivision, \[ z^3 + z^2 + 9 z + 9 = (z+1)(z^2 + 9) \] så vi har de tre ytterligare rötterna $z_4 =-1$, $z_5 = 3i$, $z_6 = -3i$.

#Uppgift 4

Uppgift 4

Givet nollskilt $z \in \setC$, sätt $w = \frac{1}{2}(z + \frac{1}{z})$, som då ligger mitt emellan $z$ och $\frac{1}{z}$.

(a)

Beräkna $w$ för $z=2$, $z=\frac{3+4i}{5}$ och $z=1+2i$.

(b)

Visa att $w$ är ett reellt tal om och endast om $z$ är reellt, eller om $|z|=1$.

Visa lösningDölj lösning

Vi har att $w$ blir (respektive) \[ \frac12(2+\frac12) = \frac{5}{4}, \quad \frac{1}{2}\left(\frac{3+4i}{5}+\frac{5}{3+4i}\right) = \frac35, \quad \frac{1}{2}\left(\frac{5(1+2i)}{5} + \frac{1-2i}{5}\right) = \frac{3+4i}{5}. \] Låt nu $z = re^{it}$. Det räcker att visa att $2w = re^{it} + r^{-1}r^{-it}$ är reelt precis då $t \in \{0,\pi\}$ eller $r=1$. Vi har att imaginärdelen av $2w$ ges av \[ r \sin(t) + r^{-1} \sin(-t) = \sin(t)\left(r - 1/r \right). \] Detta är noll precis då antingen $\sin(t) =0$ (och $t \in \{0,\pi\}$), eller så måste $r=1/r$, vilket ger att $r=1$.

#Uppgift 5

Uppgift 5

De 9 damerna Agda, Berit, Cecilia, Dorotea, Ester, Frideborg, Gerd, Hilda och Ingalill ska organisera syföreningens årsmöte. Agda, Berit och Cecilia kan bara laga huvudrätter. Gerd, Hilda och Ingalill kan bara laga efterrätter. De tre övriga kan laga både huvudrätter och efterrätter.

(a)

Mötet behöver exakt fyra personer som kan laga huvudrätter. På hur många sätt kan dessa utses bland de sex som kan laga huvudrätt?

(b)

Om man nu vill välja en grupp damer där exakt fyra av dem kan laga huvudrätt, och exakt fyra av dem kan laga efterrätt, på hur många sätt kan detta göras? Som exempel: $ \{\mathtt{Berit},\, \mathtt{Dorotea},\, \mathtt{Ester},\, \mathtt{Frideborg},\, \mathtt{Gerd} \} $ utgör ett godkänt urval, då exakt fyra av dessa kan laga huvudrätt och exakt fyra av dem kan laga efterrätt.

(c)

Berit och Gerd vill inte laga mat med Ester; de är rädda för Esters matlagning¹. På hur många sätt kan man nu göra urvalet i (b) där vi undviker att Ester blir vald samtidigt som Berit eller Gerd?

Inget av svaren på (a), (b), (c) överstiger $100$.

Se föregående tenta---Ester har en historik med att råka flambera sina husdjur. ↩

Visa lösningDölj lösning

Det finns sex personer som kan laga huvudrätt, att välja 4 av dem kan göras på $\binom{6}{4} = 15$ sätt.
Damernas expertisområden illustreras nedan:

Vi gör en falluppdelning beroende på hur många som ingår bland $B = \{\mathtt{Ester},\mathtt{Dorotea},\mathtt{Frideborg} \}$. Vi väljer först från $B$, och lägger därefter till damer från $H$ och $E$: \[\begin{aligned} \textbf{En dam från $B$:} &\quad \binom{3}{1} \cdot \binom{3}{3} \cdot \binom{3}{3} = 3, \\ \textbf{Två damer från $B$:}&\quad \binom{3}{2} \cdot \binom{3}{2} \cdot \binom{3}{2} = 27,\\ \textbf{Tre damer från $B$:}&\quad \binom{3}{3} \cdot \binom{3}{1} \cdot \binom{3}{1} = 9. \end{aligned}\] Detta ger totalt $39$ olika val.
Vi gör inklusion--exklusion. Vi räknar först när Ester och Gerd båda ingår. Detta val måste kompletteras med damer från $B$, $H$ och $E$: \[\begin{aligned} \textbf{Ingen dam till från $B$:} &\quad \binom{2}{0} \cdot \binom{3}{3} \cdot \binom{2}{2} = 1, \\ \textbf{En dam till från $B$:} &\quad \binom{2}{1} \cdot \binom{3}{2} \cdot \binom{2}{1} = 12, \\ \textbf{Två damer till från $B$:} &\quad \binom{2}{2} \cdot \binom{3}{1} \cdot \binom{2}{0} = 3. \end{aligned}\] Totalt: $16$ val. På samma sätt så finns det 16 val där både Ester och Agda ingår.

Vi dubbelräknar dock de fall där alla tre (Ester, Agda och Gerd) ingår. Det saknas då två till personer för huvudrätt, och två till för efterrätt (som kan vara samma).

\[\begin{aligned} \textbf{Ingen dam till från $B$:}&\quad \binom{2}{0} \cdot \binom{2}{2} \cdot \binom{2}{2} = 1, \\ \textbf{En dam till från $B$:} &\quad \binom{2}{1} \cdot \binom{2}{1} \cdot \binom{2}{1} = 8, \\ \textbf{Två damer till från $B$:}&\quad\binom{2}{2} \cdot \binom{2}{0} \cdot \binom{2}{0} = 1. \end{aligned}\] Detta ger oss $10$ val där både Ester, Agda och Gerd ingår.

Så med inklusion--exklusion finns det då totalt $ 39 - 2\cdot 16 + 10 = 17 $ olika val där Ester (om hon är med) inte är tillsammans med Agda eller Gerd.
```
(* Med Mathematica, Agda=1, Berit=2, etc *)
Select[
  Subsets[Range[9]],
  Length[Intersection[Range[1, 6], #]] == 4 &&
    Length[Intersection[Range[4, 9], #]] == 4 &&
    Implies[MemberQ[#, 5], ! MemberQ[#, 2] && ! MemberQ[#, 7]] &
  ] // Column
```