📝

Lektion 10: Kombinatorik

📝Lektion 11: Antalet delare till heltal

📝Lektion 9: Mängder och venndiagram


Lektionsöversikt


Ordlista


10.1 Introduktion till kombinatorik

Kombinatorik är ett område inom matematiken som främst handlar om att räkna antal av något. Det kan vara att räkna ut antalet alternativ du har att välja mellan i ett visst scenario eller antalet sätt som ett visst utfall kan uppstå på. Ofta brukar detta inte vara något som helst problem; vi bara räknar en sak i taget tills att vi är klara. Vi kanske också använder oss av multiplikation eller division för att göra processen snabbare. Men ibland är det faktiskt inte så lätt att veta hur man ska gå tillväga. Ta det här problemet som exempel:

📝
Johannes och Joel ska köpa glass. De kommer båda att välja tre kulor från sex olika smaker, men de kommer inte att välja samma smak två gånger. Joel vill ha åtminstone en kula med samma smak som hans storebror Johannes. Hur många sätt kan de välja sina glassar på? Högstadiets Matematiktävling, kvalificering 2009/2010, problem 2

Vi kanske tänker oss att vi numrerar smakerna med siffrorna 161-6. Några möjliga glassar som Johannes då skulle kunna välja vore {1,2,3},{1,2,4},{1,2,5}\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\} och {1,2,6}\{1, 2, 6\}. Vi kanske fortsätter med {2,3,1},{2,3,4},{2,3,5}\{2, 3, 1\}, \{2, 3, 4\}, \{2, 3, 5\} och {2,3,6}\{2, 3, 6\}. Men nu ser vi att {1,2,3}\{1, 2, 3\} och {2,3,1}\{2, 3, 1\} i själva verket är samma glass, bara med smakerna i en annan ordning. Vi har alltså räknat den glassen två gånger. Även om vi till slut lyckas räkna ut alla möjliga glassar som Johannes kan välja måste vi sedan också ta reda på hur många kombinationer av glassar som bröderna tillsammans kan välja. Då måste vi också ta in i beräkningen att Joel måste ha minst en smak som är samma som de Johannes valde.

Att försöka räkna alla kombinationer en i taget blir väldigt komplicerat och tidskrävande. Förmodligen kan vi göra det hela snabbare genom att använda multiplikation och division, men då måste vi också vara försiktiga så att vi inte räknar samma glass flera gånger för att smakerna var i en annan ordning. I det här kapitlet kommer du att få lära dig metoderna som behövs för att enkelt lösa sådana här typer av problem.

10.2 Beräkning av kombinationer med multiplikation

Låt oss börja med hur vi beräknar antalet kombinationer som uppstår när vi ska göra olika flera val i följd. Ta följande problem som exempel:

📝
Mikael har fyra olika tröjor, tre olika par byxor och sex olika par skor. Hur många klädkombinationer kan han välja när han ska till skolan?

Mikael har fyra olika tröjor att välja mellan. För varje av dessa tröjor kan han välja mellan tre olika par byxor. Han har alltså 43=124\cdot3=12 olika kombinationer av tröjor och byxor att välja mellan. För varje av dessa 1212 kombinationer kan han nu välja mellan sex olika par skor. Mikael har alltså 436=724\cdot3\cdot6=\mathbf{72} olika klädkombinationer att välja mellan.

Förhoppningsvis ser du ett mönster här. Om du kan först kan välja mellan xx olika alternativ, och för varje av de alternativen har du ytterligare yy alternativ att välja mellan, så är det totala antalet möjliga kombinationer alltid produkten av xx och yy. Det är väldigt viktig att vi multiplicerar och inte adderar. Om vi hade adderat 4+3+64+3+6 hade vi fått antalet klädesplagg som Mikael har, istället för antalet sätt som de klädesplaggen kan kombineras på.


Övning 1

Miranda singlar fem stycken mynt. Hur många olika utfall kan hon få?


Övning 2

Hur många “ord” med tre bokstäver kan vi skapa genom att använda oss av bokstäverna a,b,c,d,ea, b, c, d, e och ff? (Vi ignorerar stavning, etc och vi kan använda samma bokstav flera gånger).


Övning 3

Hur många “ord” med tre bokstäver kan vi skapa genom att använda oss av bokstäverna a,b,c,d,ea, b, c, d, e och ff om första bokstaven måste vara en vokal och vi får inte använda samma bokstav två gånger?


Övning 4

Gustav är ute på stan en varm sommardag och blir plötsligt sugen på glass. Han går in på närmaste glasställe där de har tio olika smaker att välja mellan. Man kan få glassen serverad antingen i bägare eller i strut, och man man är sötsugen kan man också få sin glass toppad med strössel, kolasås eller chokladsås. Gustav vill bara en kula till sin glass. Hur många olika glassar kan han köpa?


10.3 Arrangera föremål

Säg att vi har fyra olika föremål på en rad: en kvadrat, en triangel, en cirkel och en pentagon. Hur många olika arrangemang kan du skapa genom att flytta om föremålen? Ett exempel på ett sätt att arrangera de fyra föremålen på är följande:

Inom matematiken brukar vi kalla sådana arrangeringar av föremål för permutationer. Till exempel är (1,2,3)(1, 2, 3) en permutation av (3,1,2)(3, 1, 2) och vice versa. Ett enkelt sätt för att beräkna antalet permutationer av de fyra föremålen ovan är att föreställa sig att vi har fyra tomma platser som vi ska placera föremålen på.

Vi börjar med kvadraten, därefter triangeln, cirkeln och sist pentagonen. Vi har 44 tomma platser att välja mellan för kvadraten. När vi sedan ska placera ut triangeln har vi bara 33 tomma platser att välja mellan, eftersom att kvadraten kommer att ta upp en av platserna. Går vi sedan vidare till cirkeln har vi denna gång bara 22 platser att välja mellan. Sist men inte minst har vi 11 plats kvar för pentagonen. Det totala antalet sätt att arrangera de fyra föremålen är alltså 4321=244\cdot3\cdot2\cdot1=\mathbf{24}.

