Matematik i Genikampen – tredje avsnittet

Rolig matte?

Tredje avsnittet av Genikampen innehöll mycket matte! Så mycket att det inte hanns med att skriva om det innan avsnitt fyra kom ut. Avsnitt fyra och fem kommer jag däremot att slå ihop till ett inlägg.

Avsnitt tre innehöll tre tävlingar: allmänbildningspyramiden, bombdesarmering och pussel i duellen.

Pyramiden

I pyramidtävlingen skulle vi välja ett av fyra svarsalternativ på varje fråga, ställa in lådorna med de sidorna framåt och sedan klättra upp på pyramiden för att få en kontroll. Programledaren Micke skulle då säga hur många rätt vi hade (men förstås inte vilka som var rätt) och då kunde vi ändra lådorna till nästa kontroll. Det gällde att få alla rätt, men hur ska man göra om man inte kan svaret på frågorna?

Hade man fått veta vilka frågor man hade fått fel på, så skulle det inte ta mer än fyra testomgångar för att lyckas få alla rätt — då tar man ju bara hela tiden nästa alternativ på de som är fel. Eftersom man bara får veta antalet, så gäller det att chansa lite vilka frågor man hade fått fel på.

Mer om detta senare, men i verkliga förloppet hade vi verkligen tur med att snabbt få noll rätt.

Foto: SVT/Genikampen/Axel Bååthe
Foto: SVT/Genikampen/Axel Bååthe

Som sagt i programmet ger detta oss nu 3^10 = 59049 möjliga kombinationer för de rätta svaren som ska testat istället för 4^10 = 1048576, nästan 18 gånger färre det vill säga! I termer av utvunnen information är det till och med lite sämre att få fem rätt, då man inte vet vilka fem det är och resterande fem kan varieras på tre sätt, så antalet kombos som fortfarande funkar är:

{10 \choose 5}\cdot 3^5 = 61236

Noll rätt är dessutom riktigt bra att få tidigt, då framtida manipulationer av lådor kan bara göras på tre sätt istället för fyra (om man nu kommer ihåg de felaktiga alternativen, men vi utgår från perfekt minne här förstås).

Nu är det intressant att avgöra vilken taktik som snabbast ger en alla rätt om man bara chansar (och inte använder faktakunskaper man tror man besitter, hade vi kunnat någon fråga så hade vi nog inte fått noll rätt :)).

För enkelhets skull jämför vi två taktiker: att chansa på en låda i taget eller att chansa på två lådor i taget (och sedan förändra dem en och en för att få båda rätt). Att vända på lådorna tar ungefär lika lång tid som att att vänta på svar från programledaren, så det är det totala antalet “försök” som avgör tiden det tar att testa sig fram.

Om man vänder på en låda i taget (och har tre alternativ som kan vara rätt), så är det en på tre att man gissar rätt och två på tre att man gissar fel. I det andra fallet behöver man max gissa en gång till, sedan kan man gå vidare till nästa låda, eftersom man vet vilket alternativ som är rätt. Det allra sista kontrollen kan vi alltså bortse från (försumbart). Således, väntevärdet på antalet försök är:

\frac{1}{3}\cdot 1 + \frac{2}{3}\cdot 2 = \frac{5}{3}

Gör man detta för två lådor, blir väntevärdet då lite mer än 3.

Om vi vänder två lådor i taget kan vi få tre alternativ: antalet rätt ökar med 2, med 1 eller med 0. Om två lådor är rätt behövdes det då ett försök, om en låda är rätt, så behöver man först vända en av dem för att bestämma vilken låda som var rätt (om man vänder på den som var fel kommer antalet rätt öka med 0 eller 1 (det senare fallet händer med mycket liten sannolikhet), annars minska), sedan kommer man antingen behöva testa noll/ett alternativ till (om man vände på den lådan som var fel) eller ett/två alternativ (om man saboterade den lådan som var fel från början). Om man har däremot 0 rätt från början så vänder man på båda lådorna igen och sedan behöver vända en eller två gånger till för att få båda rätt. Totalt blir väntevärdet ungefär följande:

\frac{1}{9}\cdot 1 + \frac{4}{9}\cdot (\frac{1}{2}\cdot (\frac{1}{3}\cdot 1 + \frac{2}{3}\cdot 2) + \frac{1}{2}\cdot (\frac{1}{3}\cdot 2 + \frac{2}{3}\cdot 3)) + \frac{4}{9}\cdot (\frac{1}{4}\cdot 2 + \frac{2}{4}\cdot 3 +  \frac{1}{4}\cdot 2)

vilket också är lite mer än 3!

Därför spelar det inte så stor roll om man testar en låda i taget eller två (och sedan fixar till lådorna en och en). I längden får man göra lika många försök i alla fall.

Sedan är ju frågan om man ska gå efter genomsnittsfallet (3 försök på båda strategierna), på värsta fallet (att man har maximalt otur) eller på det bästa fallet (att man har maximalt tur).

Första strategin (vända en låda i taget) har följande antal försök (innan man vet de rätta svaren) på vart och ett av fallen:

Värsta fallet: 5
Genomsnittsfallet: 3
Bästa fallet: 2

Andra strategin har följande:

Värsta fallet: 4
Genomsnittsfallet: 3
Bästa fallet: 1

Detta visar på att om man vill köra “safe” så ska man satsa på andra strategin, då man behöver försöka färre gånger om man har otur. Men ointuitivt nog ska man också köra på den om man vill köra “djärvt” och vill kunna klara pyramiden på färsta möjliga antalet försök. Den första strategin är helt enkelt för “långsam”. Detta förutsätter att man har bra minne, men i övrigt tror jag båda lagen körde på den här strategin, vilket visar på en bra intuition för matematik och sannolikheter hos deltagarna.

Bombdesarmeringen

I andra tävlingen skulle lagen komma på ett kommunikationssystem för att kunna överföra siffrorna 0-9 och bokstäverna A-J utan ljud på ett långt avstånd till sina lagkamrater. För att inte hålla för mycket i huvudet kom båda lagen på ett system för antingen siffrorna eller bokstäverna och endast den typen skickades (gult lag skickade siffror, blått — bokstäver). Sedan översatte mottagarna på flotten: A=0, B=1, C=2 och så vidare. Detta system förutsätter att mottagarna inte till exempel råkar tänka att A=1. Effekten +/-1 är annars är ett vanligt fel vuxna brukar göra, till exempel när de programmerar eller beräknar antalet dagar i ett visst tidsintervall.

Systemet med siffror tyckte vi hade en fördel, eftersom uppgifterna gick ut på att få fram siffror, både i del 1 och del 2. Det hade varit lite extraarbete och osäkerheterna kommer in när man först ska översätta siffran till en bokstav, skicka bokstaven och sedan ska bokstaven översättas tillbaka till siffran i del 1. Men det verkade blå laget klara bra, det var inte det som var svårast, utan att lösa uppgifterna var det. Sedan är det ju en fördel i andra delen, att skicka bokstäverna direkt. I vilket fall blir det samma antal översättningarna för båda strategierna i andra delen.

Foto: SVT/Genikampen
Foto: SVT/Genikampen

När jag ändå pratar om osäkerhetsfaktorer, så är det just på grund av dem som det hade varit bra att skicka all information på en gång i andra omgången. Dykaren får veta fem bokstäver vars motsvarande kablar hen ska klippa. OM man räknat fel så finns det stor sannolikhet att kabeln med bokstaven inte ens finns. (OM man till exempel får två likadana siffror som svar så vet man redan på berget att man har gjort fel. Det vet man inte om man skickar en siffra i taget.) Då kan dykaren låta bli att klippa något och säga att en viss bokstav inte finns, vilket mottaggarna får försöka kommunicera tillbaka till räknarna.

