Nr
Uppgift
Poäng
1
[Biggs 2.6.10] Visa att det i varje mängd med 172 heltal finns ett par vars skillnad är delbar med 171. Är detta sant även om skillnaden ersätts med summan.
3
Lösning: Av 172 tal måste det enligt duvslagsprincipen finnas minst två som har samma rest vid division med 171. Alltså kommer skillnaden mellan dessa att vara delbar med 171. Om vi istället för skillnad tar summa kommer detta argument inte längre fungera.
2
[Biggs 3.2.2] Antag att vi har ett antal delmängder av N8 med egenskapen att alla har fyra element och varje element i N8 tillhör precis tre av dem. Hur många delmängder är det? Skriv ned en uppsättning av sådana delmängder.
3
Lösning: Vi räknar par av element och delmängder där elementet ligger i delmängden, dvs {(a,S) | aÎS}. Eftersom varje delmängd innehåller fyra element kommer det att finnas 4k sådana par om det är k delmängder. Å andra sidan ligger varje element i tre delmängder, så det måste vara 3×8=24 sådana par. Alltså måste k=6. Vi kan tex välja delmängderna {1,2,5,6}, {1,3,5,7},{1,4,5,8},{2,3,6,7},{2,4,6,8},{3,4,7,8}. Att detta fungerar beror på att vi har tagit alla sex tvådelmängder av {1,2,3,4} och {5,6,7,8}. Varje tal ligger i precis tre sådana.
3
[Biggs 3.5.4] Låt (n)m =n(n-1)...(n-m+1). Visa att det för alla heltal n>r>m gäller att
(n)m(n-m)r-m=(n)r
genom att tolka det som ett resultat om ordnade val.
3
Lösning: Vi kan göra ett ordnat val utan återläggning av m element ur en mängd med n element på (n)m olika sätt. Om vi skall göra ett ordnat val utan återläggning av r element ur samma mängd kan vi först välja ut m element och sedan r-m element bland de återstående n-m elementen. Alltså måste
(n)r =(n)m(n-m)r-m.
4
[Biggs 3.6.5] Låt K den delmängd av S4 som innehåller identitetspermutationen och de tre permutationerna som består av två cykler av längd 2. Skriv upp multiplikationstabellen för K när multiplikationen tolkas som sammansättning av permutationer.
3
Lösning: De tre permutationerna som består av två cykler av längd 2 är (12)(34), (13)(24) och (14)(23). Om vi sammansätter den första av dem med den andra får vi (14)(23). Om vi skriver upp multiplikationstabellen för de fyra elementen i K får vi
*
id
(12)(34)
(13)(24)
(14)(23)
id
id
(12)(34)
(13)(24)
(14)(23)
(12)(34)
(12)(34)
id
(14)(23)
(13)(24)
(13)(24)
(13)(24)
(14)(23)
id
(12)(34)
(14)(23)
(14)(23)
(13)(24)
(12)(34)
id
5
[Biggs 3.7.9] Låt a och b vara permutationerna a=(1237)(49)(58)(6) och b=(135)(246)(789) i S4 skrivna i cykelnotation. Skriv ned cykelnotationen för permutationerna ab, ba, a2, b2, a-1 och b-1.
3
Lösning: För att bestämma sammansättningarna ab och ba måste vi sätta in den ena permutationen i den andra, ex ab(1)=a(b(1))=a(3)=7, ab(2)=a(b(2))=a(4)=9, ab(3)=a(b(3))=a(5)=8, ab(4)=a(b(4))=a(6)=6, ab(5)=a(b(5))=a(1)=2, ab(6)=a(b(6))=a(2)=3, ab(7)=a(b(7))=a(8)=5, ab(8)=a(b(8))=a(9)=4, ab(9)=a(b(9))=a(7)=1. Skriver vi detta på cykelnotation får vi ab=(17529)(3846). På liknande sätt får vi ba=(14738)(2596). För att hitta kvadrater och inverser kan vi behandla cyklerna var för sig. Alltså får vi a2=(13)(27)(4)(5)(6)(8)(9)=(13)(27), b2=(153)(264)(798), a-1 =(1732)(49)(58)(6) och b-1=(153)(264)(798).
6
[Biggs 3.7.17] Låt un vara antalet ord av längd n i alfabetet {0,1} som saknar konsekutiva nollor. Visa att
u1=2, u2=3 och un=un-1+ un-2 för n>2.
6
Lösning: Det är klart att det finns två ord av längd ett, eftersom både 0 och 1 är godkända ord. Av längd 2 finns det tre godkända ord eftersom 01, 10 och 11 är godkända, men inte 00.
När vi sedan går vidare kan vi se att ett ord av längd n antingen börjar på 1 och då kan det följa vilket godkänt ord som helst av längd n-1. Om ordet däremot börjar på 0 måste det följa en etta, varefter det kan följa ett godtyckligt godkänt ord av längd n-2. Eftersom dessa två fall utesluter varandra, har vi delat upp de gokända orden av längd n i två disjunkta delmmängder, en med un-1ord och en med un-2 ord. Enligt additionsprincipen är nu un=un-1+ un-2 för n>2.
7
I tärningsspelet Yatzy finns bland annat möjlighet att få tretal, fyrtal, yatzy, liten stege, stor stege och kåk.Vilka är sannolikheterna att få var och en av dessa i första kastet?
6
Lösning: I Yatzy har vi fem tärningar som skall kastas. För att se på sannolikheterna för olika möjligheter ser vi först på hur det går när vi kastar en tärning i taget. Det är ett ordnat val med återläggning och vi får 65=7776 olika fall som alla är lika sannolika – under förutsättning att tärningarna är justa.
När vi sedan skall se på de olika kombinationerna spelar det inte längre någon roll i vilken ordning tärningarna slagits.
Tretal: Om det är ett rent tretal, och inte kåk, fyrtal eller yatzy ingår tre olika tärningsresultat. Tretalet består av tre tärningar, och vi kan välja ut vilka tre det är på
sätt. Vi kan välja ut vilket värde tretalet har på 6 sätt och sedan de övriga två tärningarna på 5×4=20 sätt. Totalt får vi
och sannolikheten att få tretal i första kastet är 1200/7776.
Fyrtal: Här kan vi välja ut de fyra tärningarna på
sätt och värdena på tärningarna kan väljas på 6 sätt för fyrtalet och 5 sätt för den sista tärningen.
Alltså får vi totalt
olika sätt och sannolikheten att få fyrtal i första kastet är 150/7776.
Yatzy: Vi har 6 sätt att välja ut vad vi skall få yatzy i. Sannolikheten att få yatzy i första kastet är 6/7776=1/1296.
Liten stege, stor stege: För sannolikheten spelar det ingen roll vilken av stegarna vi skall få. Vi måste få precis de fem tärningsslagen som ingår i stegen, men ordningen kan vara hur som helst. Det finns därmed 5! olika sätt att få detta. Sannolikheten att få liten stege i första kastet är 5!/7776=1/1296.
Kåk: Precis som för tretal finns det
sätt
att välja ut vilka tärningar som bildar tretalet. Det
finns sedan 6 sätt att välja ut värdet på
tretalet och sedan 5 sätt att välja ut värdet på
paret. Totalt får vi
olika sätt och sannolikheten att få kåk i första kastet är 300/7776.
8
I kortspelet poker finns bland annat två par, triss, fyrtal, stege och kåk. Vilka är sannolikheterna att få var och en av dessa i given?
6
Lösning: Det är här fråga om val utan återläggning. Det finns 52 kort i kortleken och därmed
olika pokerhänder som alla borde vara lika sannolika.
Två par: För två par ser vi först att vi kan välja ut valörerna på paren på
sätt. Det sista kortet kan sedan väljas på 11× 4 sätt. Totalt får vi sannolikheten
Triss: För att se hur många av pokerhänderna som innehåller en triss ser vi först att vi kan välja ut valören på 13 sätt. Sedan finns det 4 sätt att välja ut vilka tre färger som skall ingå i trissen. Återstående kort kan väljas bland de övriga valörerna bara de är olika. Sedan finns det 4 val av färg för var och en av dessa två. Totalt får vi sannolikheten
Fyrtal: För fyrtal ser vi först att vi kan välja ut valören på fyrtalet på 13 sätt. Vi kan välja valören på det sista kortet på 12 sätt. Färgerna kan vi sedan välja på 1 respektive 4 sätt. Totalt får vi sannolikheten
Stege: En stege kan börja på 1,2,3,...,10. Det finns alltså 10 sätt att välja vilka valörer som skall ingå. Vidare finns det för varje valör 4 möjliga val av färg. Alltså får vi sannolikheten