Det här mönstret gäller för vilket antal unika föremål du än väljer. Har du exempelvis 55 unika föremål kan du arrangera dem på 54321=1205\cdot4\cdot3\cdot2\cdot1=120 olika sätt. Har du däremot 1111 unika föremål finns det 111021=39 916 80011\cdot10 … 2\cdot1 = 39 \ 916 \ 800 olika ordningar att placera dem på, och så vidare.

Som du nog har märkt kan det ibland vara jobbigt att hela tiden skriva långa produkter som 11102111\cdot10 … 2\cdot1. Det finns dock ett kortare sätt att göra detta på, nämligen att sätta ett utropstecken efter det första talet. Vi skriver alltså 11!11! istället för att faktiskt skriva hela sekvensen. Detta uttalas “elva fakultet”.


Övning 5

Hur många gånger större är 101!101! än 99!99!?


Övning 6

Tomas har två hyllor på väggen i sitt vardagsrum. På den ena hyllan står det tre olika krukväxter och på den andra står det fem olika glasprydnader. Alla föremål är uppställda på rad. På hur många olika sätt kan han flytta om föremålen på de två hyllorna så att krukväxterna och glasprydnaderna står kvar på samma hylla?


När alla föremål inte är unika

Spelar det någon roll om föremålen vi arrangerar är unika eller inte? Kommer antalet ordningar att förändras om två föremål ser exakt likadana ut eller är resultatet fortfarande detsamma? Ta dessa fyra föremål som exempel. Hur många sätt kan vi arrangera dem på?

Teoretiskt sätt kan vi såklart flytta om de fyra trianglarna på 4!=244! = 24 olika sätt, men problemet är att alla dessa utfall kommer att se exakt likadana ut. Vi har 2424 kopior av samma permutation. Detta är uppenbarligen inte särskilt praktiskt och av den anledningen brukar vi endast intressera oss för unika permutationer.

Ta dessa fem föremål som exempel:

Eftersom att vi har fem föremål kan vi arrangera dem på 120120 olika sätt, men flera av dessa permutationer kommer att vara kopior av varandra. Vårt uppdrag är alltså att ta reda på hur många kopior det finns för varje unik permutation. Vi kan undersöka detta om vi ger varje kvadrat var sitt nummer.

Så länge vi bara byter plats på kvadraterna kommer den unika kombinationen inte att förändras. Frågan är alltså hur många sätt vi kan arrangera de 33 kvadraterna på? Svaret är 3!=63! = 6. Kvadrat 11 kan placeras 33 möjliga platser. Vi har sedan 22 platser kvar åt kvadrat 22 att välja mellan och sedan finns det bara 11 plats kvar åt kvadrat 33 på slutet. Här nedan kan du se alla möjliga kopior av denna kombination.

Detta innebär att det finns 3!=63! = 6 kopior av varje unik permutation. Antalet unika permutationer av de 55 föremålen måste alltså vara 5!3!=20\frac{5!}{3!}=\mathbf{20}.

Detta mönster gäller för alla tal. Om du exempelvis har 77 föremål som består av en kvadrat, en triangel, en pentagon och fyra identiska cirklar kommer du att kunna skapa 7!4!=210\frac{7!}{4!}=\mathbf{210} unika kombinationer. Föremålen kan arrangeras på 7!=50407! = 5040 sätt, men det kommer att bildas 4!=244! = 24 kopior av varje unik permutation. För att ta bort dessa kopior behöver vi dela 7!7! med 4!4! vilket ger oss 210\mathbf{210}.


Övning 7

Lisa har två identiska cirklar och fyra identiska kvadrater. Hur många unika kombinationer kan hon få genom att arrangera föremålen?


10.4 Att välja ett par föremål bland många olika

Säg att vi har nio olika föremål och vi vill välja tre av dem. Hur många unika mängder av föremål kan vi välja? (Bara för att förtydliga, för att två mängd ska vara unika måste de bestå av olika kombinationer av föremål. Vi bryr oss inte om i vilken ordning de valdes i).

Vi har 99 alternativ för vårt först val, 88 alternativ för vårt andra val och sist 77 alternativ för vårt tredje val. Det finns alltså 987=5049\cdot8\cdot7 = 504 sätt att välja våra tre föremål på. Men kommer alla dessa 504504 val att leda till unika mängd?

Vår uträkning 987=5049\cdot8\cdot7 = 504 omfattar varenda möjlig kombination som vi kan välja de tre föremålen på. En av dessa 504504 valmöjligheter kommer vara att vi först valde föremål AA, sedan föremål BB och sist CC. En annan valmöjlighet kommer vara att vi först valde CC, sedan AA och sist BB. Som du kan se har vi ett problem här. {A,B,C}\{A,B,C\} och {C,A,B}\{C,A,B\} är inte två unika mängder. De är två olika permutationer av samma mängd.

Vi kan lösa det här problemet på samma sätt som vi gjorde förut. Om vi har tre föremål kommer de att kunna arrangeras på 3!=63! = 6 olika sätt. Det kommer alltså finnas sex kopior av varje unik mängd, så antalet unika mängd vi kan välja är alltså 9 8 73!=84\frac{9\ \cdot8\ \cdot7}{3!}=\mathbf{84}.

Det här mönstret gäller endast så länge alla föremål är unika. Har vi 2222 unika föremål och vill välja fem av dem kan du göra detta på 22 21 20 19 185!=22 334\frac{22\ \cdot21\ \cdot20\ \cdot19\ \cdot18}{5!}=22\ 334 sätt. Om två eller flera av föremålen däremot hade varit identiska kommer den här metoden inte att fungera. Vi kommer att gå in på varför det är så och hur vi hanterar ett sådant problem i nästa del av det här kapitlet.


Övning 8

Casper får en mängd med nn olika föremål och han ska välja mm av dessa. Hur många unika mängder med mm föremål kan Casper välja?


