Dugga 2 (inkl ersättningsuppgifter för Dugga 1!)

Obs! Duggorna är alltså inte obligatoriska, men kan ge 2 bonuspoäng per dugga på tentan.

Ni som har fått rest (dvs kommentarer om att något är fel eller behöver redovisas bättre) på uppgifterna 2, 3 och 5 får här "ersättningsuppgifter" numrerade 2', 3', och 5'. Eventuella fel på uppgifterna 1 och 4 bortser vi från.
Uppgifterna som hör till Dugga 2 är numrerade 6-10.

Lämnas in senast vid början av föreläsningen den 2 mars.

Uppgift 2'
Låt $A$ vara mängden $\{1, 2, 3\}$.
a) Ge ett exempel på ett element i $A$, dvs något som tillhör $A$.
b) Ge ett exempel på en delmängd till $A$.

Uppgift 3'
Betrakta följande tre funktioner från $\mathbb{R}$ till $\mathbb{R}$. Ange vilken som är surjektiv, vilken som är injektiv, och vilken som är varken eller.
a) $f(x) = x^2$.
b) $g(x) = \arctan(x)$.
c) $h(x) = x^3 - 10x$.

Uppgift 5'
Bevisa att \[\sum_{k=1}^n \frac1{k(k+1)} = \frac{n}{n+1},\] genom att skriva av nedanstående och fylla i luckorna.

Låt $p_n$ vara utsagan att (fyll i).
Utsagan $p_1$ säger att (fyll i), vilket är sant eftersom (fyll i) är lika med (fyll i).
Låt nu $n$ vara ett godtyckligt positivt heltal. Vi ska visa att utsagan $p_n$ implicerar utsagan $p_{n+1}$. Antag därför att utsagan $p_n$ är sann. Vi ska nu härleda utsagan $p_{n+1}$, som säger att (fyll i).
Vi har \[\sum_{k=1}^{n+1} \frac1{k(k+1)} = \sum_{k=1}^n \frac1{k(k+1)} + \frac1{(n+1)(n+2)}.\]
Enligt induktionsantagandet är detta lika med \[\text{(fyll i)} +  \frac1{(n+1)(n+2)}.\]
Genom att sätta på gemensamt bråkstreck och förenkla ser vi att detta är lika med högerledet i utsagan $p_{n+1}$, och vi har därmed visat att $p_n$ implicerar $p_{n+1}$.
Enligt induktionsprincipen följer att utsagan $p_n$ gäller för varje $n$. 

6.
Finn $x$ och $y$ så att talet $6216x + 3885y$ är en delare till både 6216 och 3885.

7.
Bevisa att ekvationen \[2x^2 - 5y^2 = 1\] saknar heltalslösningar, genom att välja lämpligt tal $n$ och visa att kongruensen \[ 2x^2 - 5y^2 \equiv 1 \quad \text{(mod $n$)}\] saknar lösningar.

8.
Vi tänker oss att talen $a$, $b$ och $c$ är positiva heltal med ungefär 1000 siffror. Vilka av följande beräkningsproblem kan (alltid) lösas på rimlig tid med en dator?
a) Bestämma sgd($a, b$).
b) Bestämma det minsta primtal som delar $a$.
c) Bestämma det minsta positiva heltal som är kongruent med $a^b$ modulo $c$.

9.
Nisse tippar ett visst antal rader stryktips varje vecka (13 matcher, varje match slutar med 1, X, eller 2, se uppgift 6.11 i boken), och väljer slumpmässigt mellan 1,  X, och 2 i varje match. Förra veckan hade han en rad med 12 rätt, och hade han bara haft rätt på match 9 också, så hade han haft 13 rätt. Nisse hade ju sannolikheten $1/3$ att ha rätt på match 9, så han tycker att ungefär var tredje gång han har minst 12 rätt borde han få 13. Det har hänt 3 gånger att Nisse har haft 12 rätt, så han tycker att han har haft lite otur.

Hur många gånger vanligare är det att få 12 rätt än att få 13 rätt?

10.
Hur många uppspännande träd finns det i $K_4$ (den fullständiga grafen på 4 noder)? Hur många (klasser av) icke isomorfa sådanan träd finns det?