Kategoriarkiv: Vecktraklet

Den icke-trivialaste trivian du inte vill missa!

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.”

Limericks med, för och av Spektrum

En limerick är en sorts skämtvers eller dikt. Namnet härstammar från den Irländska staden Limerick men versformens ursprung är okänt. Den brittiska författaren Edward Lear populariserade limerickversen. En typisk limerick kan se ut som följande:

”There was an Old Man of Cape Horn
Who wished he had never been born;
So he sat on a chair,
Till he died of despair,
That dolorous Man of Cape Horn”

Edward Lear: ”Book of nonsense”

En limerick ska således ha fem rader med rimordningen: A A B B A. Den första raden brukar av tradition avslutas med ett geografiskt namn men det är inte obligatoriskt. Rad 1, 2 och 5 har vanligen mellan åtta och 10 stavelser medan rad 3 och 4 har fem eller sex stavelser. Vi har här på Spektraklet tidigare skrivit limericks och om limerickar. Robert skrev om användandet av limerickar som minnesregler för matematiska formler: https://spektrum.fi/spektraklet/lustiga-limerickar-och-vetenskaplig-vers/ och Palle skrev limerickar om förra årets årsfestvecka: https://spektrum.fi/spektraklet/en-limerick-for-arsfesten-lxxxv/.

På engelska finns det en hel del finurliga limerickar med naturvetenskapstema. Bland annat från Harvards fysikfakultets hemsida hittas flera skämtsamma verser: https://www.physics.harvard.edu/academics/undergrad/limericks. Jag har dock inte lokaliserat ett liknande utbud på svenska. Därför efterlyser jag nu limerickar av er läsare, helst med naturvetenskapstema eller Spektrumanknytningar. Lämna gärna era limericks som kommentarer till denna artikel.

Här följer några limericks på tidigare nämnda teman:

Några av studielivets bästa hits
Avsluta en tentvecka med sitz
Festa på klubben
Ponga med Stubben
Och vakna på akutrummets brits

Det var en fysiker från Pampas
Som med fymmen försökte tampas
Men så gick något fel
I tentens första del
Och i hans hjärna det börja krampas

En man kämpade sig uppför Gumtäktsbacken
Väskan var tung och öm var nacken
I dörren han tog tag
Insåg att det var fel dag
Han svor, gäspade och vände på klacken

Relativistiska skämt är av sådan sort
Att längdkontraktionen gör den kort
För att inte bli sur
Behöver man tur
Så poängen inte lämnas….(bort)

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