Övning 9

Tio grannar träffas för att äta middag och alla hälsar genom att skaka hand en gång med alla inbjudna. Hur många handskakningar blir det totalt?


10.5 Sammanfattning

Vi kommer nu använda det vi har lärt oss i det här kapitlet för att lösa problemet som vi introducerade i början av det här kapitlet:

📝
Johannes och Joel ska köpa glass. De kommer båda att välja tre kulor från sex olika smaker, men de kommer inte att välja samma smak två gånger. Joel vill ha åtminstone en kula med samma smak som hans storebror Johannes. Hur många sätt kan de välja sina glassar på? Högstadiets Matematiktävling, kvalificering 2009/2010, problem 2

Joel kommer att välja sina smaker beroende på hur Johannes väljer, så det är lättast beräkna antalet valmöjligheter som Johannes har först. Johannes kan välja sina tre kulor på 6546\cdot5\cdot4 olika sätt, men eftersom att ordningen inte spelar någon roll måste vi också dela med 3!3!. Det finns alltså 2020 möjliga glassar som Johannes kan välja.

Joel ska nu välja sin glass på ett sätt så att åtminstone en kula är densamma som de som Johannes valde. Vilken glass Johannes än bestämde sig för finns det exakt en glass som Joel inte kan välja; nämligen att han tar de tre andra smakerna som Johannes inte valde. Om Johannes exempelvis valde smakerna {1,2,3{1,2,3}} kan Joel välja allt utom just {4,5,6{4,5,6}}. Joel har alltså 201=1920 - 1 = 19 möjliga glassar att välja mellan. Bröderna kan alltså välja sina glassar på 2019=38020\cdot19 = \mathbf{380} sätt.

10.6 Olika fall

Säg att vi vill välja tre föremål från mängden här nedan. Hur många unika mängder kan vi välja?

Det här problemet går inte att lösa genom att dela 6!6! med 3!3!. Den metoden bygger som sagt på att varje mängd vi väljer kan arrangeras på exakt 3!3! olika sätt och därmed kommer ge upphov till 66 kopior av varje unikt mängd. Tänk dig att vi väljer ett mängd som består av cirkeln samt de två identiska kvadraterna. Hur många kopior kommer det att finnas av den mängden? Det kommer inte att vara 3!=63! = 6, eftersom att det inte är någon skillnad ifall vi bytte plats på kvadraterna. Vi har i själva verket bara 3!2!=3\frac{3!}{2!}= 3 kopior av det mängder. Vår metod fungerar alltså bara för vissa mängder, men inte för alla. Det enklaste sättet att lösa en sådan här uppgift är därför att dela upp det i olika fall.

(1) Alla föremål vi väljer är unika

I det här fallet får vi inte välja båda kvadraterna. Vi kan alltså bara välja mellan fem av de sex föremålen. Detta ger oss 543=605\cdot4\cdot3 = 60 olika valmöjligheter, och eftersom att alla föremål är unika måste vi dela med 3!3!. Detta fall ger oss alltså 1010 unika mängder.

(2) Alla föremål vi väljer är inte unika

I det här fallet är vi tvungna att välja båda kvadraterna. Vi har sedan fyra alternativ att välja mellan för det sista föremålet; antingen cirkeln, pentagonen, triangeln eller korset. Det här fallet ger oss alltså 44 unika mängder.

Sammanlagt kan vi alltså välja 10+4=1410 + 4 = \mathbf{14} unika mängd av tre föremål.

Ibland är det svårt att göra en enda uträkning som kommer att lösa uppgiften omedelbart. Det här händer oftast när uppgiften kan delas in i kategorier som alla kräver helt olika tillvägagångssätt. Exempelvis var svaret det till första fallet 1010 för att vi behövde välja 33 föremål från ett mängd av 55 unika föremål 5! 4 33!\frac{5!\ \cdot4\ \cdot3}{3!}. Svaret till det andra fallet var däremot 44 för att vi behövde välja 11 föremål från ett mängd av 44 unika föremål 4!1!\frac{4!}{1!}. Det finns ingen som helst koppling mellan dessa två scenarier. Därför är det mycket lättare att dela upp dem i olika fall, beräkna dem separat och sedan addera resultaten.

Hur vet vi när vi behöver dela upp ett problem i olika fall och när vi inte behöver göra det? Vi kan använda oss enbart av ren multiplikation om antalet valmöjligheter inte varierar beroende på vilka val vi gör. Om jag exempelvis har tre jackor och fyra mössor att välja mellan när jag ska gå utomhus kan jag välja min klädsel på 34=123\cdot4 = 12 olika sätt. Antalet mössor jag kan välja förändras inte om beroende på vilken jacka jag väljer. Därför kan jag bara multiplicera antalet jackor och mössor med varandra för att räkna ut hur många val av klädsel jag har. Om jag däremot inte vill ha min blåa mössa tillsammans med min bruna eller min svarta jacka måste jag dela upp problemet i två olika fall. (Vi antar att alla klädesplagg har olika färg).

(1) Jackan jag väljer är brun eller svart

Detta ger mig två valmöjligheter när jag ska välja jacka. Eftersom att jag nu inte får välja den blåa mössan har jag endast tre mössor kvar att välja mellan. Jag har därmed 23=62\cdot3 = 6 möjliga val av klädsel i detta fall.

(2) Jackan jag väljer är inte brun eller svart

Detta ger mig endast ett alternativ när jag ska välja jacka men jag kan nu välja vilken av de fyra mössorna jag vill. Jag har därmed 14=41\cdot4 = 4 möjliga val av klädsel i detta fall.

Jag kan alltså välja min klädsel på 6+4=106 + 4 = \mathbf{10} olika sätt.

OBS! När du delar upp en uppgift i olika fall är det väldigt viktigt att dina fall verkligen täcker in alla möjliga alternativ och att det heller inte finns något överlapp mellan fallen. Täcker dina fall inte in alla möjliga alternativ får du ett för litet svar och om du istället har ett överlapp kommer du beräkna vissa alternativ mer än en gång och få ett för stort svar.


