kombinatorik – Sida 2

Planära grafer

I ett sällskap med många personer kan man leka en lek som kallas ”knuten”. Alla ställer sig i en ring och sluter ögonen. Sedan sträcker alla fram båda sina händer och börjar gå mot mitten. Alla ska ta tag i två andra händer med sina egna.

Efter att alla är klara med det öppnar man ögonen. Målet är nu att lösa upp ”knuten” som bildats utan att släppa taget med händerna. Det gäller att bilda en stor ring igen (det kan också hända att det blir flera ringar).

Ett liknande spel är Planarity, fast personerna i spelet kan ha fler än två händer. Målet är att lösa upp all tilltrassel så att inga par av händer måste hållas över varandra.

Personer är representerade med punkter och en kant som går mellan två punkter visar att de två personerna håller handen. Alla spelande har väldigt uttänjbara händer. Försök att klara några nivåer! (Jag kom till Level 7.)

Sådana här bilder kallas grafer, om de går att ”plana ut” på det här snygga sättet (så att inga två kanter korsar varandra) kallas de planära. Det är svårt att se direkt huruvida en graf är planär eller inte, däremot uppfyller alla planära grafer följande formel.

Eulers formel

En graf är ritad på ett plan på så sätt, att inga två kanter korsar varandra. Om V är antalet hörn i grafen, E – antalet kanter och F – antalet områden som planet delas upp i, så gäller:

V – E + F = 2

Att det blev just talet 2 beror på att man ritade på ett plan. Ritar man grafer på andra konstiga ytor blir det ett annat specifikt tal just för denna yta. Det talet kallas ytans eulerkaraktäristik.

Lösning till problem vecka 19

En fotboll är hopsydd av 32 lappar: vita sexkanter och svarta femkanter. Varje svart lapp gränsar till bara vita, varje vit lapp gränsar till tre vita och tre svarta lappar. Hur många vita lappar finns det i en fotboll?

Man kan anta att Eulerkarakteristiken på fotbollen är 2 och arbeta utifrån det, om man nu vet vad Eulerkarakteristik är för något. Med nedan använder jag mig av Thomas lösning.

Lösning:

Det finns S svarta lappar och V vita lappar. Totalt finns det 32 st, så S + V = 32.

För varje svart lapp finns 5 vita lappar runt den, men varje vit lapp ligger intill 3 svarta, så 5S räknar varje vit lapp 3 gånger och vi får 5S / 3 = V

Och S + 5S/3 = 32, det vill säga 3S + 5S = 96 och då är S = 12, V = 20. Alltså finns 20 vita lappar.

Omkastad stad

Rekommenderad från: 12 år

[kkratings]

Benny skrev upp namnet på sin hemstad och alla cykliska ”förskjutningar” av det och fick tabell 1. Sedan ordnade han om namnen och skrev de i bokstavsordning i tabell 2 i stället.

v48

Därefter läste han av ”ordet” i sista kolonnen: SLAUPPA.

Josefin gjorde samma sak med sin hemstad och fick ”ordet” TNUUENRTL. Vilken stad kommer Josefin ifrån om man vet att den börjar med bokstaven L?

Visa lösningen

I både tabell 1 och tabell 2 kommer varje bokstav i stadens namn komma på sista plats exakt en gång (eftersom ”orden” är alla förskjutningar av stadsnamnet).

Eftersom vi vet att ”orden” i tabell 2 kommer i bokstavsordning, så kan vi rekonstruera första kolonnen i den tabellen:

BILD 1

Notera nu att i tabellen står ”förskjutningar” av stadsnamnet. Då kan vi läsa av den delen av tabellen som vi fick fram att exempelvis att bokstaven R kommer precis efter bokstaven E, att ena bokstaven T kommer precis efter en bokstav N och den andra bokstaven T kommer precis efter en bokstav R och så vidare (föreställ er nu att ordet loopar, det vill säga vi kan säga att första bokstaven kommer precis efter det sista).

Med denna information kan vi rekonstruera andra kolonnen i tabell 2. Där vi garanterat vet efterföljaren (efter U kommer N, efter E kommer R, efter R kommer T, efter L kommer U) skriver vi in den direkt i den andra kolonnen. Där det finns tvetydighet (efter T kommer E eller U, efter N kommer L eller T) avgör vi hur de ska skrivas in med hjälp av bokstavsordningen. Till exemepel, E kommer före U i alfabetet, så det nya E:et ska skrivas in på 6:e raden och den nya U:et ska skrivas in på 7:e.

BILD 2

Vi fortsätter med samma princip att fylla på kolonnerna en i taget. Vi har en tydlig instruktion för hur tabellen ska fyllas i, eftersom vi vet efterföljarna för varje bokstav samt att ”orden” i tabell 2 står i bokstavsordning.

