MM2001 · Tidigare tentor

MM2001 · Diskret matematik

Tenta 2024-08-13

Per Alexandersson6 uppgifter
#Uppgift 1
Uppgift 1
Lös följande problem.
(a)
Ge exempel på två sammansatta tal $a$ och $b$ så att $\SGD(a,b)=1$.
(b)
Formulera Fermat's lilla sats.
(c)
Beräkna resten då $4^{63}$ delas med $31$.
Visa lösningDölj lösning
  1. Man kan ta t.ex $a=4$ och $b=9$.
  2. Om $p$ är ett primtal och $a$ är ett heltal så att $a$ ej delas av $p$, då gäller $a^{p-1} \equiv 1$ (mod $p$).
  3. Eftersom $31$ är ett primtal, gäller enl. Fermat's lilla sats att \[ 4^{63} = 4^3 (4^{30})^2 \equiv_{31} 4^3 \cdot 1^2 = 64 \equiv_{31} 2. \] Alternativt, $4^{60} = 2^{120} = (2^5)^{24} = (32)^{24} \equiv_{31} 1^{24} = 1$, där $\equiv_{31}$ indikerar att talen ger samma rest modulo $31$.
#Uppgift 2
Uppgift 2
Polynomet $2 x^3-3 x^2-6 x + a$ har $x = \frac{3}{2}$ som nollställe. Finn talet $a$ samt polynomets övriga nollställen.
Visa lösningDölj lösning
Vi sätter in $x=\frac{3}{2}$ i polynomet. Detta ger \[ 2 \cdot \frac{3^3}{2^3} - 3\cdot \frac{3^2}{2^2} - 6\cdot \frac{3}{2}+a = \frac{27}{4}-\frac{27}{4} - 9 + a = a-9. \] Eftersom $3/2$ ska vara vara ett nollställe måste $a=9$. Polynomet är alltså \[ 2 x^3-3 x^2-6 x + 9, \] och det innehåller $2x-3$ som faktor. Polynomdivision med detta ger kvoten $x^2-3$ så de två sista rötterna är $\pm \sqrt{3}$.
#Uppgift 3
Uppgift 3
Lös ekvationen $|x^2 - 1| + |x - 1| = x+1$ för $x \in \setR$.
Visa lösningDölj lösning
Uttrycken inom absolutbeloppen byter tecken vid $x=-1$ och $x=1$, respektive. Vi delar upp i tre fall.
  • Fall $x<-1$: Här blir ekvationen \[ (x^2-1) - (x-1) = x+1 \iff x^2-2x-1 = 0 \iff x = 1 \pm \sqrt{2}. \] Ingen av lösningarna uppfyller $x<-1$.
  • Fall $-1 \leq x < 1$: Här blir ekvationen \[ -(x^2-1) -(x-1) = x+1 \iff x^2+2x-1 = 0 \iff x = -1\pm \sqrt{2}. \] Enbart $x = \sqrt{2}-1$ ligger inom intervallet.
  • Fall $1\leq x $: Här blir ekvationen \[ (x^2-1) + (x-1) = x+1 \iff x^2-3 = 0 \iff x = \pm \sqrt{3}. \] Bara $\sqrt{3}$ är lösning inom intervallet.
Ekvationen har lösningarna $x=\sqrt{3}$ samt $x=\sqrt{2}-1$.
#Uppgift 4
Uppgift 4
Bestäm för vilka $z\in \setC$ vi har att $\dfrac{1}{z} + \overline{z}$ är ett reellt tal.
Visa lösningDölj lösning
Vi bryter ut $\overline{z}$ och får att \[ \frac{1}{z} + \overline{z} = \overline{z}\left(\frac{1}{z\cdot \overline{z}} + 1\right) = \overline{z}(|z|^{-2} +1), \] då $z\cdot \overline{z} = |z|^2$. Eftersom $|z|^{-2} +1$ är reellt, räcker det att $\overline{z}$ ska vara reellt. Detta sker bara om talet $z$ själv är reellt (och nollskilt).
#Uppgift 5
Uppgift 5
Bokstäverna P, E, N, N, A, N kan man sätta samman och bilda kombinationer med 6 bokstäver (ord). Hur många ord
(a)
kan skapas totalt?
(b)
uppfyller att P står direkt till vänster om E?
(c)
uppfyller att P står först eller N står sist (eller båda)?
Svaren ska anges med heltal. Inget svar överstiger 300.
Visa lösningDölj lösning
  1. Ordet innehåller 6 bokstäver, men vi har att NNN är tre lika bokstäver så totala antalet ord är $\frac{6!}{3!} = 6!/6 = 5! = 120$.
  2. Vi betraktar PE som om det vore en bokstav som kan placeras ut. Detta ger $\frac{5!}{3!} = 20$ olika sådana ord.
  3. Antal ord där P står först är $5!/3! = 20$, då vi måste bilda ord genom att kasta om ENNAN. Liknande, antal ord där N står sist är $5!/2! = 60$, då vi måste bilda ord genom att kasta om PENNA. Slutligen, antal ord där P står först och N står sist fås genom omkastning av ENNA, vilket ger $4!/2! = 12$ ord. Inklusion-exklusion ger nu att totala antalet ord vi söker är \[ 20+60-12 = 68 \] då vi bland de $20+60$ orden med antingen P först eller N sist, dubbelräknar de $12$ ord som uppfyller båda kraven.
#Uppgift 6
Uppgift 6
Visa med hjälp av induktion att \[ \sum_{k=1}^n k\cdot 2^{k-1} = (n-1)\cdot 2^n + 1 \tag{$\ast$} \] gäller för alla heltal $n\geq 1$. Ange tydligt basfall samt induktionsantagande.
Visa lösningDölj lösning
Vi har basfallet $n=1$. Vänsterledet och högerledet är båda $1$ i ekvationen.

Vi antar nu att formeln ovan gäller för ett fixt värde på $n \geq 1$. Vi vill nu visa att nästföljande fall också gäller, dvs. \[ \sum_{k=1}^{n+1} k\cdot 2^{k-1} = (n)\cdot 2^{n+1} + 1. \] Vi har nu att \[ \sum_{k=1}^{n+1} k\cdot 2^{k-1} = \underbrace{\left( \sum_{k=1}^{n} k\cdot 2^{k-1} \right)}_{\text{byts ut enl. antagande}} + (n+1)\cdot 2^n = (n+1)\cdot 2^n + 1 + (n-1)\cdot 2^n. \] Högerledet kan skrivas om, \[ (n+1)\cdot 2^n + 1 + (n-1)\cdot 2^n = ((n+1)+(n-1))\cdot 2^n + 1 = 2n\cdot 2^n +1 = n\cdot 2^{n+1}+1, \] så vi har nu visat ekvationen. Basfallet samt induktionsprincipen ger nu att den slutna formeln för summan gäller för alla $n\geq 1$.
Figur