Övning 10

Hur många positiva heltal mellan 100100 och 300300 innehåller exakt två likadana siffror? (Vi inkluderar både 100100 och 300300 i vår räkning).


Övning 11

Barnen Simon, Wilhelmina och Rasmus har sammanlagt tre enkronor. På hur många sätt kan de dela upp mynten mellan varandra?


Övning 12

Simon, Wilhelminas och Rasmus lärare kommer nu förbi och ger de tre barnen en till enkrona. Hur många sätt kan de nu dela upp enkronorna mellan sig?


10.7 Överräkning

Något som vi behöver vara försiktiga med i kombinatorik är att se till att vi inte räknar samma objekt flera gånger. Ta det här problemet som exempel:

📝
Vad är det största heltalet nn så att 2n2n delar 20!20!?

Vi kan strukturera upp talen i produkten 20!20! i fyra olika grupper:

Låt oss börja med talen i den första gruppen. Varje tal i den här gruppen ger oss en 2:a var så vi får totalt tio stycken 2:or. Vi går nu vidare till den andra gruppen. Varje tal här är delbart med 44 så de ger oss två stycken 2:or var. Här måste vi dock vara försiktiga! Alla tal i den andra gruppen var också med i den första gruppen, så vi har redan räknat en av dessa talens 2:or när vi räknade igenom den första gruppen. Även om varje tal i den andra gruppen innehåller två stycken 2:or ska vi bara räkna det som att talen bidrar med en ny 2:a var. Den andra gruppen ger oss alltså 55 nya 2:or. Med samma resonemang kommer vi fram till att varje tal i den tredje gruppen också bara bidrar med en ny 2:a vardera då två av deras tre 2:or redan har blivit räknade när vi gick igenom den första och andra gruppen. Den tredje gruppen ger oss därmed två stycken nya 2:or. Slutligen ger oss den fjärde gruppen ytterligare en ny 2:a. Sammanlagt innehåller produkten 10+5+2+1=1810 + 5 + 2 + 1 = 18 stycken 2:or. Det största heltalet nn så att 2n2n delar 20!20! är därmed 8\mathbf{8}. När vi har grupper som överlappar, så att ett objekt kan finnas i flera grupper samtidigt, behöver vi vara särskilt noggranna med att inte räkna samma objekt flera gånger.

Räkna rätt genom att räkna fel

I många situationer är den snabbaste metoden för att räkna något är att räkna det som vi inte är intresserade av och sedan subtrahera det från det totala antalet. Det vi får över är då antalet av det vi faktiskt var intresserade av att räkna.


Exempel 1

Josefine skriver upp alla positiva heltal från 11 till 200200 på klassrummets tavla. Hur många tal på tavlan innehåller siffran sju?

Lösning

Det här problemet kan lösas genom att räkna ut det totala antalet sjuor på tavlan och sedan subtrahera det med antalet tal som innehåller två sjuor. Ett tal kan innehålla siffran sju som ett ental eller som ett tiotal. Var tionde tal har en sjua på sin entalsplats så det finns 200/10=20200 / 10 = 20 entals-sjuor. För varje 100100 tal finns det också 1010 tal med en sjua på sin tiotalsplats så det finns och 210=20210 = 20 tiotals-sjuor under 200200. Sammanlagt finns det 20+20=4020 + 20 = 40 sjuor på tavlan. Det finns två tal på tavlan som innehåller två sjuor (7777 och 177177). Antalet tal på tavlan som innehåller siffran sju är alltså 402=3840 - 2 = \mathbf{38}.

Att räkna det totala antalet och sedan subtrahera det vi inte är intresserade av är särskilt användbart när problemet kan delas upp i väldigt många olika fall. Detta gäller ofta för problem där vi ska räkna ut antalet sätt vi ska räkna ut antalet kombinationer problemet kan delas upp i väldigt många olika fall.


Exempel 2

Ulf har en korg med nio olika frukter. Två av dessa frukter är gula, tre är gröna och fyra är röda. På hur många sätt kan Ulf välja fyra frukter så att åtminstone en frukt är röd?

Lösning

Det här problemet kan delas in i fem olika fall

(1) 00 av de fyra frukterna är röda

(2) 11 av de fyra frukterna är röd

(3) 22 av de fyra frukterna är röda

(4) 33 av de fyra frukterna är röda

(5) 44 av de fyra frukterna är röda

Vi vill beräkna summan av fall (2), (3), (4) och (5). Vi kan göra detta på två olika sätt. Antingen beräknar vi alla dessa fall separat och sedan summerar dem, eller så beräknar vi fall (1), att ingen av frukterna är röd, och subtraherar det från det totala antalet fall. Lägg märke till att det inte finns någon situation som inte kan sorteras in i något av våra fem fall, så summan av de fem fallen måste vara det totala antalet sätt som Ulf kan välja fyra frukter på.

Ulf kan välja fyra frukter från sin korg på totalt 9876/4!=1269\cdot8\cdot7\cdot6 / 4! = 126 olika sätt. Om ingen frukt får vara röd har han fyra frukter kvar att välja mellan. Detta kan ske på 5432/4!=55\cdot4\cdot3\cdot2 / 4! = 5 olika sätt. Ulf kan alltså välja fyra frukter så att minst en av dem är röd på 1265=121126 - 5 = \mathbf{121} sätt.

När än ett problem kan delas upp i flera olika fall är det ofta en bra idé att lista alla möjliga fall och sedan bedöma vilken strategi som kommer kräva minst arbete. Ibland är det enklare att bara räkna de fall vi är intresserade av och ibland är det enklare att göra tvärtom. En ledtråd är att hålla utkik efter orden “minst”, “åtminstone” eller “som mest” i uppgiften. Om något av dessa uttryck finns med är det oftast enklast att välja den andra metoden där vi räknar antalet fall vi inte är intresserade av och subtraherar det från det hela.


