MM2001 · Diskret matematik

Tenta 2024-11-20

#Uppgift 1

Uppgift 1

Lös följande problem.

(a)

Bestäm det minsta positiva heltalet $A$, som gör att den Diofantiska ekvationen $ Ax - 143y = 1 $ inte går att lösa.

(b)

Avgör om påståendet nedan är sant eller inte: \[ \forall y \in \setR \; \exists x \in \setR \; : \; x^3+y^2x-y + 100000=0. \]

(c)

Om man ska visa identiteten $\displaystyle \sum_{k=0}^n (k+1)\cdot 2^k = 1+n\cdot 2^{n+1}$ för $n \geq 0$ med induktion behövs ett basfall. Vad är basfallet? Om formeln ovan för ett visst $n$ är induktionsantagandet, vilket påstående vill man därefter visa?

Visa lösningDölj lösning

Vi har att $143 = 11 \cdot 13$, och ekvationen saknar lösning om $\SGD(A,11\cdot 13) \neq 1$. Detta sker om $A = 11$, men inte för något mindre $A$.
För varje värde på $y$, så får vi en tredjegradsekvation med reella koefficienter. Sådana tredjegradare har alltid en reell rot, $x$, så påståendet är sant.
Basfallet är att verifiera identiteten för $n=0$, dvs. att $(0+1)\cdot 2^{0} = 1+0\cdot 2^{0+1}$. Om formeln ovan är induktionsantagandet, så måste vi visa formeln för nästa värde på $n$, så vi vill visa att \[ \sum_{k=0}^{n+1} (k+1)\cdot 2^k = 1+(n+1)\cdot 2^{n+2}. \]

#Uppgift 2

Uppgift 2

Formulera binomialsatsen. Bestäm därefter koefficienten för $z^{9}$ i polynomet $\left(\frac{1}{16} + (1+i\sqrt{3})z \right)^{12}$.

Visa lösningDölj lösning

Binomialsatsen säger att $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$.

Enligt binomialsatsen har vi att \[ \left(\frac{1}{16} + (1+i\sqrt{3})z \right)^{12} = \sum_{k=0}^{12} \binom{12}{k} 16^{-(12-k)} (1+i\sqrt{3})^k z^k, \] och vi söker koefficienten som motsvarar $k=9$. Genom att skriva om $1+i\sqrt{3}$ på polär form, får vi att koefficienten som sökes är \[ \binom{12}{9} 16^{-3} \left( 2 \cdot e^{\pi i / 3}\right)^9 = \frac{12\cdot 11\cdot 10}{3\cdot 2\cdot 1} \cdot \frac{2^9}{2^{12}} \cdot e^{3 \pi i} = -\frac{55}{2}. \]

#Uppgift 3

Uppgift 3

Finn alla komplexa lösningar till ekvationen $x^2+(4-6 i) x- (5+10 i)=0$.

Visa lösningDölj lösning

Vi kvadratkompletterar: \[\begin{aligned} \left( x+2-3i \right)^2 &= (5+10i) + (2-3i)^2 \\ &= -2i. \end{aligned}\] Vi söker nu $a+bi$ så att $(a+bi)^2 = -2i$. Utvecklar vi kvadraten och jämför absolutbelopp, real- och imaginärdel, får vi \[ a^2+b^2=2,\quad a^2-b^2=0, \quad \text{samt} \quad 2ab = -2. \] De två första ekvationerna ger $a = \pm 1$, och med andra ekvationen får vi de två lösningarna \[ a+bi = -1+i, \qquad a+bi = 1-i. \] Eftersom $x + 2-3i = a+bi$, får vi att lösningarna är $x_1 = -1+2i$, $x_2 = -3+4i$.

#Uppgift 4

Uppgift 4

Bestäm alla $x\in\setR$ som löser ekvationen $|x(x-1)| = 2|(x-1)(x+2)|$.

Visa lösningDölj lösning

Vi ser att uttrycken inom absolutbeloppen byter tecken vid $x\in \{-2,0,1\}$. Detta delar upp den reella talaxeln i fyra fall:

Fall 1: $x<-2$. Ekvationen blir \[ x(x-1) = 2(x-1)(x+2) \iff (x-1)(2x+4-x) = 0 \iff x \in \{1, -4\}. \] Bara roten $x_1 = -4$ ligger inom intervallet.

Fall 2: $-2 \leq x<0$. Ekvationen blir \[ x(x-1) = -2(x-1)(x+2) \iff (x-1)(2x+4+x) = 0 \iff x \in \{1, -\tfrac43 \}. \] Bara roten $x_1 = -\frac43$ är inom intervallet.

Fall 3: $0\leq x < 1$. Detta ger samma ekvation (och rötter) som i Fall 2, och vi får inga rötter inom intervallet.

Fall 4: $x\geq 1$. Vi får samma ekvation som i Fall 1, men denna gång ligger $x_3=1$ inom intervallet.

Lösningarna är $x = -4$, $x = -\frac{4}{3}$ samt $x = 1$.

#Uppgift 5

Uppgift 5

Kjell Andersson, Kjell Bertilsson, Kjell Carlsson, Kjell Davidsson och Kjell Eriksson har gått ned i källaren för att kjell-sortera. På hur många sätt kan de 5 stå i kö,

(a)

utan några extra villkor?

(b)

så att Carlsson står någonstans mellan Andersson och Eriksson (men inte nödvändigtvis direkt intill någon av dessa)?

(c)

så att Andersson inte är först och Bertilsson inte står direkt bakom Andersson?

Alla svar ska anges som heltal.

Visa lösningDölj lösning

De är 5 personer, så det finns $5!=120$ olika köer.
Placera först Bertilsson: $5$ olika alternativ. Därefter Davidsson: $4$ alternativ. På de tre tomma platserna, sätt Carlsson i mitten. Därefter, har vi två val för placeringen av Andersson och Eriksson. Totalt: $5\cdot 4\cdot 2 = 40$.
Med Andersson först, finns det $4!=24$ köer, och med Bertilsson efter Andersson finns det också $4!$ köer (sätt in Bertilsson direkt efter Andersson). Med både Andersson först och Bertilsson därefter, finns det $3!=6$ arrangemang. Inklusion-exklusion ger då $120-2\cdot 24 + 6 = 78$ olika köer.

Alternativt kan man dela upp i två fall: Andersson på plats $5$, eller Andersson på plats $2,3$ eller $4$. Med Andersson på plats 5, så kan övriga stå på $4!=24$ sätt. Om Andersson är på plats $2,3$ eller $4$, så har Börjesson bara 3 platser att välja bland. De övriga $3$ kan placeras på $3!$ sätt. Fall 2 ger därför $3\cdot 3 \cdot 3! = 54$, så med första fallet får vi totalt får vi $78$.