Uppgift 1
Bestäm samtliga lösningar till den diofantiska ekvationen $221x+391y=51$.
MM2001 · Diskret matematik
Tenta 2023-10-20
#Uppgift 1
Visa lösningDölj lösning
Vi börjar med att beräkna $\operatorname{SGD}(221,391)$ via Euklides algoritm:
$$
391=221+170,\quad 221=170+51,\quad 170=3\cdot51+17,\quad 51=3\cdot17.
$$
Alltså är $\operatorname{SGD}(221,391)=17$. Den ursprungliga diofantiska ekvationen är därför ekvivalent med
$$
13x+23y=3. \tag{*}
$$
Enligt satsen om diofantiska ekvationer är lösningarna, om $(x_0,y_0)$ är en partikulärlösning,
$$
x=x_0-23k,\qquad y=y_0+13k,\qquad k\in\mathbb Z.
$$
Vi ser att $(x,y)=(2,-1)$ är en lösning. Samtliga lösningar ges alltså av
$$
x=2-23k,\qquad y=-1+13k,\qquad k\in\mathbb Z.
$$
#Uppgift 2
Uppgift 2
Lös olikheten $\frac{1}{4x+5}<\frac{1}{(x+1)(x+3)}$.
Visa lösningDölj lösning
Vi använder ett teckenstudium. Först skriver vi om olikheten:
$$
\frac1{4x+5}<\frac1{(x+1)(x+3)}
\Longleftrightarrow
\frac{(x+1)(x+3)-(4x+5)}{(4x+5)(x+1)(x+3)}<0,
$$
det vill säga
$$
\frac{x^2-2}{(4x+5)(x+1)(x+3)}
=\frac{(x-\sqrt2)(x+\sqrt2)}{(4x+5)(x+1)(x+3)}<0. \tag{*}
$$
Uttrycket i vänsterledet i (*) är en produkt av fem faktorer. Brytpunkterna är
$$
-3<-\sqrt2<-\frac54<-1<\sqrt2<2.
$$
(Vi vet att $-\sqrt2<-\frac54$ eftersom $(\frac54)^2=\frac{25}{16}<2$.) För $x>2$ är uttrycket positivt, och tecknet alternerar när vi passerar en brytpunkt. Ingen brytpunkt löser olikheten. Därför är lösningen
$$
x\in(-\infty,-3)\cup(-\sqrt2,-\tfrac54)\cup(-1,\sqrt2).
$$
#Uppgift 3
Uppgift 3
Bestäm samtliga lösningar $z\in\mathbb{C}$ till ekvationen $(z-(1+i))^4=16$ och bestäm hur många av lösningarna som uppfyller $\operatorname{Re}(z)<0$.
Visa lösningDölj lösning
Vi skriver $u=z-(1+i)$ och löser först $u^4=16=2^4e^{i\cdot0}$. Enligt satsen om binomiska ekvationer är lösningarna
$$
u=2e^{i\pi k/2},\qquad k=0,1,2,3,
$$
det vill säga $u=2$, $u=2i$, $u=-2$ eller $u=-2i$. Eftersom $z=(1+i)+u$ får vi
$$
z\in\{3+i,\ 1+3i,\ -1+i,\ 1-i\}.
$$
Endast $z=-1+i$ har $\operatorname{Re}(z)<0$. Svar: ekvationen är ekvivalent med denna mängd lösningar, och endast $z=-1+i$ har negativ realdel.
#Uppgift 4
Uppgift 4
Polynomet $p(z)=z^4-2z^3+9z^2-8z+20$ har $z=2i$ som en rot. Bestäm polynomets samtliga rötter i $\mathbb{C}$.
Visa lösningDölj lösning
Eftersom $p(z)$ endast har reella koefficienter medför $p(2i)=0$ att $p(-2i)=0$, enligt konjugatrotssatsen. Därför är $(z-2i)(z+2i)=z^2+4$ en faktor till $p(z)$. Polynomdivision ger
$$
z^4-2z^3+9z^2-8z+20=(z^2+4)(z^2-2z+5).
$$
Faktorn $z^2-2z+5$ har enligt pq-formeln rötterna $z=1\pm2i$. Rötterna till $p(z)$ är alltså $\pm2i$ och $1\pm2i$.
#Uppgift 5
Uppgift 5
En standardkortlek består av 52 kort i fyra olika färger, med 13 valörer per färg. En pokerhand består av fem olika kort.
(a)
Bestäm antalet pokerhänder. Ditt svar får endast innehålla heltal och de fyra vanliga räknesätten.
(b)
Bestäm antalet pokerhänder som innehåller tre kort av en valör och två kort av en annan valör. Ditt svar ska ges som ett uttryckligt heltal. Till exempel är $8\clubsuit ,8\heartsuit ,8\spadesuit ,4\clubsuit ,4\diamondsuit $ en sådan hand, som består av tre kort med valören 8 och två kort med valören 4.
Visa lösningDölj lösning
(a) Detta är
$$
\binom{52}{5}
$$
enligt definitionen av binomialkoefficienter. Med formeln för binomialkoefficienter får vi
$$
\binom{52}{5}=\frac{52\cdot51\cdot50\cdot49\cdot48}{5\cdot4\cdot3\cdot2\cdot1}.
$$
(b) Det finns $13$ sätt att välja valören som ska förekomma två gånger, och för vart och ett av dessa finns $\binom42$ sätt att välja vilka färger valören ska förekomma i. Därefter finns $12$ sätt att välja valören som ska förekomma tre gånger, och för varje sådant val $\binom43$ sätt att välja färgerna. Enligt multiplikationsprincipen blir antalet
$$
13\binom42\,12\binom43=13\cdot6\cdot12\cdot4=3744.
$$
#Uppgift 6
Uppgift 6
(a)
För $d,n\in\mathbb{Z}$, ange definitionen av att $d\mid n$.
(b)
Bevisa att det för varje heltal $n$ gäller att $4\mid n^2$ eller $4\mid(n^2-1)$.
Visa lösningDölj lösning
(a) För heltal $d$ och $n$ skriver vi $d\mid n$ om det finns ett heltal $m$ sådant att $n=dm$.
(b) Låt $n$ vara ett heltal. Enligt divisionsalgoritmen kan vi skriva $n=2k+r$ där $r\in\{0,1\}$.
Om $r=0$, det vill säga om $n$ är jämnt, får vi $n^2=4k^2$, och därmed $4\mid n^2$.
Om $r=1$, det vill säga om $n$ är udda, får vi
$$
n^2-1=(2k+1)^2-1=4(k^2+k),
$$
och därmed $4\mid(n^2-1)$. Oavsett värdet på $r$ gäller alltså att $4\mid n^2$ eller $4\mid(n^2-1)$.