Övning 13

Hur många fyrsiffriga tal innehåller minst en jämn siffra?


Övning 14

Bildläraren Josef har en förpackning med pennor i färgerna blått, rosa, rött, grönt och brunt. På hur många olika sätt kan han:

a) ge tre elever en penna vardera?

b) ge tre elever en penna vardera så att ingen elev har samma färg?

c) ge tre gröna pennor till tio elever så att ingen elev har mer än en penna?

d) ge tre olikfärgade pennor till tio elever så att ingen elev har mer än en penna?

e) ge tre rosa pennor till tre elever?

f) ge tre pennor till tre elever så att inte mer än två pennor är röda eller bruna?


10.8 En vanlig fälla

Än så länge har vi endast diskuterat olika sätt att arrangera föremål när de är placerade på en rad. Ibland kommer vi dock stöta på problem där de istället är arrangerade i en ring. Detta är en stor skillnad eftersom att en ring kan roteras utan att det leder till en ny permutation. Om fem personer i en ring alla hoppar ett steg åt höger är ordningen fortfarande densamma. Om fem personer istället hade varit placerade på i en rad hade varje hopp åt höger (den femte personen placeras då längst fram i raden) däremot bildat en ny permutation. Eftersom att en ring med n unika föremål kan roteras n gånger utan att ordningen förändras finns det sammanlagt n!n=(n1)!\frac{n!}{n} = (n - 1)! unika sätt som de föremålen kan arrangeras på.

Hur gör vi med föremål som nyckelringar där vi har tre dimensioner att förhålla oss till? Till skillnad från en cirkel kan en nyckelring inte bara roteras utan också vändas upp och ner. Antalet unika permutationer blir därmed ännu färre. I dessa fall måste vi dela med en ytterligare faktor av 22 eftersom att varje permutation är densamma som dess upp-och-ner vända motsvarighet. Om n föremål är placerade på en nyckelring kan de alltså arrangeras på (n1)!/2(n - 1)! / 2 olika sätt.

Exempelvis finns det bara en permutation av en nyckelring med tre nycklar på sig.


Övning 15

På hur många sätt kan fem olika föremål arrangeras om de är:

a) På en rad?

b) I en cirkel?

c) På en nyckelring?


Problem att lösa för Lektion 10

1. På ett kakfat finns åtta sorters kakor. På hur många olika sätt kan du välja tre kakor om du bara får ta en kaka av varje sort?

Pythagoras Quest, riksfinal 2009, del 2 problem 2

2. De 66 eleverna i elevrådet vill sammankalla alla skolans elever till ett möte i aulan. Var och en av elevrådsmedlemmarna ringer 66 elever, som i sin tur ringer 66 elever var och dessa ringer till slut 44 elever var. Hur många elever känner till mötet om ingen av eleverna har fått mer än ett samtal?

Pythagoras Quest, distriksfinal 2013, del 1 problem 1

3. Vad är slutsiffran av summan 1!+2!+3!+14!+15!1! + 2! + 3! + … 14! + 15! ?

(MATHCOUNTS 1991)

4. Ett bra ord består endast av bokstäverna P, Y, T, H och Q. Dessutom får inte P följas direkt av Y, Y får inte följas direkt av T, T får inte direkt följas av H, H får inte följas direkt av Q och Q får inte följas direkt av P. Hur många bra ord av längden fem finns det?

(OBS! Varje bokstav kan förekomma mer än en gång per ord t.ex. PPPPP)

Pythagoras Quest, distriksfinal 2016, del 2 problem 7

5. En yoghurtbutik har fyra olika smaker och sex olika toppings. Om en kund vill ha en smak och två olika toppings, hur många olika kombinationer kan hon välja?

MATHCOUNTS 1990

6. På hur många sätt kan fem böcker arrangeras på en hylla om två böcker måste vara bredvid varandra?

MATHCOUNTS 1984

7. Claudia har 1212 mynt. Varje mynt är antingen en femma eller en tia. Genom att kombinera dessa kan hon få exakt 1717 olika summor (summa 0\neq 0). Hur många tior har Claudia?

Pythagoras Quest, distriksfinal 2015, del 11 problem 2

8. Hur många femsiffriga tal innehåller minst två udda siffror?

9. För att numrera sidorna i en bok användes 201201 siffror. Hur många numrerade sidor hade boken?

Pythagoras Quest, riksfinal 2013, del 1 problem 1

10. Zlatans mormor har tre barnbarn som alla ringer henne med jämna mellanrum. Barnbarn nummer 11 ringer henne varannan dag, barnbarn nummer 22 ringer henne var tredje dag och barnbarn nummer 3 ringer henne var femte dag. Alla tre barn ringde henne den 11 januari 20172017. Hur många dagar under 20172017 fick hon inga samtal (totalt det fanns 365365 dagar under 20172017)?

Pythagoras Quest, distriktsfinal 2018, del 1 problem 2

11. Sex tågvagnar, antag P, Y, T, H, Q och U, ska sättas ihop på ett sådant sätt att P måste vara

framför Y. På hur många sätt är detta möjligt?

Pythagoras Quest, riksfinal 2017, del 2 problem 3

12. Christian ska byta ut sitt bankkorts fyrsiffriga PIN-kod. Han har tidigare haft koden 2 0 1 7. Vad finns det flest av: koder som har minst en av dessa siffror, eller koder som inte har det?

Pythagoras Quest, riksfinal 2017, del 1 problem 3

13. Färre än 5050 personer är bjudna på en fest. Varje person skakar hand med alla de andra gästerna. Vad är det största antal gäster som kan vara på festen om det totala antalet handskakningar är udda?

Mandelbrot #1

14. Fyra par (en kvinna och en man i varje par) skall äta middag vid ett runt bord. De får inte sitta bredvid en person av samma kön och inte heller bredvid sin partner. Betecknar gästerna med A,a,B,b,C,c,D,dA, a, B, b, C, c, D, d där versalen (den stora bokstaven) står för kvinnan. På hur många olika sätt kan de placera sig? Två placeringar är samma om alla personer har samma två bordsgrannar.