Lag gult hann inte dock skicka ut någon information i del 2, utav vi fokuserade på att kontrollräkna istället då vi inte fick några likadana siffror.

Vad gäller del 1 så var det bra att skicka ett lås i taget, då man kan kolla just ett lås i taget (och inte en siffra i taget), om det är rätt, och kostnaden för fel är mycket mindre.

Här hittar du lösningar till alla uppgifter. Som jag nämner i det inlägget så kunde man löst uppgifterna på ett ännu smartare sätt, då man visste att svaret skulle bli en siffra. En smart lösning som min kompis Johan B tipsade mig till uppgiften

((√256 x 20 − 25^2 + 15^2 + 3^4) x 10) / 5 = ?

är följande:

Vi vill veta vilken siffra som resultatet är, därför räcker det att betrakta uppgiften “modulo 10”, det vill säga studera slutsiffram i varje steg. Till exempel ser vi att vi har uttrycket (√256 x 20 − 252 + 152 + 34) x 2, därför kommer siffran att bli jämn. Och därför räcker att kolla vad uttrycket innan x 2 kommer att vara modulo 5. √256 x 20 slutar på 0 oavsett vad √256 är, därför kan vi strunta i att räkna ut det. − 25^2 + 15^2 är båda delbara med 5 och därför inte kommer bidra till sista siffran när man multiplicerar med 2 i slutet. 3^4 är det enda viktiga och vi kan räkna ut att det slutar på 1. Därför blir slutsiffran 1×2=2.

På liknande sätt kunde man ha gjort med kabel 3-uppgiften (försök själv!)

(15 – 7)(1500 – 25) – 2200 x 3 – 8^4 – 2^10 – 79 = ?

Foto: SVT/Genikapem
Foto: SVT/Genikapem

Pusselduellen

Det var svårt att se pusslen under programinspelningen, så vi roade oss med att räkna antalet kombinationer som varje pussel kunde vara i. Sedan gäller det förstås att hitta en bra sökväg mellan alternativen för att lösa pusslen snabbt.

Första pusslet består av sex bitar. Det var kanske givet vilken bit som skulle vara längst ner (om det inte var givet kunde man ta en godtycklig bit), så de resterande bitarna kan du placera på 5!*8^5 = 3932160 olika sätt (när du väl väljer en bit och en plats kan du vrida biten på 8 olika sätt vid den platsen, givetvis kommer de flesta sätt att direkt inte passa). Det är såklart inte rimligt att testa alla de sätten då en människa kan direkt se vad som passar och vad som inte passar. Ganska enkel brute force löser uppgiften i det här fallet.

Andra pusslet bestod av 18 bitar! Om man nu bara testar att lägga ner dem som en apa (utan att bry sig om hålen), så kan man göra det på 18!*4^18 sätt (varje pinne kan placeras på 4 sätt, em kombination av bak-och-fram eller inte och upp-och-ner eller inte), och det är för stort för att få plats i Google miniräknare-fönstret (storleksordningen 10^26)! Sedan kan man ha vissa symmetrier på hela konstruktioner, men det är bara en liten konstant som man delar med.
Man kan inte minska sökvägen jättemycket här heller, utan det finns väldigt många kombinationer ändå. Man får utgå från olika bitsorter och testa att starta på olika sätt. Inte konstigt att det tog lång tid…

Tredje pusslet är lättare än den andra, då det innehåller färre bitar. Här är tricket att börja med den största biten, den med mest volym och testa alla möjligheter för hur den kan sitta i den stora (än imaginära) kuben. Sedan ska den näst största biten in och så vidare. På så sätt kapar man sökträdet som bäst i början. Här är det svårt att uppskatta antalet kombinationer som behöver “testas”, då pusslet har en mycket oregelbunden struktur.

Kommentera