Kategoriarkiv: Vecktraklet

Den icke-trivialaste trivian du inte vill missa! Semi-regelbundna korta texter, länkar till andra webbsidor och simpla förklarningar på ting.

2018, Vecktraklet

Lustiga limerickar och vetenskaplig vers

Lämna en kommentar

Matematiska texter från antikens och medelålderns Indien hade en egendomlig struktur. För att hjälpa läsaren minnas dem framställdes problem och resultat ofta som vers. Till exempel Bakshali-manuskriptet är en sådan text.

I nutidens utbildning är poesi en form som används väldigt lite inom vetenskaplig utbildning. Trots det hittar man på nätet många matematiska verser, som människor skrivit för skojs skull eller för att minnas dem bättre. En särskilt minnesvärd versform är limericken, varav några presenteras till näst (i ökande svårighetsgrad):

”A dozen, a gross and a score
Plus three times the square root of four
Divided by seven
Plus five times eleven
Is nine squared and not a bit more”

Ramsan beskriver följande simpla uträkning:
\displaystyle\frac{12+144+20+3\sqrt{4}}{7}+(5\cdotp 11) = 9^2 + 0
Huruvida ramsan är användbar eller inte lämnas till läsarens beaktande. Till näst nåt en aning knepigare:

”The integral z squared dz
From one to the cube root of three
Times the cosine
Of three pi over nine
Is the log of the cube root of e”

Här beskrivs en annan identitet:

\displaystyle\int_{1}^{\sqrt[3]{3}}z^2dz \cdotp \cos{\left(\frac{3\pi}{9}\right)} = \ln{\left(\sqrt[3]{e}\right)}

Läsaren må påminnas att \cos{\left(\frac{3\pi}{9}\right)} = \frac{1}{2} och \ln{\left(\sqrt[3]{e}\right)} = \frac{1}{3}.
I allmänhet är de två föregående verserna skrivna mer för poesins skull, inte för innehållet. Till sist ett mer sofistikerat resultat:

”Take M a complete metric space
If nonempty, it’s always the case
That if f’s a contraction
Then under its action
Exactly one point stays in place”

Versen beskriver den s.k. Banachs fixpunktssatsen. Utan att överkomplicera: I ett fullständigt metriskt rum gäller att om på varandra följande punkter i en följd kommer godtyckligt nära varandra, så har också hela följden en gränspunkt den går mot. En kontraktion är en funktion som, givet två godtyckliga punkter, flyttar dem närmare varandra än de var förut.

MS Paint-illustration av Banachs fixpunktssats

Satsen säger, att kontraktionen f har endast en unik fixpunkt, dvs. en punkt som inte rör sig då kontraktionen appliceras.

Limericken om Banachs fixpunktssats hjälpte mig faktiskt minnas satsen till provet i topologi. Poesi är ett kraftigt verktyg för att få något att fastna i huvudet, och jag skulle vilja se det användas oftare inom matematikutbildningen. Så länge innehållet är ändamålsenligt alltså; förvränger man ekvationer för att göra dem till limericks så gör man det nog mest för poesins skull.

 

2018, Vecktraklet

Extreme hänggubbe

Lämna en kommentar

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.

2018, Vecktraklet

Minne: Kapitel 2

Lämna en kommentar

Direkt Robben tror sig trycka på strömbrytaren känner han en kraftig smäll på kinden och han kvicknar till. Under en kort stund är han igen borttappad och förbryllad, men efter ett par minuter börjar pusselbitarna äntligen falla ihop. Smällen på kinden fick han av Linda, en ung matematiker, som väckt honom och nu berättar vad Robben gjort den senaste timmen.

Robben hade tydligen aldrig gått hem efter den sista beerpongen, utan efter att ha vunnit spelet mot gamylerna John och Mathias hade han ännu svept ett fullt stop öl och meddelat med hög röst att ”jag tror jag borde gå hem nu”. Enligt Linda var detta uppenbarligen stunden då Robben tappat sitt minne och började yra omkring på Alina-salen värre än Spektrums normala fyllehund Olle.

Robben hade, istället för att ta rocken och gå hem, börjat vingla sig mot kökets frys och letat fram en iskall flaska punsch. Han hade bestämt sig för att en pünschen skulle förgylla kvällen och fick Olle övertalat om att detta faktiskt stämmer. John och Mathias fungerade som domare och som nyfiken gulis hade Linda tagit fram sin telefon och filmat hela prestationen, och visade den till Robben som nu var övertygad om att pünschen inte hade varit en bra idé. Olle och Robben var supertaggade på pünschen och hade före starten meddelat med väldigt berusad röst: ”full power framåt, inget kan stoppa oss”. Linda, som hade en ny telefon och inte ännu fullständigt bemästrade den, hade glömt blixten på då hon filmade vilket hade förbryllat både Robben och Olle.

Efter att Robben slickat den sista punschen från tallriken och domarna meddelat att prestationen var underkänd pga för mycket spill, hade Robben fallit ner på golvet och slocknat. Robben vaknade efter en dryga 10 minuter och började mumla något om att han har en föreläsning nästa dag klockan åtta och borde komma ihåg att lägga alarmet på så att han inte sover hela morgonen. Linda hade då hjälpt Robben att ställa in hans alarm på klockan till 07:30 (vilket borde räcka så att han hinner från Majstranden till Gumtäkt på morgonen), men Robben hade som princip att alltid ha ett primtal som minutvärdet på sin väckning, så Linda ställde klockan in på 07:31 så att Robben var nöjd. Nu började Robben vingla sig mot vessan, en del krypandes och en del på två ben. På vägen till vessan hade Robben knuffat Spektrums vice-ordförande Albert som redan börjat moppa golvet och spytt i vattenämbaret som Albert använt till moppandet. När Robben äntligen kommit fram till vessadörren försökte han våldsamt knuffa sig genom dörren tills han lyckades dra i dörren och den öppnades. Då hade Robben blivit stående i dörröppningen med en tom blick mot väggen. Nu hade Linda fått nog av Robbens yrande och gett honom en klapp på kinden för att få honom tillbaka till denna verklighet.

Linda, som också bodde i Majstanden, bestämde sig för att hjälpa Robben hem, klockan var ju redan fyra på natten och Robben verkade inte vara i skick att hitta hem på egen hand. De tog flygfältsbussen och steg av i Vallgård och gick tillsammans mot Arabia. Robben hade nyktrat till lite grann och medan de gick började Linda och Robben tala om allt mellan himmel och jord. Linda märkte att Robben egentligen var ganska trevlig och smart trots kvällens X antal öl. De växlade telefonnummer utanför Robbens hemdörr där han bad om ursäkt och tackade Linda för en trevlig och förvirrande kväll. Robben steg in, märkte att han hade väckning om knappa två timmar och ramlade i sin säng och somnade direkt.