Pythagoras Quest, riksfinal 2014, del 1 problem 1

15. I Geometrilandet har alla barn leksaker som uppfyller följande:

  • De har en av tre former (kub, klot eller tetraeder).
  • De består av ett av fyra material (plast, trä, gummi eller porslin)
  • De har en av fem storlekar (XL, L, M, S eller XS)
  • De har en av sex färger (vit, svart, gul, grön, röd eller blå.
  • Alla möjliga kombinationer finns representerade och alla barn har exakt en leksak av varje sort.

a) Hur många olika leksaker har varje barn?

b) Hur många leksaker är olik en svart XL plastkub på minst två sätt?

Pythagoras Quest, riksfinal 2014, del 1 problem 5

Lösningar

1. Vi kan välja tre kakor från ett urval av åtta på 8  7  63!=56\frac{8\ \cdot \ 7 \ \cdot \ 6}{3!} = \mathbf{56} olika sätt.

2. Låt oss dela in eleverna i olika grupper beroende på i vilket steg de blev informerade om mötet. I den första gruppen har vi de 66 elevrådsmedlemmarna. De ringer sedan 66 elever var så den andra gruppen består av 66=366\cdot6 = 36 elever. Eleverna i den andra gruppen ringer i sin tur 66 elever var så den andra gruppen består av 366=21636\cdot6 = 216 elever. Slutligen kommer den fjärde gruppen bestå av 2164=864216\cdot4 = 864 elever. Antalet elever som känner till mötet är därmed summan av alla fyra grupper vilket blir sammanlagt 6+36+216+864=11226 + 36 + 216 + 864 = \mathbf{1122} elever.

3. Ett tal slutar alltid på siffran 00 om det är delbart med 1010, det vill säga om dess primtalsfaktorisering innehåller minst en 2:a och en 5:a. Alla tal n!n! där n=5n = 5 kommer innehålla minst en 2:a och en 5:a så de kommer alltid att sluta på 00. Slutsiffran av summan 1!+2!+3!+14!+15!1! + 2! + 3! + … 14! + 15! är därmed densamma som slutsiffran av 1!+2!+3!+4!1! + 2! + 3! + 4!. Dessa fyra termer har slutsiffrorna 1,2,61, 2, 6 respektive 44 så slutsiffran av deras summa är 3\mathbf{3}.

4. Vi har fem alternativ att välja mellan för den första bokstaven. Den andra bokstaven kan dock bara väljas på fyra sätt då det alltid finns en bokstav som inte får följas direkt av en annan. Av samma skäl har vi också fyra alternativ att välja mellan till den tredje, fjärde och den femte bokstaven. Allt som allt finns det 54444=12805\cdot4\cdot4\cdot4\cdot4 = \mathbf{1280} bra ord.

5. Kunden kan välja smaken på fyra olika sätt och sina toppings på 6  52!=15\frac{6 \ \cdot \ 5}{2!} = 15 olika sätt. Det går alltså att välja 415=604\cdot15 = \mathbf{60} olika kombinationer.

6. Vi kan välja att placera de två böckerna som måste vara bredvid varandra på fyra olika sätt: plats 11 och 2,22, 2 och 3,33, 3 och 44 eller 44 och 55. Vi kan också välja att antingen byta plats på dessa två böcker eller att låta dem vara som de var från början. De tre sista böckerna kan vi sedan byta välja att byta plats på 3!=63! = 6 olika sätt. Sammanlagt kan vi arrangera böckerna på 426=484\cdot2\cdot6 = \mathbf{48} olika sätt.

7.

Lösning 1

Eftersom antalet mynt är jämnt måste Claudia ha ett udda antal femkronor för att kunna få 77 olika summor. Hon kan då kombinera dessa mynt till exakt 1212 kombinationer. För varje femkrona vi byter ut mot en tiokrona kommer summan av mynten att öka med 55. Detta kommer göra det möjligt för henne att uppnå en ny summa utan att hon går miste om någon summa som hon tidigare kunde skapa. Hon kommer därmed kunna skapa exakt 1717 summor om hon byter ut fem femkronor mot tiokronor. Claudia har således 5\mathbf{5} tiokronor.

Lösning 2

Claudia måste ha minst en femkrona då endast tiokronor kan ge henne max 1212 olika summor. Eftersom att hon har minst en femkrona är det möjligt för henne att uppnå varje summa som är en multipel av 55, det vill säga 5,10,15,205, 10, 15, 20 … etc, ända tills att hon når sin maxgräns. För att hon ska kunna uppnå exakt 1717 olika summor måste det största tal hon kan skapa vara 175=8517\cdot5 = 85. Låt oss säga att Claudia har xx femkronor och yy tiokronor. Det följer då att:

x+y=125x+10y=85x + y = 12 \\ 5x + 10y = 85

vilket har lösningen (x,y)=(7,5)(x, y) = (7, 5). Claudia har således 5\mathbf{5} tiokronor.

8. Den här uppgiften kan delas in i följande fall:

(1) Tal med 0\mathbf{0} udda siffror

(2) Tal med 1\mathbf{1} udda siffra

(3) Tal med 2\mathbf{2} udda siffror

(4) Tal med 3\mathbf{3} udda siffror

(5) Tal med 4\mathbf{4} udda siffror

(6) Tal med 5\mathbf{5} udda siffror

Eftersom vi vill beräkna antalet tal med minst två udda siffror vill hitta summan av fall (3), (4), (5) och (6). Detta gör vi enklast genom att beräkna fall (1) och (2) och subtrahera det från det totala antalet femsiffriga tal. Det finns 45555=25004\cdot5\cdot5\cdot5\cdot5 = 2500 femsiffriga tal med inga udda siffror. (Den första siffran får inte vara 00 så vi har endast fyra jämna siffror att välja mellan för talets först siffra istället för fem). Vi går nu vidare till att beräkna antalet femsiffriga tal med exakt en udda siffra. Det här kan i sin tur delas upp i följande två fall:

