Etikettarkiv: Grafteori

Extreme hänggubbe

Dags för ett litet ordspel!

Spelet liknar hänggubbe eller hängman, i och med att du skall gissa ett ord som bara jag vet. Du kan gissa bokstäver, ord eller delar av ord, exempelvis ”kaff”.

Jag måste svara på om din gissning finns i mitt ord. Om det dolda ordet är ”abrakadabra” och du gissar på ”bra” svarar jag jakande, men om du gissar ”arb” svarar jag nekande. Du får inte veta var i ordet din gissning förekommer.

Frågan är nu, vad är det snabbaste sättet att klura ut ordet? Några lösningar beskrivs nedan, läs på egen risk!

Att testa sig fram tar i genomsnitt 1/2 * bordn/(bA! bB! … bZ!) försök, där bord är mängden olika bokstäver som finns i ordet. Ordet ”abrakadabra” tar ungefär 1/2 * 2911/(5! 2! 2! 1! 1!) ~ 1.27 * 1013 försök. Ett Twitter-meddelande som inkluderar siffror och små bokstäver kan ta upp till 1.37 * 10210 försök.

Så istället för att bara hitta bokstäverna som förekommer i ordet och sedan testa oss fram, varför klurar vi inte ut alla 2-strängar (2 bokstäver långa teckensträngar) som finns i ordet? Kan vi då få reda på ordet snabbare? Svar: jo.

Att klura ut alla 2-strängar kräver högst B + bord * (bord-1) / 2 eller i värsta fall B/2 + B2/2 gissningar, där B är mängden användbara bokstäver. Detta tar inte så värst länge, men vad har man för nytta av 2-strängar? Kan man med hjälp av dessa bygga snabbt upp 3-strängar?

Genom att visualisera 2-strängar som en graf kan man skära bort flera onödiga gissningar. Noderna i grafen är alla 2-strängar vi känner till, och kanterna länkar strängarna till varandra så att följande sträng börjar med delsträngen som den första slutar med. Notera att mängden olika k-strängar av ordet inte kan vara mer än n-k+1 (eller Bk för den delen). Mängden kanter i grafen kan inte vara mera än (n-k+1) * B, eftersom varje nod har högst en kant per bokstav. 3-strängar kan fortsättningsvis visualiseras som en graf, vilket till slut leder till en n-sträng, vilket måste vara ordet vi söker efter.

Notera att grafen för alla 3-strängar i ”abrakadabra” har blivit en stor ögla. I detta fall kan man gissa sig fram till lösningen genom att välja en nod som startpunkt, och sedan åka ett varv runt. I detta fall får man till näst gissningarna ”abrakadab”, ”brakadabr” och ”rakadabra”. Dessa skapar en simpel graf på 3 noder som sedan leder till ordet vi letade efter, ”abrakadabra”

Värsta möjliga antalet gissningar för ord blir till sist:

B/2 + B2/2 + (n-1) B + (n-2) B + … + 1 B = B/2 + B2/2 +  n2B/2 – nB/2

vilket vi kan avrunda glatt till n2B. I verkligheten krävs det mycket mindre arbete, eftersom grafen som bildas snabbt blir en ögla (”abrakadabra” krävde 45 + B gissningar, och en 137 karaktär lång meddelande krävde ~2100 + B gissningar). Att räkna ut det praktiska tidskravet av den presenterade algoritmen lämnar jag som läxa för läsaren.

PS. Fresh Prince of Bel-Air theme orden (1788 tecken) löses på 31446 gissningar.

Kartor, grafer och kaffemuggar

De som har deltagit i gulisintagningen tidigare under hösten känner kanske till muggen ovan. Vid matematikpunkten på Wall Street Bar fick gulisarna till uppgift att med tusch koppla varje hus till varje enhet (el, vatten, gas) utan att förbindelserna korsar varandra. De fick med andra ord lösa det s.k. Three Utilities Problem. Om du vill fundera på problemet själv och undvika spoilers, gör det nu (Eller kolla på 3Blue1Browns video om temat, rekommenderas varmt).

Det väsentliga som gjorde uppgiften lösbar är att en mugg är (topologiskt sett) fundamentalt annorlunda än ett klot eller ett papper. Om man tänker sig att muggen är gjord av lera, kan man utan att bryta den eller slå nya hål forma om den till en donits. Med andra ord är kaffemuggen en torus, en sluten kropp med ett hål. Det visar sig att uppgiften är lösbar på en torus, men inte på ett klot eller ett papper!

 

Muggproblemet kan förvånansvärt nog ge oss insikt om ett helt annat problem: Om du har en karta där varje land är en sammanhängande region, hur många färger behöver du för att färglägga varje land utan att två grannländer får samma färg? Då kartan är ritad på ett papper eller en boll visar det sig att högst fyra färger behövs; resultatet är känt som Four color theorem.

Kartan över Frankrikes provinser behöver fyra färger

Men om kartan är ritad på en annan slags kropp, t.ex. en torus, räcker fyra färger till? För att förstå denna situation bättre söker vi ett ”renare” sätt att rita vår karta. Vi ersätter först varje region med en punkt. Sedan ritar vi streck mellan två punkter ifall de motsvarande regionerna gränsar till varandra. Det vi får är en graf: en samling noder (punkter) och kanter (streck) mellan dessa. I själva verket är det en planär graf, dvs. den kan ritas utan att två streck korsar varandra.

En karta och dess motsvarande graf

Det visar sig att varje karta motsvarar en planär graf och vice versa. Så istället för att granska kartor på en torus, kan vi kolla på planära grafer på en torus: Hur många färger behövs för att färglägga noderna så att två grannar inte får samma färg? Men här kommer insikten från muggproblemet in: Grafen som bildas i Three Utilities Problem är inte planär på ett papper (dvs två kanter måste korsa varandra) men den är planär på en torus. Det betyder att mängden av planära grafer på en torus är fundamentalt större!

Kan vi alltså hitta en graf som kräver mer än fyra färger? Grafen i muggproblemet kan färgas med endast två färger. Men t.ex. den kompletta grafen K5 kräver 5 färger och kan ritas på en kaffemugg utan att två kanter korsar varandra.

K5 ritad på en kaffemugg utan att två kanter korsar

Och vad är det högsta antalet färger vi kan behöva?
https://mathsgear.co.uk/products/7-colour-torus-mug

Det mest spännande inom matematiken är då två koncept som verkar mycket annorlunda egentligen är nära sammankopplade. Många situationer där vi beaktar föremål (länder) och förbindelser mellan dem (gränser) kan uttryckas med hjälp av grafteori. Men en grafs egenskaper hänger inte bara på grafen själv, utan också på kroppen den ritas på. Kaffemuggen är ett intressant topologiskt föremål, inte bara en pryl för att hälla i sig kaffe.