Hej gänget,
Bra jobbat igår och det var super att många av er var uppmärksamma på framförallt uppgift 1! Här kommer några lösningsförslag till gårdagens uppgifter :D
Uppgift \(1\):
- - - - - - - - - - -
Antag motsatsen. D.v.s. antag att det finns en ändlig uppsättning primtal \(p_{1} , ..., p_{n}\). Konstruera nu ett nytt tal
\(x = p_{1} \cdot ... \cdot p_{n} +1\).
Om \(x\) vore sammansatt skulle vi kunna primtalsfaktorisera det och således skulle detta tal behöva vara på formen
\(x = p_{1}^{m_{1}} \cdot p_{2}^{m_{2}} \cdot ... \cdot p_{n}^{m_{n}}\)
för några icke-negativa heltal \(m_{1} , ..., m_{n}\). Vi antog ju att \(p_{1} , ..., p_{n}\) var de enda primtalen som existerade och som konsekvens måste dessa var de enda primtalen som kan uppkomma i primtalsfaktoriseringen av varje heltal. Men enligt konstruktionen av \(x\) kommer ingen av \(p_{1} , ..., p_{n}\) dela \(x\) och vi drar därför slutsatsen att \(x\) inte kan vara sammansatt. Den enda möjligheten är därför att \(x\) är ett av de listade primtalen men detta är ju uppenbarligen också falskt. I båda fallen får vi en motsägelse och vi drar därför slutsatsen att det finns oändligt många primtal.
(Tillbaks till diskussionen vi hade under seminariet. En del av er var skeptiska till slutsatsen att \(x\) inte kan vara ett sammansatt tal. Ert argument var att \(x\) fortfarande kan vara ett sammansatt tal men att dess primtalsfaktorisering kommer utgöras av andra primtal som inte är någon av de listade. Detta är korrekt i allmänhet. Men här är det viktiga, under beviset så antar vi att \(p_{1} , ..., p_{n}\) är de enda primtalen och under detta antagande så är det korrekt att säga att \(x\) inte kan vara sammansatt. Logiken som används för motsägelsebevis kan ibland vara knepig så jag förstår om det fortfarande finns en viss förvirring. Hör gärna av er till mig om ni fortfarande är skeptiska eller förvirrade. Min mail är "emil.eriksson@math.su.se".)
Uppgift \(2\):
- - - - - - - - - - -
Vi noterar att vi egentligen bara behöver undersöka jämna och udda exponenter. Ty
\(7^{2k} \equiv_{4} 3^{2k} = (3^2)^k = 9^k \equiv_{4} 1^k = 1\)
och\(7^{2k+1} \equiv_{4} 3^{2k+1} = (3^2)^k \cdot 3^1 = 9^k \cdot 3 \equiv_{4} 1^k \cdot 3 = 1 \cdot 3 = 3.\)
Det finns \(11\) heltal på intervallet \(30 \leq x \leq 40\) och precis \(6\) av dessa är jämna och slutsatsen blir därför att
P(Emil blir sparkad) = P(Emil landar på bokstaven \(B\)) = \(\frac{6}{11}\).
Uppgift \(3\):
- - - - - - - - - - -
Fallet \(n=2\) är mer eller mindre trivial. Vi ställer den som vann först och den som förlorade sist.
Antag nu att påståendet är sant för alla \(2 \leq n \leq k\) , för något \(k \geq 2\). Betrakta nu fallet med \(k+1\) spelare. Arrangera först \(k\) av spelarna i en giltig sekvens (säg \(S_{1} , ..., S_{k}\)) vilket går att göra enligt induktionsantagandet. Det som kvarstår att visa är att vi kan placera den sista spelaren \(S_{k+1}\) någonstans i denna sekvens som gör att vi får en ny sekvens som fortfarande är giltig (med giltig menar jag att vilkoret i uppgiftslydelsen är uppfylld). Betrakta nu följande iterativa algoritm
För \(i = 1 , ..., k\) undersök följande:
(1) Om spelare \(S_{k+1}\) vann över spelare \(S_{i}\), placera \(S_{k+1}\) precis till vänster om \(S_{i}\)
och terminera.
(2) Om spelare \(S_{k+1}\) förlorade över spelare \(S_{i}\) och \(i < k\), gå vidare till nästa iteration
(d.v.s. iterationen där vi jämför \(S_{k+1}\) med \(S_{i+1}\)).
(3) Om spelare \(S_{k+1}\) förlorade över spelare \(S_{k}\), placera \(S_{k+1}\) precis till höger om
\(S_{k}\) och terminera. OBS! Detta motsvarar fallet då \(S_{k+1}\) förlorade mot alla spelare och därmed placeras längst ut till höger.
Observera nu att algoritmen är väldefinierad i den mening att den alltid terminerar. Om spelare \(S_{k+1}\) vann minst en match skulle ju någon iteration leda till fall (1). Om däremot spelare \(S_{k+1}\) förlorade alla sina matcher skulle vi hamna under fall (3). Efter att vi satt in spelare \(S_{k+1}\) kan vi också garantera oss att alla spelare till vänster om \(S_{k+1}\) är de spelarna som \(S_{k+1}\) förlorade mot och att spelaren precis till höger om \(S_{k+1}\) är en spelare som \(S_{k+1}\) vann emot. Med lite eftertanke så kan man övertyga sig om att denna nya sekvens är giltig.
Nästa seminarium tar Yishao hand om. Tveka inte att höra av er till oss ifall ni har frågor eller funderingar. Allt gott och ta hand om er!
Med vänliga hälsningar,
Emil Eriksson