Etikettarkiv: Matematik

Dricker du så dricker jag

Det är dags för en till ramble om matematisk logik.
Observera följande påstående:
”I varje bar finns en person så att om han dricker, dricker alla.”

Är påståendet sant eller falskt? Intuitivt låter det ju som total nonsense, men meningen kan granskas exakt med hjälp av predikatlogik.

Då vi betecknar personer i baren med x och y, fås följande symboliska form:
\exists x (D(x) \to \forall y D(y))

Kort förklaring:

  • \exists x betyder ”det existerar x så att…”
  • \forall y betyder ”för alla y gäller…”
  • D(x) innebär ”x dricker”
  • \to är en implikation, som har följande sanningstabell:

Två distinkta situationer gäller nu för baren:
Om alla i baren dricker, kan vi välja vilken som helst person y. Då är y en sådan person, att om han dricker, dricker alla.
Om det föregående inte gäller, finns det en person x i baren som inte dricker. Nu är båda påståendena D(x) och \forall y D(y) falska, så enligt sanningstabellen ovan är implikationen sann.

Tolkat i predikatlogik är alltså påståendet alltid sant, dvs. vi har en tautologi. Detta kan även verifieras exakt t.ex. med Tarskis sanningsdefinition.

Men beakta nu följande situation med tre personer på en bar:

Alla personerna dricker vid något skede, men ingen av dem får alla andra att dricka samtidigt. Nu verkar påståendet igen inte stämma, what gives?

Vad vi nyss har diskuterat är Drinker Paradox, som i själva verket inte är en paradox, men illustrerar hur matematisk logik inte alltid stämmer överens med naturligt språk. Skillnaden ligger i hur implikationer tolkas: i naturligt språk är en implikation inte meningsfull ifall premissen är falsk. Däremot har logikens s.k. materiella implikation ingen sådan begränsning: en levande person som påstår ”om jag är död lever jag förevigt” skulle tala sanning enligt denna modell.

Då vi ännu återgår till baren och figuren ovan, märker vi att logik inte tar tidsdimensionen i beaktande. Påståendet gäller bara som en materiell implikation då en specifik tidpunkt fixeras. Detta är meningsfullt, eftersom kunder kan anlända till och lämna baren, och i synnerhet kan vi inte tala om drickande personer ifall baren är tom.

Den materiella implikationen är inte onödig eller meningslös inom matematik, men tolkat inom en vanlig mening kan vi formulera väldigt underhållande ”sanna” påståenden. Om du vill hitta på egna: ersätt x och y med andra personer eller föremål, och D med någon annan egenskap än ”dricker”, så får du t.ex.

”I varje godispåse finns en karamell så att om den är choklad, 
är alla karameller choklad.”

”I varje ämnesförening finns en person så att om han är vegan, 
är alla veganer.”

”I varje människokropp finns ett ben så att om det benet bryts, 
bryts alla ben.”

Gott och blandat

Du kanske har hört att det krävs sju blandningar för att blanda en kortlek¹. Men varifrån kommer det här påståendet? Och krävs det faktiskt just sju blandningar?

Svaret på första frågan är ganska enkelt, påståendet kommer ursprungligen ur en artikel (”Trailing the Dovetail Shuffle to Its Lair”) av matematikerna Persi Diaconis och Dave Bayer. För att svara på den andra frågan måste vi titta noggrannare på artikeln.

Det jag menar med en blandning är en s.k. riffle shuffle², men i äkta matematisk anda så behandlar inte artikeln fysiska kortlekar som blandas utan en matematisk modell av detta. Modellen som används är den s.k. Gilbert-Shannon-Reeds modellen. I modellen går en blandning ut på att kortleken först delas i två ungefär lika stora högar. Högarna kombineras sedan ett kort i taget så att man slumpmässigt väljer en av högarna och placerar dess bottenkort överst i den nya kombinerade högen. Sannolikheten att en hög väljs är direkt proportionell mot hur många kort det finns i högen, ju fler kort desto sannolikare. Det har visat sig att denna modell motsvarar ganska bra hur människor i verkligheten blandar kortlekar.

Utöver en modell för kortblandning behöver man också ett mått på hur väl blandad en kortlek är. Det finns flera olika mått som går att användas men de fungerar alla så att man jämför resultaten av blandningen med en perfekt blandning (var alla arrangemang av korten är lika sannolika). Det måttet som Diaconis och Bayer bestämde sig för att använda kallas ”total variation distance” (TVD).

TVD kan definieras såhär. Låt A vara en händelse, t.ex. att första kortet är ruter tre eller något mer komplicerat som att man vinner en viss form av patiens. P1(A) är sannolikheten för händelsen enligt modellen och P2(A) är sannolikheten för händelsen om kortleken är perfekt blandad. TVD är lika med det högsta möjliga värdet på P1(A)-P2(A). Så om TVD=0.3 så finns det någon händelse som är 30 procentenheter sannolikare med en kortlek blandad enligt modellen än med en perfekt blandad kortlek. TVD=1 betyder alltså att kortleken är helt oblandad medan TVD=0 betyder att den är perfekt blandad.

I grafen ovanför ser vi att TVD hålls först nästan konstant men börjar sjunka snabbt kring 6 blandningar och efter det ungefär halveras det per blandning. För sju blandningar ser vi att TVD är ungefär 0.3 vilket är ganska lågt. Men är det tillräckligt lågt? Det tråkiga svaret är att det beror på vad man spelar. Det krävs färre blandningar för kortspel var man inte bryr sig om land. Men t.ex. finns det också en version av patiens var sannolikheten att man vinner är 30% högre om man använder en kortlek som har blandats sju gånger istället för en perfekt blandad kortlek.

Men TL;DR: Sju blandningar är helt ok för de flesta spel.

¹ T.ex. från Numberphile https://www.youtube.com/watch?v=AxJubaijQbI

² https://www.youtube.com/watch?v=Pd-71L3KoOI

Lustiga limerickar och vetenskaplig vers

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.