MM2001 · Diskret matematik
Blandade frågor.
Finn $\operatorname{SGD}(240,154)$ med Euklides algoritm.
Beräkna resten då $5^{40}$ delas med 11.
Ge exempel på en mängd $A$ sådan att $\lvert A\times A\rvert=9$, där mängden $A\times A$ består av alla ordnade par av element ur mängden $A$.
(a) Euklides algoritm ger
$$
\begin{aligned}
240&=1\cdot154+86,&154&=1\cdot86+68,\\
86&=1\cdot68+18,&68&=3\cdot18+14,\\
18&=1\cdot14+4,&14&=3\cdot4+2,\\
4&=2\cdot2.
\end{aligned}
$$
Den sista icke-nollresten är $2$. Alltså är $\operatorname{SGD}(240,154)=2$.
(b) Vi räknar modulo $11$. Eftersom $5^5=3125\equiv1\pmod{11}$ får vi
$$
5^{40}=(5^5)^8\equiv1^8\equiv1\pmod{11}.
$$
Resten är alltså $1$.
(c) För en ändlig mängd gäller $|A\times A|=|A|^2$. Vi behöver därför $|A|=3$. Ett exempel är $A=\{1,2,3\}$. Då har $A\times A$ precis $3\cdot3=9$ element.
Logik och mängdlära.
Avgör om följande påstående är sant eller falskt för $x,y\in\mathbb{R}$: $\forall x\,\exists y\,(x^2+y=10)$. Motivera noga.
Låt $A,B,C$ vara mängder. Visa att $(A\setminus B)\setminus C=A\setminus(B\cup C)$ genom att använda mängdlärans definitioner.
(a) Påståendet
$$
\forall x\ \exists y\,(x^2+y=10)
$$
är sant. Låt $x\in\mathbb R$ vara godtyckligt och välj $y=10-x^2$. Då är $y\in\mathbb R$ och $x^2+y=x^2+(10-x^2)=10$. Det finns alltså ett sådant $y$ för varje reellt $x$.
(b) Vi visar att ett godtyckligt element $x$ tillhör vänsterledet om och endast om det tillhör högerledet:
\[
\begin{aligned}
x\in(A\setminus B)\setminus C
&\Longleftrightarrow x\in A\setminus B\text{ och }x\notin C\\
&\Longleftrightarrow x\in A,\ x\notin B\text{ och }x\notin C\\
&\Longleftrightarrow x\in A\text{ och }x\notin(B\cup C)\\
&\Longleftrightarrow x\in A\setminus(B\cup C).
\end{aligned}
\]
Eftersom detta gäller för varje $x$ följer att $(A\setminus B)\setminus C=A\setminus(B\cup C)$.
Polynom.
Visa att $x-1$ är en faktor i $p(x)=x^4-3x^3+x^2+3x-2$ och finn samtliga reella nollställen.
Bestäm ett reellt polynom $q(x)$ av lägsta möjliga grad som har nollställen i $x=2$ och $x=i$.
(a) Först beräknar vi
$$
p(1)=1-3+1+3-2=0.
$$
Enligt faktorsatsen är därför $x-1$ en faktor. Polynomdivision ger
$$
p(x)=(x-1)(x^3-2x^2-x+2).
$$
Kubiken faktoriseras genom gruppering:
$$
\begin{aligned}
x^3-2x^2-x+2
&=x^2(x-2)-(x-2)\\
&=(x^2-1)(x-2)\\
&=(x-1)(x+1)(x-2).
\end{aligned}
$$
Alltså är
$$
p(x)=(x-1)^2(x+1)(x-2).
$$
De reella nollställena är därför $x=-1$, $x=1$ och $x=2$, där $x=1$ är ett dubbelt nollställe.
(b) Eftersom $q$ har reella koefficienter och $i$ är ett nollställe måste även det komplexkonjugerade talet $-i$ vara ett nollställe. Ett polynom av lägsta möjliga grad har därför faktorerna
$$
(x-2)(x-i)(x+i)=(x-2)(x^2+1).
$$
Vi kan alltså välja
$$
q(x)=(x-2)(x^2+1)=x^3-2x^2+x-2.
$$
Absolutbelopp.
Lös ekvationen $\lvert x-1\rvert+\lvert 2x+4\rvert=6$ för $x\in\mathbb{R}$.
Lös olikheten $\lvert 3x-2\rvert<5$.
(a) Teckenbyten sker vid $x=-2$ och $x=1$. Vi behandlar tre intervall.
Om $x<-2$ är
$$
|x-1|+|2x+4|=(1-x)+(-2x-4)=-3x-3.
$$
Ekvationen $-3x-3=6$ ger $x=-3$, vilket ligger i intervallet.
Om $-2\le x<1$ är
$$
|x-1|+|2x+4|=(1-x)+(2x+4)=x+5.
$$
Ekvationen $x+5=6$ ger $x=1$. Detta är randpunkten; direkt insättning visar att $x=1$ uppfyller den ursprungliga ekvationen.
Om $x\ge1$ är
$$
|x-1|+|2x+4|=(x-1)+(2x+4)=3x+3.
$$
Ekvationen $3x+3=6$ ger $x=1$, vilket är tillåtet. Alltså är lösningarna $x=-3$ eller $x=1$.
(b) Definitionen av absolutbelopp ger
$$
-5<3x-2<5.
$$
Adderar vi $2$ i alla led får vi $-3<3x<7$, och division med $3$ ger
$$
-1<x<\frac73.
$$
Kombinatorik.
Hur många unika ord med 6 bokstäver kan bildas av bokstäverna i ”KOKOS”?
En kommitté på 4 personer ska väljas från en grupp av 6 män och 5 kvinnor. Hur många sådana kommittéer kan bildas om den måste innehålla minst två kvinnor?
(a) Som uppgiften är skriven finns en motsägelse: ordet ”KOKOS” innehåller endast fem bokstäver. Om varje förekomst i ”KOKOS” får användas högst en gång går det därför inte att bilda ett ord med sex bokstäver; den bokstavliga tolkningen ger $0$.
Den sannolikt avsedda frågan är hur många unika ord med fem bokstäver som kan bildas av bokstäverna i ”KOKOS”. Då finns två K, två O och ett S. Antalet olika permutationer är
$$
\frac{5!}{2!\,2!}=\frac{120}{4}=30.
$$
(b) Vi delar upp efter antalet kvinnor.
Exakt två kvinnor och två män ger
$$
\binom52\binom62=10\cdot15=150.
$$
Exakt tre kvinnor och en man ger
$$
\binom53\binom61=10\cdot6=60.
$$
Exakt fyra kvinnor ger
$$
\binom54\binom60=5\cdot1=5.
$$
Totalt får vi $150+60+5=215$.
Summor.
Visa med induktion att $\sum_{k=1}^{n}(2k-1)=n^2$ för alla $n\ge1$.
Formulera de induktionsantaganden som används i detalj.
(a) Vi visar med induktion att
$$
\sum_{k=1}^{n}(2k-1)=n^2
$$
för alla $n\ge1$.
Basfall: För $n=1$ är
$$
\sum_{k=1}^{1}(2k-1)=2\cdot1-1=1=1^2.
$$
Påståendet gäller alltså för $n=1$.
Induktionsantagande: Antag att påståendet gäller för ett godtyckligt men fixerat heltal $n\ge1$, det vill säga
$$
\sum_{k=1}^{n}(2k-1)=n^2.
$$
Induktionssteg: Då får vi
$$
\begin{aligned}
\sum_{k=1}^{n+1}(2k-1)
&=\sum_{k=1}^{n}(2k-1)+2(n+1)-1\\
&=n^2+2n+1\\
&=(n+1)^2,
\end{aligned}
$$
där induktionsantagandet användes i den andra raden. Alltså gäller påståendet även för $n+1$. Enligt induktionsprincipen gäller därför formeln för alla $n\ge1$.
(b) Det induktionsantagande som används ovan är: För ett godtyckligt men fixerat $n\ge1$ antar vi att
$$
\sum_{k=1}^{n}(2k-1)=n^2.
$$
Detta antagande används sedan för att visa motsvarande formel för $n+1$.