Den i särklass svåraste uppgiften på tentan var tydligen 1a, att avgöra huruvida det är sant att $\{1,2,3\}\in \mathbb{N}$. Det är det inte. 1, 2, och 3 är visserligen naturliga tal, men mängden som innehåller 1, 2, och 3 är inte ett tal utan en mängd. Den är en delmängd till $\mathbb{N}$ och inte ett element.
1b var sann, 1c falsk, 1d sann, och 1e sann. Några missade att $\prod$ står för produkt och inte summa.
På uppgift 2 hade många missat att saker som upprepas inom klamrarna ändå bara räknas en gång. Svaren var 4, 7, 2, 9, 64.
På uppgift 3 gällde det att avgöra huruvida en viss relation är en ekvivalensrelation respektive partiell ordning. Den är varken eller. Eftersom den inte är symmetrisk, är den inte en ekvivalensrelation. Till exempel gäller $1R0$ men inte $0R1$. Märkligt nog hävdade många att $\cos 0 < \cos 1$, fast det är tvärtom.
När det gäller partiell ordning är det antisymmetrin som fallerar. Det finns element som båda står i relation till varandra, trots att de är olika. Till exempel är $\cos 0 \leq \cos(2\pi)$ och $\cos(2\pi)\leq \cos 0$.
Uppgift 4 bestod i ett induktionsbevis. Trots att jag påminde om att man måste ange vad som är induktionshypotesen och var den används, är det många som har slarvat med detta. Några har gjort själva räkningarna rätt, men i stort sett inte redovisat någonting av bevisets struktur, och jag misstänker att en och annan blir besviken över att då bara få en poäng för att ha kollat basfallet.
I många fall står lösa påståenden utan att det framgår om detta är något som man påstår är sant, antar är sant, eller försöker bevisa. Flera har använt bokstaven $k$ som övre summationsgräns i induktionssteget, vilket gör att den bokstaven får två olika betydelser. Då blir det tokigt ibland, som när man måste tala om den term som svarar mot att "$k=k+1$".
På uppgift 5 gällde det att veta att största gemensamma delare bestäms med Euklides algoritm, att potenser modulo 841 beräknas med upprepad kvadrering, och att (eftersom dessa blir över) faktorisering kan göras med det så kallade kvadratiska sållet. Sedan var uppgiften att göra en av dessa beräkningar, och då är (a) den rimligaste, och den som de flesta har gjort. Det är inte otänkbart att lösa (b) för hand, men av de två-tre som försökte var det ingen som räknade rätt hela vägen. (c) är jag osäker på om ens en dator skulle hinna med under tentamenstiden.
Uppgift 6 har överlag gått bra, och kunde lösas genom att man räknar antingen modulo 3 eller modulo 7.
På uppgift 7 verkar ordet "rad" ha vållat en del bekymmer. Med rad menades här ett sätt att välja ut 8 av 30 matcher (vilket är hur ordet används i denna typ av spel). Flera tentander har kommenterat i sina lösningar att uppgiften var dåligt formulerad.
Ibland händer det att man som examinator missar att en formulering i en uppgift kan tolkas på flera sätt. Om det finns ett par olika vettiga tolkningar kan det då hända att man får vara generös och ge poäng för lösningar som inte är som man har tänkt sig. Men så verkar det inte vara här. Vissa har förstått uppgiften och sedan räknat mer eller mindre bra, medan andra inte har gjort någon vettig tolkning av uppgiften, varken den jag hade tänkt mig eller någon annan.
Om man tycker att en uppgift är dåligt formulerad kan man antingen fråga tentamensvakten som då kan ringa examinatorn, eller så får man redovisa hur man själv tolkar uppgiften. Kommer man trots viss ansträngning inte på någon rimlig tolkning lutar det åt det förstnämnda alternativet.
Svaret var i alla fall 176, dvs $8\cdot 22$, i båda fallen, och poängen var att en rad med 7 rätt kan fås genom att man tar den rätta raden, tar bort en match (8 möjligheter), och lägger till en som man inte hade från början (22 möjligheter).
Uppgift 8 gick också ganska bra, men för att få mer än 2 poäng krävdes att man hade någon form av motivering till att de grafer man har ritat inte är isomorfa, alltså en egenskap som den ena grafen har men inte den andra. Några har ritat grafer med olika antal kanter, men då försvinner liksom uppgiften, eftersom detta i sig gör att de inte är isomorfa, så detta har gett 0 poäng utan pardon.
Nu har jag gnällt en del, men de flesta har ändå fått ihop 20 poäng. För 4 krävdes 28 poäng, och för 5 36 poäng.
Thursday, April 16, 2015
Tuesday, April 14, 2015
Resultat på tentan
Tyvärr har rättningen och rapporteringen av resultaten dragit ut på tiden. Här är i alla fall resultaten på tentan (för dem som minns sin kod, övriga får meddelande inom kort). Betygsgränserna är 20 för 3, 28 poäng för 4, och 36 poäng för 5.
KOD BETYG POÄNG
1 3 21
2 U 18
3 4 29
4 4 29
5 3 24
7 3 24
8 3 27
10 4 35
11 U 11
12 5 42
13 4 35
14 3 25
15 5 38
16 4 31
17 3 20
19 3 24
21 3 25
22 3 23
23 4 28
24 5 37
25 4 32
27 3 22
28 4 29
29 U 5
30 3 24
31 4 33
34 4 29
38 3 27
40 U 0
41 3 24
42 4 32
44 4 34
46 4 31
48 4 30
52 3 21
53 U 14
55 4 34
57 4 32
58 5 44
60 5 37
62 3 25
63 3 20
64 U 17
65 3 26
66 5 41
68 4 33
71 U 14
73 U 0
76 5 36
77 4 35
78 U 11
82 4 32
83 4 31
84 3 20
85 3 21
90 U 16
93 U 13
97 3 27
100 4 28
101 U 11
103 U 16
105 4 31
110 4 35
112 5 43
114 4 29
116 U 18
118 3 24
120 3 27
122 3 22
123 3 25
124 4 33
127 3 25
128 5 40
130 4 29
686 3 20
KOD BETYG POÄNG
1 3 21
2 U 18
3 4 29
4 4 29
5 3 24
7 3 24
8 3 27
10 4 35
11 U 11
12 5 42
13 4 35
14 3 25
15 5 38
16 4 31
17 3 20
19 3 24
21 3 25
22 3 23
23 4 28
24 5 37
25 4 32
27 3 22
28 4 29
29 U 5
30 3 24
31 4 33
34 4 29
38 3 27
40 U 0
41 3 24
42 4 32
44 4 34
46 4 31
48 4 30
52 3 21
53 U 14
55 4 34
57 4 32
58 5 44
60 5 37
62 3 25
63 3 20
64 U 17
65 3 26
66 5 41
68 4 33
71 U 14
73 U 0
76 5 36
77 4 35
78 U 11
82 4 32
83 4 31
84 3 20
85 3 21
90 U 16
93 U 13
97 3 27
100 4 28
101 U 11
103 U 16
105 4 31
110 4 35
112 5 43
114 4 29
116 U 18
118 3 24
120 3 27
122 3 22
123 3 25
124 4 33
127 3 25
128 5 40
130 4 29
686 3 20
Monday, March 16, 2015
Låtsastenta
1. Avgör vilka av följande påståenden som är sanna:
(a) Utsagan $(p\rightarrow q) \vee (q\rightarrow p)$ är en tautologi.
(b) $\{-1,2,0\} \subseteq \mathbb{Q}$.
(c) Funktionen $f:\mathbb{R} \to \mathbb{R}$ som definieras av $f(x) = e^{\cos x}$ är surjektiv.
(d) \[\sum_{k=1}^5 k = 120.\]
2. Låt $A = \{1,3,5\}$ och $B = \{4,5,6,7\}$. Bestäm antalet element i mängderna
$A\cup B$, $A\cap B$, $A\times B$ och $A\setminus B$.
3. Vi definierar två relationer på $\mathbb{Z}\times \mathbb{Z}$:
$(a,b) R (c,d)$ betyder att $a\leq c$ och $b\leq d$, och
$(a,b) S (c,d)$ betyder att $a\leq c$ eller $b\leq d$.
Är någon av $R$ och $S$ en partiell ordning?
4. Lucastalen är en talföljd som startar $1, 3, 4, 7, 11,\dots$, där varje tal är summan av de två föregående. Bevisa med induktion att största gemensamma delaren till två konsekutiva Lucastal är 1.
5. Ange alla lösningar i positiva heltal till ekvationen \[70x + 49y = 679.\]
6. Visa att ekvationen $2x^2 - 11y = 4$ saknar heltalslösningar, genom att visa att motsvarande kongruend modulo 11 saknar lösningar.
7. Hur många stryktipsrader finns det (varje omgång) som har 11 (av 13) rätt?
8. Vilken av graferna $K_4$ och $K_5$ har en Eulercykel?
Svar / kommentarer (Obs! Nedanstående är inte fullständiga lösningar och skulle inte ge full päng på tentan!):
1 (a) Sant, uttrycket blir sant oavsett sanningsvärdena hos $p$ och $q$. (b) Sant, talen $-1$, 2, och 0 är rationella. (c) Falskt, funktionen antar inte alla värden, bara dem i intervallet $[1/e,e]$. (d) Falskt, summan är $1+2+3+4+5= 15$, däremot är motsvarande produkt lika med 120.
2. Antalet element är 6, 1, 12, respektive 2.
3. Kontrollera reflexivitet, antisymmetri och transitivitet. Relationen $R$ är en partiell ordning, medan relationen $S$ varken är antisymmetrisk eller transitiv, till exempel gäller $(1,0)S(0,1)$ och $(0,1)S(1,0)$ trots att $(0,1)\neq (1,0)$.
4. Kom ihåg att ange vad som är induktionshypotesen, hur den används i induktionssteget, och kom ihåg att kontrollera basfallet!
På den här uppgiften får man göra en numrering själv. Till exempel kan man kalla Lucastalen för $L_0,L_1,\dots$, med $L_0=1$ och $L_1=3$. Man kan låta utsagan $p_n$ vara att $sgd(L_n, L_{n+1})=1$. Basfallet blir då fallet $n=0$, som säger att sgd(1,3)=1.
5. Största gemensamma delare till 70 och 49 är 7, och ekvationen är ekvivalent med
$10x+7y = 97$. En lösning är $x=9$, $y=1$, och den allmänna lösningen kan skrivas som $x= 9+7n$, $y=1-10n$. Men mängden av lösningar kan också parametriseras på andra sätt.
6. Det räcker att kontrollera att kongruensen $2x^2\equiv 4$ modulo 11 inte har någon lösning, genom att kontrollera ett värde på $x$ från varje kongruensklass, till exempel $x=0,\dots,10$.
7. Antalet sådana rader är $\binom{13}2 \cdot 4= 312$. Det finns $\binom{13}2 = 78$ sätt att välja två matcher där det blir fel, och $2\cdot 2=4$ sätt att ha fel på dessa två matcher.
8. $K_5$ har en Eulercykel (går att rita eller hänvisa till att den är sammanhängande och alla noder har jämn grad). $K_4$ har fyra noder av udda grad, och har därmed ingen Eulercykel.
(a) Utsagan $(p\rightarrow q) \vee (q\rightarrow p)$ är en tautologi.
(b) $\{-1,2,0\} \subseteq \mathbb{Q}$.
(c) Funktionen $f:\mathbb{R} \to \mathbb{R}$ som definieras av $f(x) = e^{\cos x}$ är surjektiv.
(d) \[\sum_{k=1}^5 k = 120.\]
2. Låt $A = \{1,3,5\}$ och $B = \{4,5,6,7\}$. Bestäm antalet element i mängderna
$A\cup B$, $A\cap B$, $A\times B$ och $A\setminus B$.
3. Vi definierar två relationer på $\mathbb{Z}\times \mathbb{Z}$:
$(a,b) R (c,d)$ betyder att $a\leq c$ och $b\leq d$, och
$(a,b) S (c,d)$ betyder att $a\leq c$ eller $b\leq d$.
Är någon av $R$ och $S$ en partiell ordning?
4. Lucastalen är en talföljd som startar $1, 3, 4, 7, 11,\dots$, där varje tal är summan av de två föregående. Bevisa med induktion att största gemensamma delaren till två konsekutiva Lucastal är 1.
5. Ange alla lösningar i positiva heltal till ekvationen \[70x + 49y = 679.\]
6. Visa att ekvationen $2x^2 - 11y = 4$ saknar heltalslösningar, genom att visa att motsvarande kongruend modulo 11 saknar lösningar.
7. Hur många stryktipsrader finns det (varje omgång) som har 11 (av 13) rätt?
8. Vilken av graferna $K_4$ och $K_5$ har en Eulercykel?
Svar / kommentarer (Obs! Nedanstående är inte fullständiga lösningar och skulle inte ge full päng på tentan!):
1 (a) Sant, uttrycket blir sant oavsett sanningsvärdena hos $p$ och $q$. (b) Sant, talen $-1$, 2, och 0 är rationella. (c) Falskt, funktionen antar inte alla värden, bara dem i intervallet $[1/e,e]$. (d) Falskt, summan är $1+2+3+4+5= 15$, däremot är motsvarande produkt lika med 120.
2. Antalet element är 6, 1, 12, respektive 2.
3. Kontrollera reflexivitet, antisymmetri och transitivitet. Relationen $R$ är en partiell ordning, medan relationen $S$ varken är antisymmetrisk eller transitiv, till exempel gäller $(1,0)S(0,1)$ och $(0,1)S(1,0)$ trots att $(0,1)\neq (1,0)$.
4. Kom ihåg att ange vad som är induktionshypotesen, hur den används i induktionssteget, och kom ihåg att kontrollera basfallet!
På den här uppgiften får man göra en numrering själv. Till exempel kan man kalla Lucastalen för $L_0,L_1,\dots$, med $L_0=1$ och $L_1=3$. Man kan låta utsagan $p_n$ vara att $sgd(L_n, L_{n+1})=1$. Basfallet blir då fallet $n=0$, som säger att sgd(1,3)=1.
5. Största gemensamma delare till 70 och 49 är 7, och ekvationen är ekvivalent med
$10x+7y = 97$. En lösning är $x=9$, $y=1$, och den allmänna lösningen kan skrivas som $x= 9+7n$, $y=1-10n$. Men mängden av lösningar kan också parametriseras på andra sätt.
6. Det räcker att kontrollera att kongruensen $2x^2\equiv 4$ modulo 11 inte har någon lösning, genom att kontrollera ett värde på $x$ från varje kongruensklass, till exempel $x=0,\dots,10$.
7. Antalet sådana rader är $\binom{13}2 \cdot 4= 312$. Det finns $\binom{13}2 = 78$ sätt att välja två matcher där det blir fel, och $2\cdot 2=4$ sätt att ha fel på dessa två matcher.
8. $K_5$ har en Eulercykel (går att rita eller hänvisa till att den är sammanhängande och alla noder har jämn grad). $K_4$ har fyra noder av udda grad, och har därmed ingen Eulercykel.
Monday, March 2, 2015
Gamla tentor och bokkapitel
Det finns tre gamla tentor med lösningar på en gammal kurshemsida.
Det vi har pratat om och som man bör ha läst inför tentan är:
1.1-1.8 (om det blir problem här, gå vidare!)
2
3.1-3.8
4
5
6 (samt notation från kapitel 9, alltså sannolikheter)
7.1, 7.2, 7.4, 7.7.
Innehållsförteckning (kan vara bra för dem som har gamla boken).
Sunday, March 1, 2015
Lite om Dugga 2
Uppgift 6 är en standardtillämpning av Euklides algoritm. Se till att ni kan detta inför tentan!
Uppgift 7 har lett till en del frågor och funderingar. På föreläsningen gick jag igenom ett liknande exempel, som visade att ekvationen \[x^3 - 13y^2 = 2\] saknar heltalslösningar.
Tricket är att använda kongruensräkning. Om ekvationen hade någon lösning, så skulle även kongruensen \[ x^3 - 13y^2 \equiv 2 \quad (\text{mod $n$})\] ha en lösning, oavsett vilket $n$ vi väljer. En strategi för att bevisa att ekvationen saknar lösningar (eller för att hitta dem om det finns!) är att välja några värden på $n$ och se om ekvationen (alltså motsvarande kongruens) har någon lösning modulo $n$.
Det fiffiga med moduloräkning är att det bara finns ett ändligt antal kongruensklasser. Skulle vi till exempel undersöka den här ekvationen modulo 3, finns det bara 9 olika fall. Det finns 3 kongruensklasser, och var och en av $x$ och $y$ måste tillhöra någon av dem. Nu visar det sig att ekvationen har lösningar modulo 3, till exempel $x\equiv 0$ och $y\equiv 1$. Då kan vi inte dra någon slutsats. Bara för att ekvationen har lösningar modulo 3 behöver det inte finnas någon "riktig" lösning.
Om vi i stället väljer att titta på ekvationen modulo 13, händer något intressant. Eftersom termen $13y^2$ då blir kongruent med 0, spelar det ingen roll vad $y$ är, utan vi får ett villkor på bara $x$, nämligen \[x^3 \equiv 2 \quad (\text{mod $n$}).\] Det finns bara 13 fall att testa, så vi kan göra en tabell och gå igenom alla. Enklast blir det om vi testar $x$ i intervallet $-6\leq x \leq 6$, eftersom $(-x)^3 = -x^3$. Men 13 konsekutiva tal vilka som helst går bra, vi måste bara få med ett tal i varje kongruensklass, så att vi täcker in alla fall.
Vi har
$0^3\equiv 0$, $1^3 \equiv 1$, $2^3 \equiv 8$, $3^3\equiv 1$, $4^3\equiv 12$, $5^3\equiv 8$, $6^3\equiv 8$.
Samt $(-1)^3\equiv -1 \equiv 12$, $(-2)^3 \equiv -8 \equiv 5$, $(-3)^3\equiv -1\equiv 12$, $(-4)^3 \equiv -12 \equiv 1$, $(-5)^3\equiv -8\equiv 5$, och $(-6)^3\equiv -8\equiv 5$.
Då har vi testat alla kongruensklasser, och ser att oavsett värde på $x$, så måste $x^3$ vara kongruent med något av talen 0, 1, 5, 8, och 12. Det blir alltså aldrig kongruent med 2, och därför kan ekvationen inte ha några heltalslösningar.
Jag såg också att någon har postat den här uppgiften på pluggakuten. Jag har ju sagt att ni får diskutera uppgifterna (och det är i själva verket ett pedagogiskt "trick" från min sida), så det här är inget som är förbjudet. I det här fallet har någon svarat på ett bra sätt utan att skriva en hel lösning. Så då kan jag lika gärna länka härifrån så blir det rättvist och bra!
På uppgift 8 krävs inte mycket motivering, men något litet nyckelord vill jag att ni skriver som förklaring.
Uppgift 9 verkar vara ganska "straightforward".
Uppgift 10 handlar om grafer, uppspännande träd, och isomorfi. Antalet uppspännande träd i $K_4$ efterfrågas även i uppgift 7.14 i boken. Notera att villkoret att grafen ska vara sammanhängande (som det står i uppgift 7.14) inte är nödvändigt för själva definitionen av begreppet uppspännande träd. Det är bara det att det inte finns några om grafen inte är sammanhängande. Det villkoret behöver ni således inte fundera över.
Isomorfi är en ekvivalensrelation, och de uppspännande träden i $K_4$ kan alltså delas in i klasser, där träd i samma klass är isomorfa, och träd i olika klasser inte är isomorfa.
Uppgift 7 har lett till en del frågor och funderingar. På föreläsningen gick jag igenom ett liknande exempel, som visade att ekvationen \[x^3 - 13y^2 = 2\] saknar heltalslösningar.
Tricket är att använda kongruensräkning. Om ekvationen hade någon lösning, så skulle även kongruensen \[ x^3 - 13y^2 \equiv 2 \quad (\text{mod $n$})\] ha en lösning, oavsett vilket $n$ vi väljer. En strategi för att bevisa att ekvationen saknar lösningar (eller för att hitta dem om det finns!) är att välja några värden på $n$ och se om ekvationen (alltså motsvarande kongruens) har någon lösning modulo $n$.
Det fiffiga med moduloräkning är att det bara finns ett ändligt antal kongruensklasser. Skulle vi till exempel undersöka den här ekvationen modulo 3, finns det bara 9 olika fall. Det finns 3 kongruensklasser, och var och en av $x$ och $y$ måste tillhöra någon av dem. Nu visar det sig att ekvationen har lösningar modulo 3, till exempel $x\equiv 0$ och $y\equiv 1$. Då kan vi inte dra någon slutsats. Bara för att ekvationen har lösningar modulo 3 behöver det inte finnas någon "riktig" lösning.
Om vi i stället väljer att titta på ekvationen modulo 13, händer något intressant. Eftersom termen $13y^2$ då blir kongruent med 0, spelar det ingen roll vad $y$ är, utan vi får ett villkor på bara $x$, nämligen \[x^3 \equiv 2 \quad (\text{mod $n$}).\] Det finns bara 13 fall att testa, så vi kan göra en tabell och gå igenom alla. Enklast blir det om vi testar $x$ i intervallet $-6\leq x \leq 6$, eftersom $(-x)^3 = -x^3$. Men 13 konsekutiva tal vilka som helst går bra, vi måste bara få med ett tal i varje kongruensklass, så att vi täcker in alla fall.
Vi har
$0^3\equiv 0$, $1^3 \equiv 1$, $2^3 \equiv 8$, $3^3\equiv 1$, $4^3\equiv 12$, $5^3\equiv 8$, $6^3\equiv 8$.
Samt $(-1)^3\equiv -1 \equiv 12$, $(-2)^3 \equiv -8 \equiv 5$, $(-3)^3\equiv -1\equiv 12$, $(-4)^3 \equiv -12 \equiv 1$, $(-5)^3\equiv -8\equiv 5$, och $(-6)^3\equiv -8\equiv 5$.
Då har vi testat alla kongruensklasser, och ser att oavsett värde på $x$, så måste $x^3$ vara kongruent med något av talen 0, 1, 5, 8, och 12. Det blir alltså aldrig kongruent med 2, och därför kan ekvationen inte ha några heltalslösningar.
Jag såg också att någon har postat den här uppgiften på pluggakuten. Jag har ju sagt att ni får diskutera uppgifterna (och det är i själva verket ett pedagogiskt "trick" från min sida), så det här är inget som är förbjudet. I det här fallet har någon svarat på ett bra sätt utan att skriva en hel lösning. Så då kan jag lika gärna länka härifrån så blir det rättvist och bra!
På uppgift 8 krävs inte mycket motivering, men något litet nyckelord vill jag att ni skriver som förklaring.
Uppgift 9 verkar vara ganska "straightforward".
Uppgift 10 handlar om grafer, uppspännande träd, och isomorfi. Antalet uppspännande träd i $K_4$ efterfrågas även i uppgift 7.14 i boken. Notera att villkoret att grafen ska vara sammanhängande (som det står i uppgift 7.14) inte är nödvändigt för själva definitionen av begreppet uppspännande träd. Det är bara det att det inte finns några om grafen inte är sammanhängande. Det villkoret behöver ni således inte fundera över.
Isomorfi är en ekvivalensrelation, och de uppspännande träden i $K_4$ kan alltså delas in i klasser, där träd i samma klass är isomorfa, och träd i olika klasser inte är isomorfa.
Saturday, February 28, 2015
Om Eulers $\phi$-funktion och lite annat
Här är en sak man kan klottra på en papperslapp om det blir långtråkigt på föreläsningen. Skriv två ettor på en rad på ett papper, en bra bit ifrån varandra, så att det får plats saker mellan dem. Så här:
\[ 1 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad 1\]
Nu drar vi igång en process där det i princip kommer att hamna oändligt många tal på raden mellan ettorna. Man får hålla på tills man tröttnar eller det inte får plats fler. Regeln är att när det står två tal bredvid varandra, och med bredvid menas då att inga andra tal står mellan dem, så får man skriva deras summa någonstans i mellanrummet. Annorlunda uttryckt: Man får skriva in ett tal var man vill, och när man har bestämt sig för var det ska stå, så tittar man till höger och till vänster, och tar summan av de två talen.
Vi skriver alltså en tvåa mellan ettorna:
\[ 1 \qquad \qquad \qquad \qquad \qquad 2 \qquad \qquad \qquad \qquad \qquad 1\]
Och sedan två stycken treor i de nya mellanrummen:
\[ 1 \qquad \qquad \quad 3 \quad \qquad \qquad 2 \qquad \qquad \quad 3 \quad \qquad \qquad 1\]
I nästa steg blir det
\[ 1 \qquad \quad 4 \quad \qquad 3 \quad \qquad 5 \qquad \quad 2 \qquad \quad 5 \qquad \quad 3 \quad \qquad 4 \qquad \quad 1\]
Och sedan
\[ 1 \quad 5 \quad 4 \quad 7 \quad 3 \quad 8 \quad 5 \quad 7 \quad 2 \quad 7 \quad 5 \quad 8 \quad 3 \quad 7 \quad 4 \quad 5 \quad 1\]
och sedan
\[ 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1\]
Efter ett tag verkar det som om vissa tal har en tendens att förekomma oftare än andra. Talen bildas ju genom att vi summerar två tal som vi redan har, men det är nästan som om de tal som inte uppkommer genom multiplikationer nu kompenserar det genom att uppstå i additioner. 7 och 11 finns redan med fyra gånger var, och fler blir det, medan 6 bara har kommit med så som alla tal till slut måste, bredvid de ursprungliga ettorna i sjätte steget.
Eftersom talen bara blir större och större, inser man att varje tal bara kommer att finnas med ett ändligt antal gånger. Om vi räknar de ursprungliga två ettorna som steg 1, kommer alla tal som bildas i steg $n$ att vara minst $n$ (bevisas med induktion!). Så efter $n$ steg kommer talet $n$ inte att bildas mer. Vi skulle därför kunna göra en tabell över hur många gånger varje tal förekommer:
Om man bara är intresserad av att utöka den här tabellen något, kan man spara plats genom att i steg $n$ bara ta med talet $n$, och vänta med att fylla i alla större tal tills det blir deras tur. Då skulle vi få, efter 7 steg:
\[ 1 7 6 5 4 7 3 5 7 2 7 5 3 7 4 5 6 7 1 \]
Nu fyller vi i 8 på de fyra ställen där det blir 8: $1+7$, $3+5$, $5+3$, och $7+1$.
\[ 1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1 \]
Sedan fyller vi i 9 på de 6 ställen där det blir 9, och så håller vi på upp till 12, säg.
\[ 1 12 11 10 9 8 7 6 11 5 9 4 11 7 10 3 11 8 5 12 7 9 11 2\dots \] \[ \dots 11 9 7 12 5 8 11 3 10 7 11 4 9 5 11 6 7 8 9 10 11 12 1\]
Nu blev det en ganska lång rad, men vi kan ju bryta vid tvåan i mitten, för andra halvan är ju bara första baklänges. Nu kan vi utöka vår tabell:
Vi ser att talet 11 förekom hela 10 gånger, och att faktiskt varje sätt att få 11 som en summa av två positiva heltal uppstod exakt en gång. Talet 12 däremot, uppstod bara fyra gånger, som $1+11$, $5+7$, $7+5$, och $11+1$.
Den som har övat på det här med Euklides algoritm och största gemensam delare, märker nu någonting skoj: Det verkar som om två tal bara kan hamna bredvid varandra någonsin i den här processen om deras största gemensamma delare är 1!
Har man väl gjort den observationen, är det inte svårt att bevisa den med induktion. Om vi någonstans i processen har talen $a$ och $b$, och skriver in summan $a+b$ i mellanrummet, så får vi \[\dots a \quad a+b \quad b \dots\]
Om $a$ och $a+b$ skulle ha en gemensam delare $d$, så skulle $d$ dela även $b$, eftersom $b=(a+b)-a$. På samma sätt måste varje gemensam delare till $a+b$ och $b$ också dela $a$. Om vi startar med en talrad där konsekutiva tal alltid har största gemensam delare 1, kommer den egenskapen alltså att bevaras. Och vi startade ju med bara två ettor, så enligt induktionsprincipen kommer intilliggande tal alltid att ha största gemensam delare 1.
Det betyder att talet 12 till exempel, bara kan uppstå som en av de fyra summorna $1+11$, $5+7$, $7+5$, och $11+1$. Alla andra sätt, till exempel $4+8$ eller $9+3$, har en gemensam delare 2 eller 3, och kan aldrig hamna bredvid varandra. Talet 11 däremot kan uppstå på alla 10 tänkbara sätt, $1+10, 2+9, \dots, 10+1$ . Men förklarar detta varför 11 och 12 förekommer exakt 10 respektive 4 gånger? Nja, det verkar ju som om varje talpar med största gemensam delare 1 förekommer exakt en gång, och i så fall skulle ju saken vara klar, men det återstår ju i så fall att bevisa.
Så hur bevisar man en sådan sak? Hint, det är samma svar på den här frågan som det har varit varje gång jag hittills har kastat den frågan ut i föreläsningssalen.
Induktion.
Om induktion har jag sagt att det är viktigt att ha klart för sig vad som är induktionsantagandet. Och för att veta vad som är induktionsantagandet måste man ha klart för sig vad det är man försöker bevisa. När vi nu pratar om att ett talpar $(a,b)$ förekommer intill varandra exakt en gång, menar vi alltså att talen $a$, $b$ kommer att stå intill varandra, i den ordningen, någon gång under processen, och att de kommer att fortsätta stå intill varandra tills vi skriver in deras summa mellan dem. Det är det som räknas som en gång. Om vi kör processen tills alla $a$ och $b$ har skrivits in, kan vi också säga att det finns exakt en förekomst av $a$ och exakt en förekomst av $b$ som någon gång har stått intill varandra (i den ordningen).
Anta att $a$ och $b$ är positiva heltal med största gemensam delare 1. Paret $a, b$ kan hamna intill varandra i den ordningen antingen genom att $b$ uppstår som summan av $a$ och ett annat tal, eller genom att $a$ uppstår som summan av $b$ och ett annat tal. Bara den ena varianten är tänkbar, för bara det större av $a$ och $b$ kan uppstå som en summa där det andra talet är inblandat. Om $a<b$, kan $a, b$ uppstå ur $a, b-a$, och om $a>b$, kan $a, b$ uppstå ur $a-b, b$. Om $a=b$ måste de vara lika med 1, för annars har de en gemensam delare. Men $1,1$ är basfallet i induktionen. Själva induktionssteget då? Ja, här använder vi så kallad "stark induktion", och induktionsantagandet får bli "alla par av positiva heltal med största gemensam delare 1, vars summa är högst $n$, förekommer exakt en gång i processen". Om $a, b$ är ett par vars summa är $n+1$, utnyttjar vi induktionsantagandet och drar slutsatsen att antingen $a, b-a$ eller $a-b, b$ förekommer exakt en gång (beroende på vilket av $a-b$ och $b-a$ som är positivt). Paret $a, b$ måste då också förekomma exakt en gång, och induktionssteget är klart.
Den som har läst om Eulers $\phi$-funktion känner igen talen i tabellen, och inser att vad vi har bevisat är att varje tal $n>1$ kommer att förekomma exakt $\phi(n)$ gånger. Det stämmer inte riktigt för $n=1$, eftersom vi startar med två ettor, men $\phi(1)=1$. Kanske borde vi tänka oss att talen står på en cirkel och att vi börjar med en enda etta, så att ettan till vänster egentligen är samma som ettan till höger.
Se också the Stern-Brocot tree! Och särskilt nämnarna i delen mellan 0 och 1.
\[ 1 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad 1\]
Nu drar vi igång en process där det i princip kommer att hamna oändligt många tal på raden mellan ettorna. Man får hålla på tills man tröttnar eller det inte får plats fler. Regeln är att när det står två tal bredvid varandra, och med bredvid menas då att inga andra tal står mellan dem, så får man skriva deras summa någonstans i mellanrummet. Annorlunda uttryckt: Man får skriva in ett tal var man vill, och när man har bestämt sig för var det ska stå, så tittar man till höger och till vänster, och tar summan av de två talen.
Vi skriver alltså en tvåa mellan ettorna:
\[ 1 \qquad \qquad \qquad \qquad \qquad 2 \qquad \qquad \qquad \qquad \qquad 1\]
Och sedan två stycken treor i de nya mellanrummen:
\[ 1 \qquad \qquad \quad 3 \quad \qquad \qquad 2 \qquad \qquad \quad 3 \quad \qquad \qquad 1\]
I nästa steg blir det
\[ 1 \qquad \quad 4 \quad \qquad 3 \quad \qquad 5 \qquad \quad 2 \qquad \quad 5 \qquad \quad 3 \quad \qquad 4 \qquad \quad 1\]
Och sedan
\[ 1 \quad 5 \quad 4 \quad 7 \quad 3 \quad 8 \quad 5 \quad 7 \quad 2 \quad 7 \quad 5 \quad 8 \quad 3 \quad 7 \quad 4 \quad 5 \quad 1\]
och sedan
\[ 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1\]
Efter ett tag verkar det som om vissa tal har en tendens att förekomma oftare än andra. Talen bildas ju genom att vi summerar två tal som vi redan har, men det är nästan som om de tal som inte uppkommer genom multiplikationer nu kompenserar det genom att uppstå i additioner. 7 och 11 finns redan med fyra gånger var, och fler blir det, medan 6 bara har kommit med så som alla tal till slut måste, bredvid de ursprungliga ettorna i sjätte steget.
Eftersom talen bara blir större och större, inser man att varje tal bara kommer att finnas med ett ändligt antal gånger. Om vi räknar de ursprungliga två ettorna som steg 1, kommer alla tal som bildas i steg $n$ att vara minst $n$ (bevisas med induktion!). Så efter $n$ steg kommer talet $n$ inte att bildas mer. Vi skulle därför kunna göra en tabell över hur många gånger varje tal förekommer:
| $n$ | Antal förekomster |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 4 |
| 6 | 2 |
Om man bara är intresserad av att utöka den här tabellen något, kan man spara plats genom att i steg $n$ bara ta med talet $n$, och vänta med att fylla i alla större tal tills det blir deras tur. Då skulle vi få, efter 7 steg:
\[ 1 7 6 5 4 7 3 5 7 2 7 5 3 7 4 5 6 7 1 \]
Nu fyller vi i 8 på de fyra ställen där det blir 8: $1+7$, $3+5$, $5+3$, och $7+1$.
\[ 1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1 \]
Sedan fyller vi i 9 på de 6 ställen där det blir 9, och så håller vi på upp till 12, säg.
\[ 1 12 11 10 9 8 7 6 11 5 9 4 11 7 10 3 11 8 5 12 7 9 11 2\dots \] \[ \dots 11 9 7 12 5 8 11 3 10 7 11 4 9 5 11 6 7 8 9 10 11 12 1\]
Nu blev det en ganska lång rad, men vi kan ju bryta vid tvåan i mitten, för andra halvan är ju bara första baklänges. Nu kan vi utöka vår tabell:
| $n$ | Antal förekomster |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 4 |
| 6 | 2 |
| 7 | 6 |
| 8 | 4 |
| 9 | 6 |
| 10 | 4 |
| 11 | 10 |
| 12 | 4 |
Vi ser att talet 11 förekom hela 10 gånger, och att faktiskt varje sätt att få 11 som en summa av två positiva heltal uppstod exakt en gång. Talet 12 däremot, uppstod bara fyra gånger, som $1+11$, $5+7$, $7+5$, och $11+1$.
Den som har övat på det här med Euklides algoritm och största gemensam delare, märker nu någonting skoj: Det verkar som om två tal bara kan hamna bredvid varandra någonsin i den här processen om deras största gemensamma delare är 1!
Har man väl gjort den observationen, är det inte svårt att bevisa den med induktion. Om vi någonstans i processen har talen $a$ och $b$, och skriver in summan $a+b$ i mellanrummet, så får vi \[\dots a \quad a+b \quad b \dots\]
Om $a$ och $a+b$ skulle ha en gemensam delare $d$, så skulle $d$ dela även $b$, eftersom $b=(a+b)-a$. På samma sätt måste varje gemensam delare till $a+b$ och $b$ också dela $a$. Om vi startar med en talrad där konsekutiva tal alltid har största gemensam delare 1, kommer den egenskapen alltså att bevaras. Och vi startade ju med bara två ettor, så enligt induktionsprincipen kommer intilliggande tal alltid att ha största gemensam delare 1.
Det betyder att talet 12 till exempel, bara kan uppstå som en av de fyra summorna $1+11$, $5+7$, $7+5$, och $11+1$. Alla andra sätt, till exempel $4+8$ eller $9+3$, har en gemensam delare 2 eller 3, och kan aldrig hamna bredvid varandra. Talet 11 däremot kan uppstå på alla 10 tänkbara sätt, $1+10, 2+9, \dots, 10+1$ . Men förklarar detta varför 11 och 12 förekommer exakt 10 respektive 4 gånger? Nja, det verkar ju som om varje talpar med största gemensam delare 1 förekommer exakt en gång, och i så fall skulle ju saken vara klar, men det återstår ju i så fall att bevisa.
Så hur bevisar man en sådan sak? Hint, det är samma svar på den här frågan som det har varit varje gång jag hittills har kastat den frågan ut i föreläsningssalen.
Induktion.
Om induktion har jag sagt att det är viktigt att ha klart för sig vad som är induktionsantagandet. Och för att veta vad som är induktionsantagandet måste man ha klart för sig vad det är man försöker bevisa. När vi nu pratar om att ett talpar $(a,b)$ förekommer intill varandra exakt en gång, menar vi alltså att talen $a$, $b$ kommer att stå intill varandra, i den ordningen, någon gång under processen, och att de kommer att fortsätta stå intill varandra tills vi skriver in deras summa mellan dem. Det är det som räknas som en gång. Om vi kör processen tills alla $a$ och $b$ har skrivits in, kan vi också säga att det finns exakt en förekomst av $a$ och exakt en förekomst av $b$ som någon gång har stått intill varandra (i den ordningen).
Anta att $a$ och $b$ är positiva heltal med största gemensam delare 1. Paret $a, b$ kan hamna intill varandra i den ordningen antingen genom att $b$ uppstår som summan av $a$ och ett annat tal, eller genom att $a$ uppstår som summan av $b$ och ett annat tal. Bara den ena varianten är tänkbar, för bara det större av $a$ och $b$ kan uppstå som en summa där det andra talet är inblandat. Om $a<b$, kan $a, b$ uppstå ur $a, b-a$, och om $a>b$, kan $a, b$ uppstå ur $a-b, b$. Om $a=b$ måste de vara lika med 1, för annars har de en gemensam delare. Men $1,1$ är basfallet i induktionen. Själva induktionssteget då? Ja, här använder vi så kallad "stark induktion", och induktionsantagandet får bli "alla par av positiva heltal med största gemensam delare 1, vars summa är högst $n$, förekommer exakt en gång i processen". Om $a, b$ är ett par vars summa är $n+1$, utnyttjar vi induktionsantagandet och drar slutsatsen att antingen $a, b-a$ eller $a-b, b$ förekommer exakt en gång (beroende på vilket av $a-b$ och $b-a$ som är positivt). Paret $a, b$ måste då också förekomma exakt en gång, och induktionssteget är klart.
Den som har läst om Eulers $\phi$-funktion känner igen talen i tabellen, och inser att vad vi har bevisat är att varje tal $n>1$ kommer att förekomma exakt $\phi(n)$ gånger. Det stämmer inte riktigt för $n=1$, eftersom vi startar med två ettor, men $\phi(1)=1$. Kanske borde vi tänka oss att talen står på en cirkel och att vi börjar med en enda etta, så att ettan till vänster egentligen är samma som ettan till höger.
Se också the Stern-Brocot tree! Och särskilt nämnarna i delen mellan 0 och 1.
Wednesday, February 25, 2015
Om examinationen
Det blir tenta tisdagen den17 mars kl 14-18. Tentan är det enda obligatoriska examinationsmomentet. Vi har / har haft 2 duggor, som var och en kan ge 2 bonuspoäng på tentan. Tentan i sin tur kan ge maximalt 40 poäng, och 20 poäng räcker för godkänt.
Inga miniräknare kommer att vara tillåtna på tentan. Det kommer på en del uppgifter att krävas vissa beräkningar (t ex Euklides algoritm), men dem är det meningen att man ska kunna göra för hand!
Dock kommer det att vara tillåtet att ha med sig ett A4-ark med egna handskrivna anteckningar (egen "formelsamling"), och på förfrågan vill jag minnas att jag har svarat att man får skriva på båda sidorna av arket. Det får vara vilka anteckningar som helst, till exempel lösta övningsuppgifter, men det är en pedagogisk poäng med att man ska ha skrivit ner dem själv, så det får inte vara någon datorutskrift eller kopia.
Inga miniräknare kommer att vara tillåtna på tentan. Det kommer på en del uppgifter att krävas vissa beräkningar (t ex Euklides algoritm), men dem är det meningen att man ska kunna göra för hand!
Dock kommer det att vara tillåtet att ha med sig ett A4-ark med egna handskrivna anteckningar (egen "formelsamling"), och på förfrågan vill jag minnas att jag har svarat att man får skriva på båda sidorna av arket. Det får vara vilka anteckningar som helst, till exempel lösta övningsuppgifter, men det är en pedagogisk poäng med att man ska ha skrivit ner dem själv, så det får inte vara någon datorutskrift eller kopia.
Monday, February 23, 2015
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?
Friday, February 6, 2015
Lista på begrepp att kunna
Begrepp att kunna (nu kap 1-4, kommer att fyllas på)
Utsaga
Konnektiv ($\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$)
Sanningstabell
Tautologi
Logisk konsekvens
Predikat
Kvantifikatorer ($\forall$ och $\exists$)
Mängder
Element
Tillhör ($\in$)
Tomma mängden ($\emptyset$)
Delmängd ($\subseteq$)
Standardmängder ($\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$, intervall).
Union ($\cup$)
Snitt ($\cap$)
Mängddifferens ($\backslash$)
Symmetrisk differens ($\triangle$)
Kartesisk produkt ($A \times B$)
Potensmängd ($\wp$)
Funktion
Definitionsmängd, målmängd, värdemängd, bild
Funktionsgraf
Injektiva, surjektiva, bijektiva funktioner
Sammansatta funktioner
Invers
Operatorer
Kommutativa, associativa operatorer
Identitetselement, invers (med avseende på en operator)
Relationer
Reflexiva, symmetriska, antisymmetriska, transitiva relationer
Partiell ordning
Ekvivalensrelation
$\sum$ och $\prod$
Induktionsprincipen
Induktionsantagande (=induktionshypotes)
Rekursiva definitioner av talföljder (t ex Fibonaccitalen)
Motsägelsebevis
Största gemensam delare
Euklides algoritm
Kongruens, kongruensklass
Primtal
Diofantisk ekvation
Kinesiska restsatsen
Kryptering
RSA
Multiplikationsprincipen
Binomialkoefficient
Permutation
Pascals triangel
$n!$ ("fakultet")
Graf
Nod
Kant
Grad (av nod i en graf)
Komponent
Sammanhängande
Isomorfi (grafer)
Cykel
Träd
Fullständiga grafen $K_n$
Utsaga
Konnektiv ($\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$)
Sanningstabell
Tautologi
Logisk konsekvens
Predikat
Kvantifikatorer ($\forall$ och $\exists$)
Mängder
Element
Tillhör ($\in$)
Tomma mängden ($\emptyset$)
Delmängd ($\subseteq$)
Standardmängder ($\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$, intervall).
Union ($\cup$)
Snitt ($\cap$)
Mängddifferens ($\backslash$)
Symmetrisk differens ($\triangle$)
Kartesisk produkt ($A \times B$)
Potensmängd ($\wp$)
Funktion
Definitionsmängd, målmängd, värdemängd, bild
Funktionsgraf
Injektiva, surjektiva, bijektiva funktioner
Sammansatta funktioner
Invers
Operatorer
Kommutativa, associativa operatorer
Identitetselement, invers (med avseende på en operator)
Relationer
Reflexiva, symmetriska, antisymmetriska, transitiva relationer
Partiell ordning
Ekvivalensrelation
$\sum$ och $\prod$
Induktionsprincipen
Induktionsantagande (=induktionshypotes)
Rekursiva definitioner av talföljder (t ex Fibonaccitalen)
Motsägelsebevis
Största gemensam delare
Euklides algoritm
Kongruens, kongruensklass
Primtal
Diofantisk ekvation
Kinesiska restsatsen
Kryptering
RSA
Multiplikationsprincipen
Binomialkoefficient
Permutation
Pascals triangel
$n!$ ("fakultet")
Graf
Nod
Kant
Grad (av nod i en graf)
Komponent
Sammanhängande
Isomorfi (grafer)
Cykel
Träd
Fullständiga grafen $K_n$
Thursday, February 5, 2015
Hintar till Dugga 1
Några kommentarer till duggan;
Uppgift 2, tänk på att relationerna tillhör ($\in$) och delmängd ($\subseteq$) är olika saker. En mängd skriven i klammernotation, till exempel $\{1,2,3\}$ har elementen 1, 2, och 3, och inga andra. Det som räknas upp mellan klamrarna, i det här fallet talen 1, 2, och 3, tillhör alltså denna mängd, vilket skrivs $1\in \{1,2,3\}$ osv. Men inget annat tillhör mängden.
Uppgift 3, tänk på att det är fullt tillåtet att definiera en funktion genom olika uttryck för olika $x$-värden, till exempel
\[ f(x) = \begin{cases} \text{Ett uttryck}, \quad \text{om $0\leq x \leq 1/2$},\\ \text{Annat uttryck}, \quad \text{om $1/2 < x \leq 1$},\end{cases}
\]
På så sätt kan man sy ihop funktioner av olika delar. Tänk dock på att alla tal i definitionsmängden måste få ett funktionsvärde.
Om man har gjort 3a, kan man utnyttja det i uppgift 3b genom att bilda någon lämplig typ av invers till funktionen i 3a.
Uppgift 2, tänk på att relationerna tillhör ($\in$) och delmängd ($\subseteq$) är olika saker. En mängd skriven i klammernotation, till exempel $\{1,2,3\}$ har elementen 1, 2, och 3, och inga andra. Det som räknas upp mellan klamrarna, i det här fallet talen 1, 2, och 3, tillhör alltså denna mängd, vilket skrivs $1\in \{1,2,3\}$ osv. Men inget annat tillhör mängden.
Uppgift 3, tänk på att det är fullt tillåtet att definiera en funktion genom olika uttryck för olika $x$-värden, till exempel
\[ f(x) = \begin{cases} \text{Ett uttryck}, \quad \text{om $0\leq x \leq 1/2$},\\ \text{Annat uttryck}, \quad \text{om $1/2 < x \leq 1$},\end{cases}
\]
På så sätt kan man sy ihop funktioner av olika delar. Tänk dock på att alla tal i definitionsmängden måste få ett funktionsvärde.
Om man har gjort 3a, kan man utnyttja det i uppgift 3b genom att bilda någon lämplig typ av invers till funktionen i 3a.
Tuesday, February 3, 2015
Dugga 1
Lämnas in senast vid början av föreläsningen måndagen den 9 februari.
- Vilka av följande satslogiska utsagor är tautologier?
- $(p \vee \neg q) \leftrightarrow (q \rightarrow p)$
- $((p \wedge q) \vee r) \rightarrow (p \wedge (q \vee r))$
- $(p \rightarrow q) \vee (q \rightarrow r)$
- Ge exempel på
- Två mängder $A$ och $B$ sådana att $A\subseteq B$ men $A\notin B$,
- Två mängder $C$ och $D$ sådana att $C\nsubseteq D$ men $C\in D$,
- Två mängder $E$ och $F$ sådana att $E\subseteq F$ och $E\in F$.
- Ge exempel på
- En surjektiv funktion från intervallet $[0,1]$ till $\mathbb{R}$,
- En injektiv funktion från $\mathbb{R}$ till $[0,1]$.
- Uttryck den konvergenta summan \[1+\frac18 + \frac1{27} + \frac1{64} +\dots \] med hjälp av $\sum$-symbolen.
- Bevisa, till exempel med induktion, att \[\sum_{k=1}^n k^3 = \frac{n^2(n+1)^2}4.\]
Sunday, January 25, 2015
Hello Diskret Matematik!
Då drar jag igång en blogg för kursen i Diskret Matematik MVE070 för DI2/EI2, eftersom jag tycker det har fungerat bra som ett komplement till den övriga kommunikationen (och eftersom jag fick medhåll vid utvärderingen av den linjäralgebrakurs jag höll i höstas).
Ska bara testa att det här med MathJax funkar, så man kan skriva matematiska uttryck:
\[1 \in \omega = \mathbb{N} = \{0,1,2,\dots\} = \aleph_0.\]
Verkar ok, men det kan se konstigt ut om ni läser på telefonen.
Kursbok är Algebra och Diskret Matematik av mina kollegor Johan Jonasson och Stefan Lemurell, Studentlitteratur. Närmare bestämt den andra upplagan (2013). Den första upplagan, från 2003, torde också fungera, dvs har man den eller får tag på den billigt bör man inte behöva köpa den nya. Däremot kommer kapitlen i annan ordning i den boken, och jag har inte kontrollerat i vilken mån övningsuppgifterna skiljer sig åt.
Kursen kommer att behandla kapitlen 1-7 i boken, samt använda en del terminologi från kapitel 9 (sannolikhetslära). Det sistnämnda bör inte bli några problem, eftersom ni parallellt läser en kurs i matematisk statistik där begrepp som sannolikheter, väntevärde mm är grundläggande.
En grov planering av föreläsningarna är som följer. Det här kan behöva justeras något steg efter hand, men detta kommer i så fall att framgå av kommande bloggposter. Jag misstänker att kapitel 5 om talteorin är det som kommer att vara ganska svårt, medan övriga kapitel visserligen innehåller en hel del begrepp och notation, men i princip "bara" är att läsa. Induktionsbevis förresten, brukar också kräva en hel del träning och tid att smälta.
Mer info kommer inom kort om duggor och annat!
Måndagsföreläsningarna är kl 10.15-12.00 och de på torsdagar 8.15-10.00. Dessutom är det övningslektioner en gång i veckan indelat i grupper (hittar just nu ingen schemalänk som inte kräver inloggning).
Ska bara testa att det här med MathJax funkar, så man kan skriva matematiska uttryck:
\[1 \in \omega = \mathbb{N} = \{0,1,2,\dots\} = \aleph_0.\]
Verkar ok, men det kan se konstigt ut om ni läser på telefonen.
Kursbok är Algebra och Diskret Matematik av mina kollegor Johan Jonasson och Stefan Lemurell, Studentlitteratur. Närmare bestämt den andra upplagan (2013). Den första upplagan, från 2003, torde också fungera, dvs har man den eller får tag på den billigt bör man inte behöva köpa den nya. Däremot kommer kapitlen i annan ordning i den boken, och jag har inte kontrollerat i vilken mån övningsuppgifterna skiljer sig åt.
Kursen kommer att behandla kapitlen 1-7 i boken, samt använda en del terminologi från kapitel 9 (sannolikhetslära). Det sistnämnda bör inte bli några problem, eftersom ni parallellt läser en kurs i matematisk statistik där begrepp som sannolikheter, väntevärde mm är grundläggande.
En grov planering av föreläsningarna är som följer. Det här kan behöva justeras något steg efter hand, men detta kommer i så fall att framgå av kommande bloggposter. Jag misstänker att kapitel 5 om talteorin är det som kommer att vara ganska svårt, medan övriga kapitel visserligen innehåller en hel del begrepp och notation, men i princip "bara" är att läsa. Induktionsbevis förresten, brukar också kräva en hel del träning och tid att smälta.
Mer info kommer inom kort om duggor och annat!
Måndagsföreläsningarna är kl 10.15-12.00 och de på torsdagar 8.15-10.00. Dessutom är det övningslektioner en gång i veckan indelat i grupper (hittar just nu ingen schemalänk som inte kräver inloggning).
| Tillfälle | Datum, Sal | Bokavsnitt | Innehåll |
|---|---|---|---|
| 1 | må 19/1 Alfa | kap 1 | Översikt. Satslogik. Konnektiv, sanningstabeller, tautologi, logisk konsekvens. Predikatlogik, predikat och kvantifikatorer. Betydelse av kvantifikatorernas ordning. Övningar 1: 7, 10, 11, 12, 17. |
| 2 | to 22/1 Alfa | kap 2 | Mängdlära. Begrepp och operationer på mängder. Russells paradox. Övningar 2: 1, 2, 3, 5, 6, 9, 16. |
| 3 | må 26/1 Delta | 3.1-3.4 | Repetition kap 1-2. Funktioner. Definitionsmängd, målmängd, värdemängd. Injektiva, surjektiva och bijektiva funktioner. Inversa funktioner. Sammansatta funktioner. Binära operatorer. Övningar 3: 1, 4, 5, 7, 8, 13, 15 |
| 4 | to 29/1 Alfa | 3.5-3.10 | Summasymbolen $\Sigma$ och liknande symboler. Användning av "dummyvariabler". Relationer, ekvivalensrelationer, partiella ordningar. Övningar 3: 16, 17 |
| 5 | må 2/2 Delta | 4.1-4.3 | Bevismetoder: induktion. Induktionsprincipen definierar de naturliga talen! Hur man skriver induktionsbevis. Rekursiva definitioner. Fibonaccitalen, aritmetiska och geometriska summor. Övningar 4: 1 (med på duggan!) 2, 3, 4,... |
| 6 | to 5/2 Alfa | 4.4-4.5 | Bevismetoder: motsägelsebevis. Euklides bevis för oändligt många primtal. |
| 7 | må 9/2 Alfa | 5.1-5.3 | Dugga 1 in. Talteori: Delbarhet, kvot, rest. Euklides algoritm för störst gemensamma delare. Diofantiska ekvationer. Primtal, aritmetikens fundamentalats. Övningar 5: 1,2,5,6,9,10, ... |
| 8 | to 12/2 Alfa | 5.4-5.6 | Kongruensräkning (moduloräkning). Addition, multiplikation, potenser. Kinesiska restsatsen. Eulers $\phi$-funktion, Eulers sats, Fermats "lilla" sats. |
| 9 | må 16/2 Alfa | 5.7-5.8 | Tillämpningar inom kryptering och säkerhet: Rabin-Millers primtalstest, lite om svårigheten att faktorisera stora heltal. Diffie-Hellman och RSA-kryptering. Lite om hur RSA används (för att kryptera nycklar till "klassiska" krypteringsmetoder). |
| 10 | to 19/2 Alfa | kap 1-5 | Reservtid, repetition kap 1-5. |
| 11 | må 23/2 Alfa | 6.1-6.4 | Enumerativ kombinatorik. Multiplikationsprincipen. Permutationer,
kombinationer, fakultet, binomialkoefficienter, binomialsatsen. Pascals
triangel. Lite om kopplingar till sannolikhetsteorin (kap 9 och kursen i matematisk statistik). Övningar kap 6: 5, 11. |
| 12 | to 26/2 Alfa | kap 7 | Grafteori. Övningar kap 7: 1, 10, 11, 14. |
| 13 | må 2/3 Alfa | Dugga 2 in. Repetition. | |
| 14 | to 5/3 Alfa | Repetition. | |
| Tenta! | ti 17/3 kl. 14-18. | kap 1-7 | Tenta! |
Subscribe to:
Posts (Atom)