Till slut kommer vi kunna fylla hella tabellen och läsa av ordet i andra raden (eftersom staden började på L). Det kommer vara staden LUNTERTUN. Luntertun ligger i Ängelholms kommun i Skåne.

I både tabell 1 och tabell 2 kommer varje bokstav i stadens namn komma på sista plats exakt en gång (eftersom ”orden” är alla förskjutningar av stadsnamnet).

Eftersom vi vet att ”orden” i tabell 2 kommer i bokstavsordning, så kan vi rekonstruera första kolonnen i den tabellen:

lv50_1

lv50_2

Till slut kommer vi kunna fylla hella tabellen och läsa av ordet i andra raden (eftersom staden började på L). Det kommer vara staden LUNTERTUN. Luntertun ligger i Ängelholms kommun i Skåne.

Kortlekar som ligger snyggt

Rekommenderad från: 15 år

[kkratings]

Tag en vanlig kortlek med 52 kort. Säg att kortleken ligger snyggt, ifall varje par av kort där ena ligger på den andra antingen har samma färg eller samma valör, samma sak gäller för det översta och nedersta kort samt att spader ess ligger överst. Visa att antalet sätt att lägga kortleken snyggt är

(a) delbart med 12! (12 fakultet, det vill säga 12*11*10*9*8*7*6*5*4*3*2*1)

(b) delbart med 13! (13 fakultet)

spader_ess

Visa lösningen

(a) Det gäller alltså att hitta något villkor (som kan variera), som när det är uppfyllt ger upphov till exakt 12! olika fall. Det där låter lite luddigt om man inte har funderat på det, men här kommer det mer konkreta förklaringen.

Spader ess är fixt, det kan vi inte flytta på. Säg att vi har något snyggt sätt som kortleken är lagd på. Notera då att vi kan byta plats på alla treor och alla fyror i respektive färg (så hjärter tre och hjärter fyra byter plats osv.)

Men vi kan även byta plats på alla tvåor och kungar samtidigt. Vi kan egentligen byta plats på vilka valörer som helst så länge alla kort av den valören byts mot ett annat fixt valör och så länge essen inte flyttas (de får inte flyttas för spaderesset).

Eftersom man får byta plats på 12 valörer (man kan även byta fler än 2 valörer samtidigt, t.ex. tvåor byts mot treor, treor mot fyror och fyror mot tvåor), så finns 12! sådana byten. Därför är antalet snygga uppläggningar delbart med 12 fakultet.

”Villkoret” här var egentligen att vi fixerade vilken färg varje plats hade samt vilka platser som hade likadana valörer och alla essens platser var också bestämda. Det finns 12! sätt att nu placera ut de bestämda valörerna.

(b) Uppgiften kan ses på ett annat sätt. I fall det finns en 4×13-tabell, där raderna betecknar färger och kolonnerna betecknar valörer, så är antalet snygga sätt lika med antalet sätt som ett torn kan inuti tabellen så att den startar från säg vänstra övre hörnet, kommer till varje ruta en gång och sedan kommer tillbaka till sin egen plats. Kom ihåg att ett schacktorn kan gå lodrätt eller vågrätt godtyckligt många rutor.

Eftersom delen (a) är visat, räcker att bevisa att antalet sätt är delbart med 13. Klistra ihop tabellen längs de korta ändarna så att det bildas ett band med fyra rader. Om vi fixerar en rutt som börjar från spader ess så kan vi rotera bandet 12 steg så att det för varje steg bildas en ny rutt (som inte längre börjar med spader ess).

Vi visar att varje sådan falsk rutt kan göras om till en riktig och den kommer inte vara lika med den ursprungliga.

Varje falsk rutt går ändå igenom spader esset vid något tillfälle, och eftersom den kommer tillbaka till samma ruta som den startade ifrån så kan den lika gärna betraktas som en rutt som börjar i spader ess (som nu är tillåten).

Men varför är det inte lika med det ursprungliga? Då skulle rutten vid en viss rotation avbildas till sig sjäv. Betrakta då vilket som helst vågrätt drag (ett sådant måste finnas). Om vi gör rotationen 13 gånger så ser vi att alla rutor på den raden är startpunkter för vågräta drag (eftersom 13 är ett primtal). Men det kan inte vara möjligt, eftersom vi då inte kommer från den raden.

På så sätt delas rutter upp i grupper om 13 och alltså är antalet rutter delbart med 13!

Ödlornas läsning

Rekommenderad från: 13 år

[kkratings]

Vi människor läser vanligtvis från vänster till höger och uppifrån och ner. Ödlor är inte lika snabba på att läsa, men de kan göra det på fler olika sätt. Ödlan kan läsa en bokstav och sedan förflytta sig ett steg ner, upp, till höger eller till vänster för att fortsätta läsa.