(2.1) Den första siffran är udda

Vi kan välja den udda siffran på fem olika sätt. De fyra resterande jämna siffrorna kan också väljas på fem sätt vardera. Det här fallet ger oss därmed 55555=55=31255\cdot5\cdot5\cdot5\cdot5 = 5^5 = 3125 möjliga tal.

(2.2) Den första siffran är inte udda

Vi har fyra valmöjligheter för den första siffran. Vi har fem siffror att välja mellan till den udda siffran och den udda siffran kan också placeras på fyra olika ställen. De resterande tre jämna talen kan väljas på fem sätt vardera. Det här fallet ger oss därmed 4(54)555=100004\cdot(5\cdot4)\cdot5\cdot5\cdot5 = 10 000 möjliga tal.

Det finns alltså 3125+10000=131253125 + 10 000 = 13 125 femsiffriga tal med som exakt en udda siffra. Det totala antalet femsiffriga tal är 910101010=9104=900009\cdot10\cdot10\cdot10\cdot10 = 9\cdot10^4 = 90 000. Sammanlagt finns det 90000250013125=7437590 000 - 2500 - 13 125 = \mathbf{74 375} femsiffriga tal som innehåller minst två udda siffror.

Anledningen till att vi behöver dela upp fall (2) i ytterligare två sub-fall är för att den första siffran i talet inte kan vara 00. Om den första siffran är jämn finns det därför endast fyra valmöjligheter jämfört med fem valmöjligheter om siffran vore udda.

9. De första 99 sidorna i boken kräver bara en siffra vardera. De nästa 9090 sidorna (10,1198,99)(10, 11 \ldots 98, 99) kräver två siffror vardera. När vi har numrerat de första 9999 sidorna har 20190291=12201-90\cdot2-9\cdot1=12 siffror kvar. Varje ny sida kräver nu tre siffror så vi kan numrera 123=4\frac{12}{3} = 4 sidor till. Boken har därmed 9+90+4=1039+90+4=\mathbf{103} sidor.

10. Vi kan räkna ut antalet dagar Zlatans mormor inte fick några samtal genom att räkna hur många dagar då hon fick samtal och subtrahera det från 365365. Antalet dagar hon fick samtal är lika med det totala antalet samtal hon fått bortsett från de samtal som kom under samma dag.

Barnbarn nummer 11 ringde mormon under dagarna 1,3,53651, 3, 5… 365 vilket blev totalt 365  12+1=183\frac{365 \ - \ 1}{2} + 1 = 183 samtal. (Vi subtraherar 11 från 365365 och delar med 22 för att räkna ut antalet dagar efter den första dagen som barnbarnet ringde. Vi adderar sedan 11 i slutet för att räkna med den första dagen). På samma sätt kan vi räkna ut att:

Lägg märke till att barnbarn nummer 22 ringde under dagarna 1,4,73641, 4, 7 \ldots 364, medans den sista dagen som alla andra kombinationer av samtal ringdes var dag 361361. Barnbarnen har alltså ringt totalt 183+122+73=378183 + 122 + 73 = 378 samtal till mormorn. Nu har vi dock räknat antalet dagar då två barnbarn ringde en gång för mycket och antalet dagar då de alla tre ringde två gånger för mycket. Subtraherar vi antalet gånger då två barn har ringt samma dag får vi 378613725=255378 - 61 - 37 - 25 = 255. Nu har vi dock räknat bort antalet gånger då alla tre barn har ringt en gång för mycket så vi behöver därför lägga tillbaka dessa dagar igen. Vi kommer därmed fram till att mormorn har fått samtal från något av sina barnbarn 255+13=268255 + 13 = 268 dagar under året. Således har det varit 365268=97365 - 268 = \mathbf{97} dagar under året då mormorn inte har fått några samtal.

11.

Lösning 1

Lägg märke till att när vi väl har placerat ut tågvagnarna P och Y kommer de resterande tre vagnarna alltid att kunna placeras ut på 4!=244! = 24 olika sätt. Om vi kan räkna ut antalet sätt som vi kan arrangera P och Y på behöver vi alltså bara multiplicera det talet med 66 för att få det totala antalet möjliga permutationer av vagnarna. Om vi placerar ut P på första platsen finns det fem platser kvar för vagn Y. Om vi istället väljer att sätta P på den andra platsen finns det fyra platser kvar för vagn Y, och så vidare. Genom att fortsätta den här proceduren kommer vi fram till att vagnarna P och Y kan arrangeras på 5+4+3+2+1=155 + 4 + 3 + 2 + 1 = 15 olika sätt. Således finns det 1524=36015\cdot24 = \mathbf{360} möjliga sätt att sätta ihop tågvagnarna på.

Lösning 2

Vi kan också välja att lösa det här problemet genom att dela upp det i olika fall och beräkna dem alla separat. Vi får då följande fem fall:

(1) P är på den första platsen (räknat från vänster)

Vi har fem valmöjligheter för var vi ska placera tågvagn Y. De resterande vagnarna kan placeras på 4!4! olika sätt. Totalt ger detta oss 54!=1205\cdot4! = 120 möjliga utfall.

(2) P är på den andra platsen

Vi har fyra valmöjligheter för var vi ska placera tågvagn Y. De resterande vagnarna kan placeras på 4!4! olika sätt. Totalt ger detta oss 44!=964\cdot4! = 96 möjliga utfall.

(3) P är på den tredje platsen

Vi har tre valmöjligheter för var vi ska placera tågvagn Y. De resterande vagnarna kan placeras på 4!4! olika sätt. Totalt ger detta oss 34!=723\cdot4! = 72 möjliga utfall.

(4) P är på den fjärde platsen

Vi har två valmöjligheter för var vi ska placera tågvagn Y. De resterande vagnarna kan placeras på 4!4! olika sätt. Totalt ger detta oss 24!=482\cdot4! = 48 möjliga utfall.

