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

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

Kortlekar som ligger snyggt

Rekommenderad från: 15 år

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

Ödlornas läsning

Rekommenderad från: 13 år

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

Ett matematiskt korttrick

Rekommenderad från: 12 år

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

Uppdelning i nästan lika heltal

Rekommenderad från: 15 år

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