1. På a, b, c har många tänkt att jag menade heltal, vilket jag har godkänt eftersom jag faktiskt var ltie otydlig i uppgiften. På d, e, f har de flesta förstått vilka tal som ska ingå i mängderna, dvs vilka lösningar som finns till respektive ekvation. Däremot har det varit problem med att uttrycka de här mängderna på enklast möjliga sätt. Om en mängd har ett ändligt (och inte alltför stort) antal element, är det bara att räkna upp dem. Den mängd som har elementen 1, 2 och 17 kan till exempel skrivas $\{1,2,17\}$.
Tänk på att $x$, $n$ och $r$ är "lokala" variabler. På 1d är det till exempel inte så at $x = \{1\}$. Svaret är att mängden i fråga är lika med $\{1\}$. Men vi har inte definierat någonting som heter $x$.
2. De flesta verkar ha förstått hur detta fungerar, men förklaringarna var ganska ofullständiga. Många ger exempel på ett tal, vilket jag tycker fungerar bra som förklaring i just det här fallet.
3. Den här uppgiften, att beräkna största gemensamma delare till två tal, har gått ganska bra. En bra sak som några gör är att i slutläget kontrollera att 232 faktiskt är en delare till båda de givna talen.
4. Här har det blivit en del problem. Många ställer upp ekvationen i två variabler $x$ och $y$ som vi har sagt att man ska göra, men svarar inte riktigt på frågan. Det är ganska vanligt att man har svarat på både vad $x$ är och vad $y$ är, fast jag bara frågade efter $x$ ($y$ fanns ju inte i frågan från början). Några har svarat till exempel att $x = 50 + 19k$, vilket jag har godkänt, fast det egentligen är bättre att svara med den principala resten 12, alltså $x = 12 + 19k$.
I några fall har det varit ganska otydligt vad som är svaret mitt i alla räkningar.
5. Den här uppgiften har också gått bra. Många har inte redovisat så mycket, men det var väl heller inte meningen.
Thursday, February 18, 2016
Wednesday, February 10, 2016
Vad man bör kunna i kapitel 3 (Aritmetik)
Vi har nu tagit oss igenom kapitel 3 om aritmetik (talteori). Det kan vara dags att sammanfatta lite vad man bör kunna.
Division, kvot och rest. Detta är ju i den enklaste formen grundskolematematik; $47/11 = 4+3/11$. Här är "kvoten" 4, dvs 11 "går i" 47 4 gånger. Resten blir 3.
Delbarhet. Notationen $a | b$ betyder att $a$ delar $b$. Till exempel gäller att $14|42$ därför att $42$ kan skrivas som $14$ gånger ett heltal (3). Med andra ord $42/14$ är ett heltal.
Primtal är heltal större än 1 som inte har några andra delare än $\pm 1$ och (plus/minus) sig själva. Till exempel är 439 ett primtal därför att de enda tal som delar 439 är $\pm 1$ och $\pm 439$. Talet 440 är å andra sidan inte ett primtal, eftersom det har andra elare, till exempel 2, 5, 10 och 11. Talet $440$ kan faktoriseras som en produkt av primtal: $440 = 2\cdot 2\cdot 2\cdot 5 \cdot 11$.
Det finns oändligt många primtal, vilket bevisades av Euklides ungefär år 300 f Kr.
Enligt aritmetikens fundamentalsats kan varje positivt heltal skrivas som en produkt av primtal på (väsentligen) exakt ett sätt. Reservationen "väsentligen" syftar på att man givetvis kan skriva primfaktorerna i olika ordning, men varje primtal förekommer ett bestämt antal gånger. Om man till exempel skriver 440 som en produkt av primtal, kommer talet 2 alltid att förekomma exakt tre gånger.
Delargrafen till ett tal är ingenting man behöver plugga in för dess egen skull. Den är bara till för att underlätta förståelsen, inte skapa nya problem.
En linjärkombination av två (eller flera) tal $x$ och $y$ är (precis som i linjäralgebran) ett uttryck på formen $ax+by$, där $a$ och $b$ är heltal. Om ett tal $d$ är gemensam delare till $x$ och $y$, så kommer $d$ också att dela $ax+by$.
Euklides algoritm är en metod för att beräkna de största gemensamma delaren till två tal $x$ och $y$, vilket samtidigt är den minsta positiva linjärkombinationen av $x$ och $y$.
Den minsta gemensamma multipeln $lcm(x,y)$ av två tal $x$ och $y$ är, som namnet antyder, det minsta tal som har både $x$ och $y$ som delare. Om man har beräknat största gemensamma delaren till $x$ och $y$, dvs $gcd(x,y)$, kan den minsta gemensamma multipeln beräknas genom \[lcm(x,y) = \frac{x\cdot y}{gcd(x,y)}.\]
När man adderar bråk, förlänger man så att bråken får "minsta gemensamma nämnare". De möjliga nämnarna är ju multipler av den ursprungliga, så "minsta gemensamma nämnare" betyder egentligen minsta gemensamma multipel (av nämnarna).
Diofantiska ekvationer betyder egentligen ekvationer där man söker heltalslösningar. De ekvationer vi tittar på i den här kursen är linjära ekvationer i två variabler, dvs ekvationer av typen \[ax + by = c,\] där konstanterna $a$, $b$ och $c$ är heltal. Geometriskt är lösningsmängden en rät linje i planet, så frågan är vilka heltalspunkter en sådan linje passerar genom. Sådana ekvationer löses med Euklides algoritm.
Modulär aritmetik eller kongruensräkning handlar om att man räknar "modulo $n$", där $n$ är något positivt heltal. Man kan också säga att man enbart räknar med "rester" vid division med $n$. Om man till exempel räknar modulo 12 (klockan), så är $4$, $16$ och $-8$ samma sak. Man säger att de talen är kongruenta modulo 12, vilket skrivs \[4 \equiv 16 \equiv -8 \quad \text{(mod 12)}.\]
Systemet av restklasser modulo $n$ betecknas $\mathbb{Z}_n$.
Ekvationer av typen $ax = b$ i $\mathbb{Z}_n$ kan reduceras till diofantiska ekvationer i två variabler, och löses alltså med Euklides algoritm.
Det finns även ett avsnitt om binära tal och andra talbaser. Man bör kunna konvertera tal mellan binärt och decimalt. Exempelvis är talet $77 = 64+8 + 4 +1$, så binärt skrivs 77 som $1001101$.
Division, kvot och rest. Detta är ju i den enklaste formen grundskolematematik; $47/11 = 4+3/11$. Här är "kvoten" 4, dvs 11 "går i" 47 4 gånger. Resten blir 3.
Delbarhet. Notationen $a | b$ betyder att $a$ delar $b$. Till exempel gäller att $14|42$ därför att $42$ kan skrivas som $14$ gånger ett heltal (3). Med andra ord $42/14$ är ett heltal.
Primtal är heltal större än 1 som inte har några andra delare än $\pm 1$ och (plus/minus) sig själva. Till exempel är 439 ett primtal därför att de enda tal som delar 439 är $\pm 1$ och $\pm 439$. Talet 440 är å andra sidan inte ett primtal, eftersom det har andra elare, till exempel 2, 5, 10 och 11. Talet $440$ kan faktoriseras som en produkt av primtal: $440 = 2\cdot 2\cdot 2\cdot 5 \cdot 11$.
Det finns oändligt många primtal, vilket bevisades av Euklides ungefär år 300 f Kr.
Enligt aritmetikens fundamentalsats kan varje positivt heltal skrivas som en produkt av primtal på (väsentligen) exakt ett sätt. Reservationen "väsentligen" syftar på att man givetvis kan skriva primfaktorerna i olika ordning, men varje primtal förekommer ett bestämt antal gånger. Om man till exempel skriver 440 som en produkt av primtal, kommer talet 2 alltid att förekomma exakt tre gånger.
Delargrafen till ett tal är ingenting man behöver plugga in för dess egen skull. Den är bara till för att underlätta förståelsen, inte skapa nya problem.
En linjärkombination av två (eller flera) tal $x$ och $y$ är (precis som i linjäralgebran) ett uttryck på formen $ax+by$, där $a$ och $b$ är heltal. Om ett tal $d$ är gemensam delare till $x$ och $y$, så kommer $d$ också att dela $ax+by$.
Euklides algoritm är en metod för att beräkna de största gemensamma delaren till två tal $x$ och $y$, vilket samtidigt är den minsta positiva linjärkombinationen av $x$ och $y$.
Den minsta gemensamma multipeln $lcm(x,y)$ av två tal $x$ och $y$ är, som namnet antyder, det minsta tal som har både $x$ och $y$ som delare. Om man har beräknat största gemensamma delaren till $x$ och $y$, dvs $gcd(x,y)$, kan den minsta gemensamma multipeln beräknas genom \[lcm(x,y) = \frac{x\cdot y}{gcd(x,y)}.\]
När man adderar bråk, förlänger man så att bråken får "minsta gemensamma nämnare". De möjliga nämnarna är ju multipler av den ursprungliga, så "minsta gemensamma nämnare" betyder egentligen minsta gemensamma multipel (av nämnarna).
Diofantiska ekvationer betyder egentligen ekvationer där man söker heltalslösningar. De ekvationer vi tittar på i den här kursen är linjära ekvationer i två variabler, dvs ekvationer av typen \[ax + by = c,\] där konstanterna $a$, $b$ och $c$ är heltal. Geometriskt är lösningsmängden en rät linje i planet, så frågan är vilka heltalspunkter en sådan linje passerar genom. Sådana ekvationer löses med Euklides algoritm.
Modulär aritmetik eller kongruensräkning handlar om att man räknar "modulo $n$", där $n$ är något positivt heltal. Man kan också säga att man enbart räknar med "rester" vid division med $n$. Om man till exempel räknar modulo 12 (klockan), så är $4$, $16$ och $-8$ samma sak. Man säger att de talen är kongruenta modulo 12, vilket skrivs \[4 \equiv 16 \equiv -8 \quad \text{(mod 12)}.\]
Systemet av restklasser modulo $n$ betecknas $\mathbb{Z}_n$.
Ekvationer av typen $ax = b$ i $\mathbb{Z}_n$ kan reduceras till diofantiska ekvationer i två variabler, och löses alltså med Euklides algoritm.
Det finns även ett avsnitt om binära tal och andra talbaser. Man bör kunna konvertera tal mellan binärt och decimalt. Exempelvis är talet $77 = 64+8 + 4 +1$, så binärt skrivs 77 som $1001101$.
Tuesday, February 9, 2016
Lite om Dugga 1
Nu har vi kommit igång med kursen version 2016. Här följer några kommentarer till Hemdugga 1, efter några frågor som dök upp på måndagens övning. Duggan ska som sagt lämnas in på torsdag, vid början av föreläsningen.
På uppgift 1 a, b, c, har jag tänkt mig mängder av reella tal. Alla de här mängderna är alltså intervall. En annan sak man kan tänka på är att en mängd av till exempel typen $\{x : x=17\}$ enklare kan skrivas $\{17\}$.
På uppgift 2 är det inte absolut ristat i sten vilket svar som är det rätta, men meningen är att ni ska fundera på hur detta kan fungera, vad det har att göra med binär representation av tal, samt hur Nisse gör rent praktiskt för att på en sekund räkna ut vilket tal kompisen tänkte på. Om ni inte förstår vad jag är ute efter, är ett tips att skriva upp den binära representationen av talen 1 till 31, eller förresten, 0 till 31, med 5 bitar. Alltså börja med 0 = 00000, 1 = 00001, 2 = 00010, 3 = 00011 osv, upp till 31 = 11111.
Sedan kan man fundera på hur detta har att göra med de tal som står på respektive lapp.
På uppgift 4, tänk på att man inte alltid bara kan dividera ekvationen med 2. När det gäller hur man svarar, så är det ju så att $\mathbb{Z}_n$ består av de $n$ olika kongruensklasserna modulo $n$. I princip är alltså frågan vilka av dessa ändligt många kongruensklasser som löser ekvationen.
På uppgift 5a behöver förstås inget särskilt redovisas. Om ni inte har en tärning till hands kan jag tipsa om (1) google bildsök och (2) att tal som summerar till 7 står på motsatta sidor.
På uppgift 1 a, b, c, har jag tänkt mig mängder av reella tal. Alla de här mängderna är alltså intervall. En annan sak man kan tänka på är att en mängd av till exempel typen $\{x : x=17\}$ enklare kan skrivas $\{17\}$.
På uppgift 2 är det inte absolut ristat i sten vilket svar som är det rätta, men meningen är att ni ska fundera på hur detta kan fungera, vad det har att göra med binär representation av tal, samt hur Nisse gör rent praktiskt för att på en sekund räkna ut vilket tal kompisen tänkte på. Om ni inte förstår vad jag är ute efter, är ett tips att skriva upp den binära representationen av talen 1 till 31, eller förresten, 0 till 31, med 5 bitar. Alltså börja med 0 = 00000, 1 = 00001, 2 = 00010, 3 = 00011 osv, upp till 31 = 11111.
Sedan kan man fundera på hur detta har att göra med de tal som står på respektive lapp.
På uppgift 4, tänk på att man inte alltid bara kan dividera ekvationen med 2. När det gäller hur man svarar, så är det ju så att $\mathbb{Z}_n$ består av de $n$ olika kongruensklasserna modulo $n$. I princip är alltså frågan vilka av dessa ändligt många kongruensklasser som löser ekvationen.
På uppgift 5a behöver förstås inget särskilt redovisas. Om ni inte har en tärning till hands kan jag tipsa om (1) google bildsök och (2) att tal som summerar till 7 står på motsatta sidor.
Thursday, April 16, 2015
Om ordinarie tentan
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.
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.
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).
Subscribe to:
Posts (Atom)