MM2001 · Diskret matematik

Tenta 2025-03-12

#Uppgift 1

Uppgift 1

(a)

Kurt-Erik sparar pengar under 80 dagar. På dag $k$ så lägger han $k$ kronor i en burk, för $k=1,2,3,\dotsc,80$. Hur många kronor finns i burken den sista dagen?

(b)

Exakt ett av talen $3$, $5$ och $7$ är en lösning till polynomekvationen $x^{10} -17x^9 + \dotsb -175x + 98=0$. Alla koefficienter är heltal. Bestäm vilket av talen som är lösningen. Motivera ditt svar.

(c)

Bestäm koefficienten för $x^8$ i uttrycket $\left(2x^2 + \frac{1}{x} \right)^{10}$. Svaret ska anges som en produkt av heltal.

Visa lösningDölj lösning

Detta är den aritmetiska summan $1+2+3+\dotsb+80$, som blir $81\cdot 40 = 3240$.
Sats från kursen säger att en heltalslösning $x$ till en polynomekvation med heltalskoefficienter, uppfyller att den delar konstanttermen. Det vill säga, $x$ måste dela $98$. Enbart talet $7$ är en delare till $98$, så $x=7$ är lösningen.
Binomialsatsen ger att \[ \left(2x^2 + \frac{1}{x} \right)^{10} = \sum_{k=0}^{10} \binom{10}{k} (2x^2)^k \cdot x^{-(10-k)} = \sum_{k=0}^{10} 2^k \binom{10}{k} x^{3k-10}. \] Vi söker den term som motsvarar $k=6$, så svaret är $2^6 \binom{10}{6} = 64 \cdot\frac{10\cdot 9\cdot 8 \cdot 7}{24} = 64 \cdot 30 \cdot 7$.

#Uppgift 2

Uppgift 2

(a)

Formulera Fermats lilla sats.

(b)

Bestäm $\SGD(1^{2025} + 3^{2025} + 5^{2025} + 9^{2025}, 12)$.

Visa lösningDölj lösning

Se kursboken.
Delarna till $12$ är $1,2,3,4,6$ och $12$. Vi måste då undersöka vilken rest som fås då $N = 1^{2025} + 3^{2025} + 5^{2025} + 9^{2025}$ delas med $3$ och med $4$. Vi har att \[ N \equiv_3 1+0+(-1)^{2025} + 0 = 0 \] så $N$ är delbart med $3$. Vidare, \[ N \equiv_4 1 + (-1)^{2025} + 1^{2025} + 1^{2025} = 2 \] så resten vid division med $4$ är $2$. Alltså är $N$ jämnt, men inte delbart med $4$. Största gemensamma delaren, $\SGD(N,12)$, är då $3\cdot 2 = 6$.

#Uppgift 3

Uppgift 3

Lös olikheten $ 3|x-2| + 3x \geq 2|x+5|$, för $x \in \setR$.

Visa lösningDölj lösning

Vi delar upp i tre fall, som bestäms av absolutbeloppen.

Fall 1: $x<-5$: Olikheten blir \[ 3(2-x) + 3x \geq -2(x+5) \iff 6-3x + 3x +2x+10 \geq 0 \iff x \geq -8. \] Så i detta fall får vi lösningarna $-8 \leq x < -5$.

Fall 2: $-5 \leq x < 2$: Olikheten blir \[ 3(2-x) + 3x \geq 2(x+5) \iff 6-3x + 3x -2x - 10 \geq 0 \iff -2 \geq x. \] Så i detta fall får vi lösningarna $-5 \leq x \leq -2$.

Fall 3: $x \geq 2$: Här får vi \[ 3(x-2) + 3x \geq 2(x+5) \iff 3x-6 + 3x - 2x - 10 \geq 0 \iff 4x \geq 16. \] Detta ger lösningarna $x \geq 4$.

Sammanfattningsvis, så löses då olikheten av alla $x$ som uppfyller antingen $-8 \leq x \leq -2$ eller $x \geq 4$.

#Uppgift 4

Uppgift 4

Betrakta de två Diofantiska ekvationerna $5x+14y=19$ och $13x-12z=-11$.

(a)

Ge den allmänna lösningen till var och en av ekvationerna.

(b)