(5) P är på den femte platsen

Vi har nu en valmöjlighet för var vi ska placera tågvagn Y. De resterande vagnarna kan placeras på 4!4! olika sätt. Totalt ger detta oss 14!=241\cdot4! = 24 möjliga utfall.

Vi kan alltså sätta ihop vagnarna på 120+96+72+48+24=360120 + 96 + 72 + 48 + 24 = \mathbf{360} olika sätt.

12. Låt oss först beräkna antalet koder som inte innehåller någon av siffrorna 2, 0, 1, 7. Detta innebär att vi i varje steg kan välja mellan 66 olika siffror. Det finns alltså 6666=12966\cdot6\cdot6\cdot6 = 1296 koder som inte har någon siffra gemensamt med Christians kod. Att beräkna antalet koder som har minst en av siffrorna 2,0,1,72, 0, 1, 7 är detsamma som att beräkna det totala antalet koder och sedan subtrahera det från antalet koder som inte innehåller någon av siffrorna 2,0,1,72, 0, 1, 7. Det totala antalet koder är 10101010=1000010\cdot10\cdot10\cdot10 =10 000 och vi vet att antalet koder som inte har någon siffra gemensamt med Christians kod är 12961296. Antalet koder som har minst en av siffrorna gemensamt med Christians kod är därmed 100001296=870410 000 - 1296 = \mathbf{8704}. Det finns alltså fler koder som har minst en siffra gemensamt än de som inte har det.

13. Låt antalet gäster på festen vara nn. Det totala antalet handskakningar är då n(n1)2\frac{n(n - 1)}{2}. Ett av talen nn eller (n1)(n - 1) måste vara udda. För att n(n1)2\frac{n(n - 1)}{2} ska vara udda krävs det att antingen nn eller (n1)(n - 1) är delbart på 22 endast en gång. Det största tal mindre än 5050 som endast är delbart på 22 en gång är 4646 så det största möjliga antalet gäster är därmed 4747 vilket ger totalt 47  462=1081\frac{47\ \cdot \ 46}{2} = \mathbf{1081} handskakningar.

14. Det här problemet kan enklast lösas genom att tänka det som att de åtta gästerna var placerade på en rad med kvinnorna på de udda platsnumrena och männen på de jämna platsnumrena. När vi har beräknat antalet möjliga permutationer då de är placerade på en rad delar vi med 88 för att ta hänsyn till rotationer.

Vi kan välja mellan fyra kvinnor på plats 11, tre kvinnor på plats 33, två kvinnor på plats 55 och en kvinna på plats 77. Damerna kan alltså placeras på 4!=244! = 24 olika sätt. Låt oss nu placera ut männen. Vi kan endast välja mellan två män till plats 22 då de inte får sitta bredvid sin partner. När vi har valt vilken man som sitter på plats 22 finns det bara tre platser kvar, men två av dessa lediga platser kommer att vara bredvid en dam som är partner till en av männen som inte har satt sig än. Den mannen kan alltså bara välja en sittplats så att han inte hamnar bredvid sin partner. När den mannen väl har satt sig har de övriga två också bara en sittplats kvar att välja mellan så att de inte hamnar bredvid sina respektive partners. Männen kan alltså placeras ut på 2111=22\cdot1\cdot1\cdot1 = 2 olika sätt när kvinnorna väl har satt sig. Om gästerna satt på rad skulle de alltså kunna sätta sig på 242=4824\cdot2 = 48 olika sätt, men eftersom att de sitter i en cirkel måste vi dela på 88 så i själva verket finns det endast 488=6\frac{48}{8} = \mathbf{6} olika sätt som gästerna sitta runt bordet på.

15.

a) För varje leksak kan vi välja mellan 33 former, 44 material, 55 storlekar och 66 färger. Det totala antalet möjliga leksaker är alltså 3456=3603456 = \mathbf{360}.

b) Alla leksaker kan sorteras in i någon av följande fem kategorier:

(1) Leksaker som är olik en svart, XL, plast kub på 4\mathbf{4} sätt.

(2) Leksaker som är olik en svart, XL, plast kub på 3\mathbf{3} sätt.

(3) Leksaker som är olik en svart, XL, plast kub på 2\mathbf{2} sätt.

(4) Leksaker som är olik en svart, XL, plast kub på 1\mathbf{1} sätt.

(5) Leksaker som är olik en svart, XL, plast kub på 0\mathbf{0} sätt.

Vi behöver räkna ut antalet leksaker som är olika på minst 22 sätt. Vi behöver alltså hitta summan av fall (1), (2) och (3). Detta gör vi enklast genom att räkna ut summan av fall (4) och (5) och subtrahera det från det totala antalet leksaker.

(4) Leksaker som är olik en svart, XL, plast kub på 1 sätt.

Om leksaken är olik i form finns det 22 alternativ att välja mellan (klot(klot eller tetraeder)tetraeder). Om leksaken är olik i material finns det 33 alternativ att välja mellan (tra¨,gummi(trä, gummi eller porslinporslin). Om leksaken är olik i storlek finns det 44 alternativ att välja mellan (L,M,S(L, M, S eller XS)XS). Och sist men inte minst, om leksaken är olik i färg finns det 55 alternativ att välja mellan (vit, gul, grön, röd eller blå). Det finns alltså 2+3+4+5=142 + 3 + 4 + 5 = 14 leksaker som är olik en svart, XL, plast kub på 11 sätt.

(5) Leksaker som är olik en svart, XL, plast kub på 00 sätt.

Det finns bara 11 leksak som är olik en svart, XL, plast kub på 00 sätt; nämligen den leksaken själv.

Det finns alltså 360141=345360 - 14 - 1 = \mathbf{345} leksaker som är olik en svart, XL, plast kub på minst två sätt.


📝Lektion 11: Antalet delare till heltal

📝Lektion 9: Mängder och venndiagram