MAN 010 : Algebra

Inlämningsuppgift 1

Uppgifterna utan en ∗ betraktas som ‘standard’, dvs av genomsnittlig svårighet. De med en ∗ är kanske något svårare. De inkluderas för dem som vill ha mer av en utmaning, men de är t.ex. långt över nivån som kommer att krävas på tentan. Man bör därför försöka lösa de enklare uppgifterna först. Naturligtvis är detta bara en subjektiv värdering.

1. Övning 4.15 i boken.

2. Övning 4.17 i boken.

3 (i) Bevisa med induktion (Obs! Använd inte teorin av kongruenser) att n^{5} − n ≡ 0 (mod 5) för alla naturliga tal n. (ii) Låt p vara ett primtal, k ett naturligt tal så att 0 < k < p. Bevisa att

den binomiala koeffiecienten ( \begin{matrix}p \\ k \end{matrix} ) är delbar med p.

*(iii) Låt p vara ett primtal. Använd (ii) för att bevisa MED INDUKTION att a^{p} − a ≡ 0 (mod p), för alla naturliga tal a (Fermats sats).

4. Bevisa att, för n > 1,

∑_{k=1}^{2^{n}−1} \frac{1}{k} < n.

5. Låt n ≥ 4. Ange och bevisa en formel för

∑_{k=4}^{n} \frac{1}{k^{2} − 5k + 6}.

6. Bevisa följande formel för Fibonacci talen :

F_{n} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n}] .

Obs! Nästa övning kräver partiell integration. Ni som inte ha sett detta förut får hoppa över övningen (om ni vill !).

7. För n ≥ 0, sätt

I_{n} := ∫ sec^{n} x dx, där sec x := \frac{1}{cos x}.

(i) Bevisa följande rekursion formel :

I_{n} = \frac{1}{n − 1} tan x sec^{n−2} x + \frac{n − 2}{n − 1}I_{n−2}, n ≥ 2.

(ii) Beräkna

∫_{0}^{π/4} sec^{4} x dx.

8 (i) Låt A vara en delmängd till {1, ..., 200} som består av 101 tal. Visa att A måste innehålla två tal vars SGD är lika med 1 (ett sådant par av tal sägs vara relativt prima).

Ledning : think spacings.

*(ii) Hur stor kan en delmängd A till {1, ..., 200} vara som inte innehåller något tripel av tal som är parvis relativt prima ?

9. Ett gäng av 8 killar går ut någon fredag kväll och träffar ett gäng av 6 tjejer. På hur många sätt kan de paras ihop så att ett par består av två olyckliga killar ?

10. På en restaurangsmeny finns det ett val av 6 förrätter, 8 huvudrätter och 5 efterrätter. Hur många olika middagar kan man beställa om

(i) man vill ha efterrätt, huvudrätt och efterrätt.

(ii) man vill ha huvudrätt och antingen förrätt eller efterrätt, men inte båda två. (iii) Kan man gå på denna restaurang varje dag under ett helt år och aldrig äta samma middag mer än en gång ?

11. Världens absolut bästa klubbfotbollslag, Liverpool FC (!!!), har en trupp bestående av 22 spelare : 3 målvakter, 6 försvarare, 9 mittfältare och 4 anfallare. Deras tränare föredrar spelsystemet 4-4-2, dvs målvakt + 4 försvarare + 4 mittfältare + 2 anfallare. Hur många olika laguppställningar har han då att välja ifrån, när alla spelarna är friska ?

12. Mer fotboll ! På VM i Frankrike 1998 deltog 32 länder, 15 från Europa, 5 från Sydamerika, 5 från Afrika, 4 från Asien och 3 från Nordamerika. Till gruppspelet skulle lagen lottas i 8 grupper med 4 lag i varje. Men lottningen var inte helt fri. Bland villkoren var att

(a) 8 lag var seedade, dvs inga två kunde hamna i samma grupp. Lagen var Argentina, Brasilien, England, Frankrike, Holland, Italien, Spanien och Tyskland.

(b) inte mer än 2 europeiska länder kunde hamna i samma grupp, och inte mer än ett land från varje annan världsdel.

(i) Om lottningen HADE varit helt fri, hur många olika lottningar kunde ha skett ? *(ii) Hur många olika lottningar kunde ha skett med ovanstående restriktioner ?

Obs! Bry dig inte om varken ordningen av grupperna eller ordningen av lagen i varje grupp.

13 (halvsvår). Denna övning är baserad på en sann historia (?!?) :

En viss namnlös investerare köpte i februari 1998 aktier i tre olika IT-företag, som för diskretions skull ska kallas för A,B och C. Prisen av de tre aktierna var då 220, 330 och 530 kr resp. och investeraren betalade 1897000 kr för sin portfölj. Juli 2001 hade de tre aktierna sjunkit till 110, 50, resp. 80 kr. Investeraren sålde sina aktier för 379000 kr, och hoppade snart därefter från en bro ! Samtidigt hade en data virus sett till att alla spår av hans finansiella transaktioner hade försvunnit, utom detaljerna ovan. Under polisutredningen dök alltså problemet upp att reda ut hur många aktier investeraren hade i de olika företagen. Från en hemlig källa fick de reda på att mannen hade mellan 1200 och 1500 aktier i företag C. Kan du nu hjälpa dem att lösa deras problem ?

14. Övning 3.8 (b), (d).

15. Ange en injektion f : R → R^{+} tillsammans med dess invers.

16. Ange bijektioner

(i) f : N → Z, (ii) f : [0, 2] → [2, 5], *(iii) f : N → Q, *(iv) f : R → R^{2}, *(v) f : [0, 1] → [0, 1).

17. Vilka av följande relationer (X, R) är (a) reflexiva (b) symmetriska (c) antisymmetriska (d) transitiva (e) partiella ordningar (f) ekvivalensrelationer ? I fall (X, R) är en partiell ordning, skissera dess graf. I fall den är en ekvivalensrelation, beskriv ekvivalensklasserna.

(i) X = N. Säg aRb om a och b har en gemensam delare större än 1. (ii) X = {alla räta linjer i planet}. Säg LRM om L är rättvinklig mot M. (iii) X = {alla delmängder till {1, 2, 3, 4}}. Säg aRb om a ⊆ b. (iv) X = {alla delmängder till {1, 2, 3, 4, 5, 6}}. Säg aRb om #(aΔb) är jämnt. *(v) X = N. Sär aRb om det finns rationella tal x, y så att

x^{2} + y^{2} = ab.

*18. Låt p vara ett primtal. Bevisa att

(p − 1)! ≡ −1 (mod p).

*19. Bevisa att

∑_{k=1}^{n} \frac{1}{k}

är inte ett heltal för alla n > 1.

20. I det irländska lotteriet (jag inte så välbekant med det svenska) väljer man 6 tal från 39. Man vinner pengar om man har åtminstone tre rätt.

(i) Hur många kort måste man köpa för att vara garanterat en jackpot (dvs, 6 rätt) ?

(ii, halvsvår) Om man köper bara ett kort, hur stor är chanserna att man vinner någonting ?

Anmärkning : Följande typ av problem är, i allmänhet, olöst faktiskt !!

‘Hur många kort måste man köpa för att vara garanterat någon form av vinst, och hur borde man fylla i korten i så fall ?’

*21. Bevisa att det finns oändligt många primtal p så att p ≡ 1 (mod 4).

(Ledning : Adaptera Euklides bevis att det finns oändligt många primtal).