Beskriv de $x$ som ingår i en lösning i båda ekvationerna. Med andra ord, beskriv $ \{ x \in \setZ : \exists y,z \in \setZ \text{ så att } 5x+14y=19 \text{ och } 13x-12z=-11 \}. $

Visa lösningDölj lösning

De allmänna lösningarna är \[ \begin{cases} x &= 1 + 14n \\ y &= 1 -5n, \end{cases} n \in \setZ \qquad \text{ och } \qquad \begin{cases} x &= -11 + 12m \\ y &= -11 + 13m, \end{cases} m \in \setZ, \] respektive. De tal $x$ som dyker upp i båda lösningarna måste då vara de som kan uttryckas som $x = 1+14n = -11+12m$. Detta ger att vi vill lösa $12m-14n=12$, som ger $6m-7n=6$. Här ser vi att allmänna lösningen (för $m$) blir $m=1+7t$, för $t \in \setZ$. Detta leder till att $x=-11+12m = -11+12(1+7t) = 1 + 84t$. Alltså är alla $x$ på formen $1 + 84t$, där $t$ är ett heltal, de $x$ som sökes.

#Uppgift 5

Uppgift 5

Damerna Agda, Berit, Gerd och Ester ska ha knytkalas. De har bestämt sig för att förbereda följande fyra huvudrätter: Aladåb, böcklinglåda, potatis samt köttfärslimpa. De ska såklart ha något till kaffet också. De två klassikerna citronfromage och flamberade bananer ska serveras till efterrätt.

(a)

På hur många sätt kan rätterna fördelas så att varje person lagar exakt en huvudrätt och som mest en efterrätt? Notera att varje rätt ska förekomma exakt en gång på kalaset.

(b)

Gerd har gikt så hon orkar bara laga en efterrätt om hon till huvudrätt kokar potatisar. På hur många sätt¹ kan man fördela uppgifterna så att Gerd orkar med?

(c)

Vid förra kalaset så råkade Ester flambera sin pudel, så hon får inte laga flamberade bananer denna gång. På hur många sätt kan nu rätterna fördelas, så att både Gerd och Esters (nya) pudel inte riskerar sin hälsa?

Svaren ska anges med heltal. Inget av svaren överstiger $300$.

Tips: Dela upp i två fall beroende på om Gerd gör en efterrätt eller inte. ↩

Visa lösningDölj lösning

Huvudrätterna kan fördelas på $4 \cdot 3 \cdot 2 \cdot 1 = 4! = 24$ sätt. På liknande sätt, efterrätterna kan fördelas på $4\cdot 3 = 12$ sätt. Totalt antal sätt är då $24\cdot 12 = 288$.
Det finns två fall: Gerd gör en efterrätt, eller så gör Gerd inte en efterrätt.

Om Gerd gör efterrätt, så har hon två val bland dessa, och hon måste då koka potatis. De tre återstående damerna måste då fördela 3 huvurätter och den efterrätt Gerd inte gör: $2\cdot 3! \cdot 3 = 36$ sätt.

Om Gerd inte gör efterrätt, så kan huvudrätterna fördelas fritt: $4!$ sätt. De två efterrätterna ska nu fördelas bland de 3 damerna som inte är Gerd: $3\cdot 2$ sätt. Totalt: $24\cdot 6 = 144$ sätt.

Adderar vi de två fallen får vi då $180$ sätt.

(Alternativt kan man dela upp i de två fallen: Gerd kokar potatis eller inte).
Det är enklare att räkna de förbjudna fallen. Vi gör samma sak som i (b), men vi bestämmer att Ester gör flamberade bananer. Vi får återigen två fall, beroende på vad Gerd gör.

Om Gerd gör efterrätt, så gör hon cintronfromage och hon kokar potatis. De tre återstående damerna måste då fördela sina 3 huvurätter. Detta leder till $3! = 6$ sätt.

Om Gerd inte gör efterrätt, så kan huvudrätterna fördelas fritt: $4!$ sätt. Citronfromagen ska nu lagas av Agda eller Berit: $2$ alternativ. Totalt: $24\cdot 2 = 48$ sätt.

Adderar vi de två fallen, ser vi att Ester flamberar bananer i $54$ av fallen.

Det antal vi söker är då $180-54=126$.