Uppgift 1
Bestäm samtliga $x\in\mathbb{Z}$ som uppfyller $10x\equiv2\pmod{2023}$, samt ange hur många av dessa som ligger i intervallet $[3237,5260]$.
MM2001 · Diskret matematik
Tenta 2023-11-22
#Uppgift 1
Visa lösningDölj lösning
Enligt definition gäller kongruensen om och endast om det finns något $y\in\mathbb Z$ sådant att
$$
10x=2+2023y.
$$
Detta är ekvivalent med den diofantiska ekvationen
$$
10x-2023y=2. \tag{*}
$$
Euklides algoritm ger
$$
2023=202\cdot10+3,\qquad 10=3\cdot3+1.
$$
Därmed är $\operatorname{SGD}(2023,10)=1$ och
$$
1=10-3\cdot3=10-3(2023-202\cdot10)=607\cdot10-3\cdot2023.
$$
Alltså är $(x,y)=(2\cdot607,2\cdot3)=(1214,6)$ en lösning till (*). Samtliga $x$-värden är
$$
x=1214+2023k,\qquad k\in\mathbb Z.
$$
Ett sådant $x$ ligger i det givna intervallet om och endast om
$$
3237\le1214+2023k\le5260
\Longleftrightarrow 1\le k\le2.
$$
Det finns alltså två sådana lösningar. Svar: $x=1214+2023k$ för $k\in\mathbb Z$, och precis två av dessa tal ligger i intervallet.
#Uppgift 2
Uppgift 2
Beräkna $\sum_{k=2}^{21}(3\cdot4^k+3^k)$. Svaret får innehålla en hög potens utan att denna beräknas uttryckligen.
Visa lösningDölj lösning
Summan har $20$ termer och kan delas upp enligt
$$
\sum_{k=2}^{21}(3\cdot4^k+3k)
=\sum_{k=2}^{21}3\cdot4^k+\sum_{k=2}^{21}3k.
$$
Den geometriska summan blir
$$
\sum_{k=2}^{21}3\cdot4^k
=3\cdot4^2\left(\frac{4^{20}-1}{4-1}\right)
=4^2(4^{20}-1),
$$
och den aritmetiska summan blir
$$
\sum_{k=2}^{21}3k
=\left(\frac{3\cdot2+3\cdot21}{2}\right)\cdot20
=3\cdot23\cdot10=690.
$$
Alltså är den ursprungliga summan
$$
4^2(4^{20}-1)+690=4^{22}+674.
$$
Svar: $4^{22}+674$.
#Uppgift 3
Uppgift 3
Ett polynom $p(z)$ med komplexa koefficienter ger resten 7 vid division med $(z-2)$ och resten $i$ vid division med $(z-i)$. Bestäm resten vid divisionen av $p(z)$ med $(z-2)(z-i)$.
Visa lösningDölj lösning
Enligt restsatsen är $p(2)=7$ och $p(i)=i$. Om resten vid divisionen är $az+b$, där $a,b\in\mathbb C$, gäller
$$
p(z)=(z-2)(z-i)q(z)+(az+b).
$$
Därför
$$
7=p(2)=2a+b,\qquad i=p(i)=ai+b.
$$
Detta ger $a(2-i)=7-i$, alltså
$$
a=\frac{7-i}{2-i}=3+i.
$$
Därmed är $b=7-2a=1-2i$. Svar: resten är
$$
(3+i)z+(1-2i).
$$
#Uppgift 4
Uppgift 4
Rita följande mängder i det komplexa talplanet:
(a)
$\{z\in\mathbb{C}:\operatorname{Re}(z)+\operatorname{Im}(z)=1\}$
(b)
$\{z\in\mathbb{C}:\lvert z+i\rvert\le1\}\cap\{z\in\mathbb{C}:\operatorname{Re}(z)\le0\}$
(c)
$\{z\in\mathbb{C}:\lvert z-2\rvert=\lvert z-2i\rvert\}$
(d)
$\{2w,2w^2,2w^3,2w^4,2w^5\}$ där $w=e^{2\pi i/5}$.
Visa lösningDölj lösning
(a) Kravet motsvarar att avståndet mellan $z$ och $-i$ är högst $1$ och att realdelen är icke-positiv. Figuren visar mängden.
(b) Kravet motsvarar att avståndet mellan $z$ och $2$ är lika stort som avståndet mellan $z$ och $2i$, alltså bisektrisen till sträckan mellan dessa punkter. Figuren visar mängden.
(c) Figuren visar mängden för den motsvarande geometriska beskrivningen.
(d) $w$ är en punkt på enhetscirkeln med vinkel $2\pi/5$ mot den reella axeln, och $2w$ har samma argument på en cirkel med radie $2$. Varje multiplikation med $w$ lägger till $2\pi/5$ till argumentet. Mängden består därför av punkterna i en regelbunden femhörning, med ett hörn i $z=2=2w^5$.
#Uppgift 5
Uppgift 5
I denna fråga ska svaren vara fullt uträknade, och kom ihåg att motivera fullständigt. Alla svar ligger mellan 200 och 1000.
(a)
På hur många sätt kan sex personer A, B, C, D, E, F stå på kö?
(b)
På hur många sätt kan sex personer A, B, C, D, E, F stå på kö om F inte ska stå sist i kön?
(c)
På hur många sätt kan sex personer A, B, C, D, E, F stå på kö om A och B inte ska stå bredvid/intill varandra?
Visa lösningDölj lösning
Obs: Det finns många sätt att resonera.
(a) Enligt standardsatsen om permutationer av objekt är antalet
$$
6!=6\cdot5\cdot4\cdot3\cdot2\cdot1=720.
$$
(b) Det finns $5$ val för den som står sist. För vart och ett av dessa finns $5$ val för den näst sista, därefter $4$ val för position tre och så vidare. Detta ger
$$
5\cdot5!=600
$$
möjligheter totalt.
(c) Vi tar alla $720$ köordningar och räknar bort dem där $AB$ eller $BA$ förekommer. Det finns $5!=120$ ordningar av vardera sort, nämligen permutationerna av $AB,C,D,E,F$ respektive $BA,C,D,E,F$. Alltså
$$
720-120-120=480.
$$
Svar: (a) $720$, (b) $600$, (c) $480$.
#Uppgift 6
Uppgift 6
(a)
För $a,b\in\mathbb{Z}\setminus\{0\}$, ange definitionen av $\operatorname{SGD}(a,b)$.
(b)
Låt $a,b\in\mathbb{Z}\setminus\{0\}$, och låt $d=\operatorname{SGD}(a,b)$. Bevisa att $\operatorname{SGD}(a/d,b/d)=1$.
Visa lösningDölj lösning
(a) För $(a,b)\ne(0,0)$ definierar vi $\operatorname{SGD}(a,b)$ som det största heltal $d$ som delar både $a$ och $b$. Vi definierar också $\operatorname{SGD}(0,0)=0$.
(b) Låt $c=\operatorname{SGD}(a/d,b/d)$. Per definition gäller då att $c\mid a/d$ och $c\mid b/d$. Alltså finns heltal $m,n$ sådana att
$$
mc=\frac ad,\qquad nc=\frac bd.
$$
Detta är ekvivalent med
$$
mcd=a,\qquad ncd=b.
$$
Alltså är $cd$ en delare till både $a$ och $b$. Men $d$ är den största gemensamma delaren, och därför måste $c\le1$. Eftersom $c$ är positivt följer $c=1$, vilket var det som skulle visas.