På hur många sätt kan en ödla läsa ordet FJÄRIL här nedan?
val4

Visa lösningen

Diskussion:

Man kan förstås bara sätta igång och försöka räkna alla sätten. Det är en helt okej metod för att ta reda på svaret, men det finns ingen garanti på att man räknar rätt och inte glömmer någonting. Egentligen går uppgiften ut på att skapa just den garantin, att alla fall är medräknade. Det kallas att man gör systematisk undersökning.

Men det är krånglig att göra en direkt systematisk uppräkning. Det finns 11 stycken F att börja läsa på, redan där 11 fall som vi måste hålla koll på. Vid flera av F:en har vi två vägval, vi måste nämligen välja något J. Och så vidare … och det går förstås att komma fram till rätt svar men det blir mycket krångel.

Det underlättar att notera att bilden är symmetrisk. För varje F utom det längst upp finns ett motsvarande på andra sidan pyramiden. Det finns exakt lika många sätt att läsa FJÄRIL från de speglade F:n. Därför räcker det att räkna ut antalet sätt från de första 5 F:en och sedan multiplicera det med två och sedan addera ett sätt till (från det mittersta F:et går det att bara läsa neråt). Efter det kan man notera mer symmetri som underlättar beräkningar. Det slutar med att man bara måste räkna antalet sätt från de första tre F:en. Det blir totalt 1+5+10+10+5+1+5+10+10+5+1=63 sätt.

Vi kontrollerar detta på ett annat sätt.

Lösning:

Notera att antalet sätt att läsa ordet FJÄRIL är samma som antalet sätt att läsa ordet LIRÄJF (vi låter ödlan läsa baklänges). Och annorlunda formulerat, det är lika med antalet sätt att komma från bokstaven L till kanten av pyramiden, gående till nästa bokstav i ordet LIRÄJF varje gång.

Vi löser ett lite större problem. Nämligen, för varje ruta, sätt ut ett tal som berättar om hur många sätt det finns att ta sig till den rutan om man börjar i L. I början får vi följande bild, ty det finns bara ett sätt att komma till varje I från L:et:

lv22_1 Om vi nu ska forsätta vandra till R:en, så kan vi hamna i vissa R från två olika I. Därför ska antalet sätt adderas där och vi får totala antalet sätt att läsa LIR och sluta i ett specifikt R. Just här är det kanske inte så svårt att räkna dem sätten från början, men metoden blir mer användbar senare:

lv22_2 Forsätt att fylla ut tabellen på det sättet. Varje nytt tal blir summan av talen som kommer ”precis innan”, till exempel på höger sida blir det summan av talet under och talet till vänster (om nu båda finns). Till slut fås tabellen:

lv22_3 Återigen, antalet sätt totalt att läsa ordet LIRÄJF är 1+5+10+10+5+1+5+10+10+5+1=63.

För dig som har orkat läsa så här långt kommer en extrafråga. Vad kommer svaret att vara om vi har ett längre ord istället för FJÄRIL? Låt säga att vi har en pyramid av samma sort, men ett ord som har n olika bokstäver.

Ett matematiskt korttrick

Rekommenderad från: 12 år

[kkratings]

En trollkarl med förbundna ögon och hans assistent utför följande trick. Trollkarlen har 29 kort med talen 1 till 29 på. Han ger korten till någon person i publiken, som väljer ut två av dem. Resten av korten ges till assistenten, som sedan väljer två av de resterande korten och visar till personen i publiken. Personen läser upp högt båda talen för trollkarlen (i vilken ordning han vill). Därefter gissar trollkarlen vilka kort som personen valde ut i början.

Hur skall trollkarlen och assistenen förbereda sig för att alltid lyckas med tricket?

clipart-magician-012

Visa lösningen

Diskussion:

Problemet kan först verka svårt när vi har så många kort att hålla reda på. När talet i uppgiften är stort, försök att lösa samma uppgift, fast med ett mindre tal. Välj till exempel antalet kort till 5.

Ifall bara 4 kort är inblandade handlar det inte om något trick längre. Assistenen kan ju bara välja de två korten som är kvar och trollkarlen gissar förstås vilka kort som saknas.

Lösning för 5 kort:

För att tricket alltid ska funka måste varje par av tal som trollkarlen hör ge ett bestämt par av tal som trollkarlen sedan ska gissa på. Det gäller alltså att ”para ihop” par av tal och alla dessa fyra tal måste vara olika för lyckat trick. För 5 tal kanske man listar ut svaren på följande sätt:

Para ihop alla kanter i en femhörning med var sin diagonal så som det ser ut på bilden. femhörning färg

lv19_1 Till exempel så är följande kanter bruna: den som binder ihop 2 & 3, samt den som binder ihop 1 & 4. Ifall assistenten ser att åskådaren plockar bort korten 2 och 3, så pekar han på korten 1 & 4 och trollkarlen kan då komma ihåg att kanten 1 & 4 hade den bruna färgen och säga exakt vilka kort som plockades bort från början (de som också hade den bruna färgen).

lv19_2

Ett annat exempel vore om personen i publiken valde korten 1 & 3, så pekar assistenten på korten 4 & 5 eftersom de paren har samma röda färg:

Lösning för 29 kort:

De flesta skickade in lösningen som följer. Här gäller det att tänka som att alla korten läggs på rad och att efter 29 kommer 1 igen. Trollkarlen och assistenten kan även tänka att korten ligger i en cirkel i ordning.

Vad händer då om en person i publiken väljer vilka som helst två kort? Om de inte ligger bredvid varandra, så pekar assistenten på de korten som ligger direkt efter vart och ett av de bortplockade, som till exempel här:

lv19_4 Om de valda korten ligger bredvid varandra, så pekar assistenen på två kort som också ligger bredvid varandra, nämnligen de två som kommer direkt efter. Här är ett exempel:

lv19_5

Trollkarlen kan se skillnad på de olika fallen. Ligger de talen han hör inte bredvid varandra, så gäller det första fallet. Då ska han bara subtrahera 1 från varje (och säga 29 ifall något av talen var 1). Ligger talen bredvid varandra, så ska han subtrahera 2 från varje (på samma sätt här, lite speciell subtraktion vid gränsen).

Notera att lösningen fungerar på samma sätt för vilket som helst antal kort och inte bara 29.

Uppdelning i nästan lika heltal

Rekommenderad från: 15 år

[kkratings]

På hur många sätt kan man skriva talet 2009 som en summa av några positiva nästan lika heltal? Talen kallas nästa lika om deras skillnad är (till beloppet) maximalt 1. Sätten betraktas som samma om det enda som skiljer dem åt är ordningen på termerna.

vecka17

Visa lösningen

Diskussion:

Först och främst ska man pröva sig fram till lösningar, för att ”känna på” problemet. Det gäller alltså att komma på några sätt att dela 2009 i några nästan lika stora delar. En första tanke är att dela upp det som en summa av lika stora delar. Hur man göra det beror på vilka tal 2009 är delbart med.

2009 = 7*287 = 7*7*41

Så till exempel har vi uppdelningarna i exakt lika termer

2009 = 287 + 287 + 287 + 287 + 287 + 287 + 287

2009 = 1 + 1 + … + 1 (2009 stycken ettor)

2009 = 41 + 41 + … + 41 (49 stycken 41:or)

2009 = 2009

Men vad händer om vi försöker dela upp i ett visst antal termer, där antalet inte är en delare till 2009? Till exempel två termer? Då delar vi på två så gott det går, resultatet blir 1004 med rest. Men uppdelningen

2009 = 1004 + 1005

funkar ju, för att 1004 och 1005 är nästan lika.

Försök på samma sätt med tre termer. 2009 delat på 3 blir 669 och resten är 2. Då kan vi göra såhär:

2009 = 669 + 670 + 670

Den här idén med rester kommer vi att använda i lösningen.

Lösning:

Enligt villkoren måste varje sätt att summera upp till 2009 innehålla maximalt två sortes termer: ena kan uttryckas som x och andra som x+1. Ifall det fanns andra tal, skulle de inte vara nästan lika med x eller x+1.

Notera nu att för varje antal termer (beteckna antalet med n), så finns det ett sätt att dela upp 2009 i just så många nästan lika termer. Nämligen, dela 2009 med n med rest:

2009 = n*k + r

där k är kvoten och r är resten. Man vet att resten alltid är mindre än det man delade med, således mindre än antalet termer.

Likheten kan skrivas om:

2009 = k + k + … + k + r

där termen k förekommer n gånger. Men för att få just n stycken termer, fördelar vi r stycken ettor på r stycken k-termer. Det kan vi göra eftersom k är mindre än n. Således:

2009 = k + k + … + k + (k+1) + (k+1) + … + (k+1)

där termer av typen k förekommer (n-r) gånger och termer av typen (k+1) förekommer r gånger.

Så nu har vi 2009 stycken sätt att dela upp! Ett sätt för varje antal termer. Men finns det inga andra sätt?

Nej, faktiskt inte. Vi sa ju tidigare att termerna måste vara x och x+1. Har vi ett fixerat antal termer i summan

2009 = x + x + … + x + (x+1) + (x+1) + … + (x+1)

så kan vi inte ändra vare sig några x till x+1 eller tvärtom, för då skulle det hela inte summera upp till 2009.

Således är svaret: 2009 sätt.