strategi – Mattebloggen

Matematik i Genikampen – tredje avsnittet

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.

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.

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 = ?

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.

Matematik i Genikampen – andra avsnittet

Andra avsnittet innehöll kanske inte lika mycket matte som första avsnittet, men det betyder ju inte att man inte skulle vara smart för att klara tävlingarna. Och allt som har med kreativt tänkande att göra kan jag om jag vill koppla ihop med matte så nu tänker jag göra det.

Flottbygge: Planering och materielinköp

Vi fick 3000 kronor för att handla materiel till vår flotte. Tävlingsledarna skulle kopiera både gula och blå lagets inköp och lagen skulle få de andras inköpta material först. Men i andra omgången skulle lagen få eget material, så det gällde att inte köpa sjukt dåliga saker. Framförallt gällde det att köpa något som man själv skulle ha mer nytta av än motståndaren i samma situation.

Enligt tävlingsreglerna behövde man antingen vinna båda omgångarna för att vinna hela tävlingen eller vinna en av omgångarna med bäst vinsttid (det vill säga, bara tiden för den vinnande omgången räknades). En grej som är lätt att se i efterhand och lite svårare att tänka på innan tävlingen är att det är bara den andra omgången som spelar roll. Givet erfarenhet och att man bygger med eget material tar den andra omgången med störst sannolikhet kortare tid för båda lagen. Det gällde alltså att samla erfarenhet i första och ge järnet i andra omgången.

Under tidspress kunde vi inte vara så värst smarta och planerade en konstruktion som skulle bli alldeles för tidskrävande i andra omgången (så den övergavs). Inne i affären fokuserade vi på att göra beräkningar av typen ”hur mycket volym måste flotten ha för att bära allas vikt?” (blå laget räknade detsamma verkar det som). Fysik i all ära, men ingenjörskonsten med höftning snarare än exakta beräkningar tar ändå alltid priset när det är snabba puckar och inte forskning som gäller.

Andra beräkningar som vi kunde göra skulle då vara hur många hinkar sand flotten skulle kunna bära (förutom oss själva då). Jag kom tyvärr inte ihåg att vi hade fått hinkmått eller mått på lådan vi skulle fylla också, så jag fokuserade på att räkna på kostnaden istället. Tog lite i överkant på varje vara för att inte hamna över (samt för att räkna snabbt) och det slutade med att vi verkligen inte hamnade i överkant, utan hade kunnat köpa typ ett halv toasits till.

Att köpa toasitsar som åror var en briljant idé utav Nina som sparade gula laget mycket tid som annars skulle behövs till åror-tillverkning. Synd att de var så dyra!

Flottbygge: Första omgången

Första omgången gick för båda lagen ut på att samla erfarenhet, framför allt om en bra form på flotten samt om hur många omgångar fram och tillbaka som skulle behövas för att fylla lådan med sand. Vi hade nio hinkar tillgängliga, om jag minns rätt (dock sänkte vi i gula laget en hink i sjön i första omgången). Gula laget hann dumpa sand två gånger, medan blå fyllde hinken på tre gånger! Det betydde att två eller tre gånger skulle behövas i andra omgånger för att vinna hela tävlingen.

Om man skulle åka två omgångar långsamt istället för tre snabbt skulle man ändå vinna tävlingen då tiden att åka fram-tillbaka-fram är tre intervall, medan fram-tillbaka-fram-tillbaka-fram är fem intervall, alltså tar det andra fallet mer än 50% mer tid än det första, om man nu åker med samma hastighet. Tiden det tar att dumpa sand är försumbart i jämförelse med tiden det tar att åka. I programmet hör man att vinsttiden är mer än femtio minuter. Skulle gissa på att max 15 min gick ut på att bygga för blå laget, medan allt annat var rodd (i snitt 7 min per sträcka fram eller tillbaka).

Flottbygge: Andra omgången

Vi i gula laget satsade på att fylla lådan på två rundor, det vill säga åka fram-tillbaka-fram och vinna. Blå laget satsade på samma sak. Viktiga skillnaden för gula laget var att istället för att lägga de 12 frigolitbitarna i fyra lager lägga dem i tre lager. Det betyder att flotten blev till ytan större (4 plattor iställer för 3) och mer stabil (lägre). Det var helt klart den största förbättringen för gula laget gentemot första omgången. En eloge till blå laget som körde på den utformningen av talet 12 redan från omgång ett! I slutändan som det syns i avsnittet var det inställning och småsaker som avgjorde och inte matten. Men utan de idéer som jag nämnt skulle det gula laget varit körda. Tur att det är hög lägstanivå på lagen, så att det inte blir jätteskämmigt när vi spelar genier!

Laser och speglar

Andra tävlingen gick ut på att rikta en laserstråle med hjälp av speglar. Strålen skulle förbi en massa hinder och träffa en ”prisma” (jag tyckte det mera såg ut som en halvklot ihopsatt med en halvikosaeder eller nåt, en prisma ska ha två kongruenta parallella sidor vad jag vet). Tävlingen gick i omgångar; varje omgång bestod av en planeringsfas och en resultatfas. Under planeringen fick man mäta på banan, ställa om och flytta på speglar, göra eventuella beräkningar. Sedan fick man se laserstrålen tändas och en person fick springa fram och göra högst en markering på banan.

Detta syns inte i tv men tävlingen tog hela 14 (!) omgångar. Första omgången träffade gula laget sin första spegel, medan blå laget gjorde inte ens det. Till andra omgången flyttade vi i andra laget andra spegeln lite för att strålen skulle träffa den, men tydligen flyttade vi den lite för mycket! Det var bara på tredje omgången som andra spegeln blev träffad. Och detta var bara speglarna i början, som sattes ut på samma höjd allihopa och med enklar vinklar på 45 grader. Om det var så små marginaler på dem skulle spegelinställningarna i tre dimensioner bli exponentiellt mycket svårare!

Vilket de också blev. Beräkningarna kunde man kasta i papperskorgen och vårt lags strategi var att köra på empiri, det vill säga testa och sedan göra små ändringar. Sedan kan man göra empiri olika bra ocskå. Säg att du ska gissa ett tal mellan 1 och 100 och får veta om din gissning är mindre eller större än det korrekta talet. Då är det bäst att fråga om talet 50 (eller 51). Om det tänkta talet är större, frågar du om 75 och så vidare. På liknande sätt var det för oss när vi ställde in spegelvinklar (både plattformens vinklar och spegelns vinkling): Börja med en gissning, gå sedan ganska långt åt andra hållet (för att definiera en gissningsintervall), sedan någonstans i mitten om man ser att den korrekta vinkeln är mellan de två gissningar, sedan fokusera på rätt halva av intervallet för att få rätt fjärdedel och så vidare.

Detta funkar bra med småvinkeländringar, eftersom, som jag säger i programmet, ”sinus är linjär vid 0”. Det kommer från att
$\lim_{x\to 0} \dfrac{sin x}{x} = 1$ .

Och då även
$\lim_{x\to 0} \dfrac{tan x}{x} = 1$ .

Om markavståndet (dvs avståndet projicerat ovanifrån) från spegelns mittpunkt till nästa spegel är given, så kommer alltså vinkeln bero linjärt på avståndet i den andra ledden (just det vi försöker gissa). Dubblas vinkeln, så dubblas avståndet alltså.

Så för små vinklar funkar det då med samma genomsökningsstrategi som med talen från 1 till 100. T.ex. testar vi med 5-graders vinkeln, sedan med 7 och om strålen ska vara däremellan testar vi med 6 grader (istället för att vara smarta och försöka beräkna att vi ”borde” testa 6,5 eller nåt sånt). Sånt kan ”inte ens jag” beräkna snabbt utan miniräknare och dessutom är det massa felmarginaler på mätningar, så det hade varit meningslöst ändå.

Vi fick instruktioner om att skriva lite smarta saker på tavlan, speciellt under första omgången. Det finns inte jättemycket att skriva när man kör på empiri annat än små anteckningar, så vi roade oss lite istället:

Så klart fanns det annat att tänka på än att bara höfta och ändra inställningar. En viktig sak är hur många speglar man bestämde sig för att använda (man behövde inte använda alla). Ju färre speglar, desto färre lyckade steg man behövde göra. Men å andra sidan skulle varje steg vara något svårare om man skulle försöka ställa in speglarna i 3D (vi kunde ju inte ställa de var som helst, utan bara på några av hindren). Vi körde på strategin ”better be safe than sorry” och jag blå laget gjorde det också, det vill säga använda många speglar med mindre avstånd/svårighetsgrad mellan varje intilliggande par.

En annan sak som jag kom på och var ganska stolt över var att använda flera av de lediga speglarna att ställa på rad för att chansa på att strålen skulle råka träffa nästa spegel också. Lasern bana var mycket värdefull att se och får man se ett steg till ”gratis” var det mycket värt.

Blå laget körde på att titta i speglarna och försöka se prisman i första spegeln. I programmet är jag skeptisk till hur de kunde låta ögat vara så stabilt, men det funkade ju hyfsat bra för dem. Så kanske är det en hållbar strategi ändå! Problemet är att med många speglar multipliceras felet för varje steg. Tänk på när du är i ett rum med massa speglar. Om du flyttar ögat, flyttar de mer avlägsna spegelbilderna mycket snabbare!

Svår tävling var det och krävde mycket tid och energi. Men det var nog min favorittävling i hela Genikampen. Jag gillar att lösa problem när man har ganska god tid på sig. För varje steg fram man kommer får man en kick och vill fortsätta. Dessutom kan man komma på fler och fler strategier som kan testa och föra en fram bättre och snabbare!

Pentago

Duellen gick ut på att spela några omgångar av spelet Pentago, bäst av tre. Duellanterna fick veta reglerna lite innan och provspela ett par gånger. Det finns ju stor risk för missuppfattning, även när man kommunicerar med oss genier ;) Det vore tråkigt om någon gjorde ett olagligt drag i tv eller nåt, även om det såklart svårt att göra det i just det här spelet.

Som i många spel med ett litet spelplan finns det redan beräknat hur man ska spela optimalt. I det här fallet har första spelaren en vinnande strategi, detta behövde dock beräknas med hjälp av en superdator! I massa andra sådana spel är det bevisat att första spelaren har i alla fall en icke-förlorande strategi, som t.ex. ~~i schack (vit kan aldrig förlora om hen gör rätt!)~~ i ”fem i rad” på ett oändligt bräde, men i många sådana spel finns det så många möjligheter att man inte har räknat ut den konkreta strategin. Pentago är rätt litet så det går att beräkna.

Testa att spela och vinna Pentago

Frågan är om man kan lära sig den vinnande strategin utantill, det har jag ju inte försökt mig på. Även om datorn kan göra det på några sekunder, kanske kan det ta en människa veckor för att ”plugga öppningar”. Det hade inte duellanterna. De hade kunnat fokusera på att plugga hur man ”inte gör fel”, t.ex. att man inte ska lägga i hörnen som första spelare och hur man i så fall ska svara som andra spelare. Men jag tror inte det skulle ha hjälpt för att garanterat vinna. Jag tror man kan jämföra Pentago med Othello: Det tar ett tag att bemästra och att lära sig se mönster, men när man väl gjort det så kan man spöa vilken nybörjare som helst. Det var skönt att duellanterna inte hade spelat spelet förut, så att de tävlade på samma villkor.

Jag och Axel fick senare låna spelet och vi försökte komma fram till en vinnande strategi ”för hand” genom att testa olika möjligheter, men jag tror inte vi hann göra det på en halvtimme :)

Mynten på schackbrädet

Rekommenderad från: 15 år

Du sitter i en fängelsehåla och en vakt kommer till dig med ett erbjudande. Han säger att han kommer lägga upp mynt (totalt 64 st.) på ett schackbräde, ett mynt i varje ruta och det kommer vara slumpat för varje mynt huruvida det ligger med krona eller klave uppåt. Därefter kommer vakten peka på en ruta. Du får sedan en möjlighet att vända upp-och-ner på exakt ett av mynten, vilket du vill.

Därefter kommer en kompis in i rummet, som får se schackbrädet och får gissa vilken ruta vakten pekade på. Gissar han rätt, får ni båda gå fria. Hur kan du och kompisen komma överens om en strategi som garanterar er frihet, oavsett hur vakten gör?

The_Chess_Board

Visa lösningen

För enkelhets skull betecknar vi myntet med 1 om det ligger med krona uppåt och med 0 om det ligger med klave uppåt.

Lösning 1 (Krånglig, men Valentinas egna)

Lösningen visar att det går att konstruera en sådan strategi (och hur man konstruerar), men det är inte självklart hur man ska implementera det direkt. Lösningen använder sig av matematisk induktion.

Först löser vi uppgiften då antalet mynt är två (schackbrädet är tvårutigt). Då kan mynten ligga på fyra sätt från början: 00, 01, 10 eller 11. Vi bestämmer att vi gör om bräder till 0* (det vill säga 00 eller 01) om vakten pekar på det vänstra myntet och till 1* (det vill säga 10 eller 11) om vakten pekar på det högra myntet. Vi kan ju alltid vända vänstra myntet om det visar ”fel” eller vända högra myntet om det vänstra visar ”rätt” redan.

Nu gör vi induktionsövergången från n mynt till 2n mynt. Induktionssteget är alltid likadant, så för förståelsen skull gör jag en konkret övergång från 32 till 64 mynt.

Antag alltså att vi har löst problemet för 32 mynt. Det betyder att vi i varje situation kan vända på ett av mynten så att kompisen förstår vilket av de 32 mynten vakten pekade på genom att bara titta på slutpositionen. Vi antar även att varje slutposition (av 2^32) i sin tur betyder att en viss speciell ruta blev pekad på. Så är ju fallet för 2 mynt. Det betyder att vi från varje startposition på 32 mynt kan göra om brädet så att slututseende har ett visst ”värde” (från 1 till 32).

Antag att vakten pekar på ett mynt med ett nummer som ger rest r vid division med 32. Till exempel, om resten är 3 så pekade vakten på mynt nummer 3 eller nummer 35. Då kan vi ändra brädet på två möjliga sätt så att summan av numren som de två halvorna betyder (i 32-systemet) också ger rest r vid division med 32. Det beror på att vi kan fixa vilken rest vi vill i en av halvorna enligt induktionsantagandet. På så vis kan kompisen (som även kan systemet för 32 mynt) lista ut att myntet vakten pekade på var nummer 3 eller 35 (genom att räkna ”summan” av brädhalvornas värden). Men hur ska hen avgöra vilket av de två alternativen gäller i 64-systemet?

För detta använder vi lösningen för 2 mynt. Vi kan räkna antalet kronor (uppåt) i varje brädhalva. Är det ett jämnt antal i båda halvorna betecknar vi brädet 00. Är det jämnt antal kronor i första halvan och ett udda antal i andra, så betecknar vi brädet 01 och så vidare.

Genom att vända upp-och-ner på ett av mynten kommer vi garanterat förändra en av siffrorna. Låt oss då bestämma att vi vänder så att det blir 00 eller 01 (vi kan bestämma i vilken halva vi vänder) utifall kompisen ska säga det lägre alternativet (3 i vårt exempel) och vi vänder så att det blir 10 eller 11 ifall kompisen ska säga det högre alternativet (35 i vårt exempel). Detta kan vi alltid på samma sätt som i lösningen för två rutor!

Det betyder att kompisen kan med säkerhet bestämma vilket mynt som vakten pekade på.

Lösning 2 (Snygg och praktisk, min vän Mikkes lösning)

Här är instruktionerna för hur kompisen listar ut vilket mynt vakten pekade på:

Först kollar du om det finns ett udda antal 1:or (dvs kronor uppåt) i det gröna området. Om det gör det — då letar du efter rutan i det gröna området, annars (om antalet 1:or är jämnt i det gröna) letar du efter rutan i det vita området. Lägg det stora området på minnet.

1_8x8

Nu kollar du om det finns ett udda antal 1:or (dvs kronor uppåt) i det nya gröna området. Om det gör det — då letar du efter rutan i det gröna området, annars letar du efter rutan i det vita området. Lägg det andra stora området på minnet (redan nu vet du i vilken ”fjärdedel” myntet bör ligga).

2_8x8

Gör på samma sätt med resterande gröna områden:

För varje nytt halvgrönt bräde (som du föreställer dig i huvudet) halverar du antalet möjliga svar. Efter sex bräden har du kommit fram ett enda möjliga myntet och det kommer vara myntet som vakten pekade på!

Varför är det då möjligt för dig att fixa myntvädningen så att kompisen kan lista ut det utpekade myntet? Du kan också föreställa dig de halvgröna bräden en i taget och se ifall kompisen kommer komma rätt. Är det så att det utpekade myntet ligger i det gröna området? Då ska du fixa så att det ligger ett udda antal 1:or i det gröna området. Antingen genom att vända i den vita halvan ifall det redan är udda i grönt eller vända i den gröna halvan ifall det är jämnt antal 1:or i grönt. Är det så att det utpekade myntet ligger i det vita området? Då fixar du så att det är ett jämnt antal 1:or i den gröna halvan.

Det här liknar alltså sista biten i Lösning 1.

På samma sätt gör du med de andra fem halvgröna bräden. Detta ger dig exakt ett bestämt mynt som du måste vända på för att fixa de korrekta pariteterna (jämn/udda precis där det behövs)!

Lösning 3 (För datavetare)

Detta är detsamma som Lösning 2, men på datorspråk. Varje myntnummer är ett binärt tal mellan 000000 och 111111 (6 bitar). Skriv upp alla tal vars mynt har krona uppåt. Gör operationen XOR på alla de mynten (med andra ord, kolla pariteten på antalet 1:or på varje bit). Gör XOR på det resultatet och numret på myntet som vakten pekade på. Detta ger numret på myntet som du ska vända på!

Din kompis listar ut resultat på samma sätt, genom att XOR:a alla ettor (kronor uppåt) som hen ser.

Spionuppdrag

Rekommenderad från: 12 år

En hemlig byggnad består av många rum som ser exakt likadana ut och som är kopplade i en stor ring med små korridorer. I varje rum finns en lampa och en lampknapp. En spion hamnade i ett av rummen. Hur ska han bestämma antalet rum i byggnaden om han bara kan gå runt och tända och släcka ljuset? Från början lyser det i vissa rum, men spionen vet inte på förhand i vilka.

lampor

Visa lösningen

Hur man klarar 2048-spelet

Om du inte redan har sett 2048-pusslet, som blivit stort online, så kan du testa att spela det på http://gabrielecirulli.github.io/2048 Det går ut på att kombinera ihop tvåpotenser (från början 2:or och 4:or) så att det bildas 2048.

Varning: Spelet är mycket beroendeframkallande!

Det tog mig några timmar att klara spelet, i början ”dör” man på tal som 256, 512 och i bästa fall 1024. Hur är det möjligt att klara spelet? Hur ska man göra för att komma vidare efter 2048 och inte ”dö” direkt?

Roligast är det om man kommer på strategierna själv, men om du känner dig fast efter några omgångar, så kan du ta del av följande tips. (Det finns såklart andra sätt att klara spelet, detta är bara vad jag kommit fram till.)

Välj ett hörn

Från början kan man bestämma ett hört, exempelvis högra-nedre hörnet där man samlar ihop sina tal. Det går att komma ganska högt genom att bara trycka ”höger” och ”neråt” varannan gång eller på måfå. Typiskt ser det ut så här när man inte längre kan göra något av de två dragen.

start

På grund av spelets regler kommer ditt största tal befinna sig i just det hörnet. Det allra bästa tipset jag kan ge i det här spelet är att du till allt pris behåller ditt största tal i det hörnet hela spelet igenom.

Justera tredje raden

För att uppnå höga resultat, se alltid till att ha full nedre rad och justera den tredje raden för att öka talen i den fjärde raden. Justering vänster-höger tills det passar på vertikal led är en viktig teknik i spelet.

Ordna potenserna på en rad

Det går att komma ganska långt med att trycka på ”höger” och ”neråt” hela tiden. Strategin för att samla ihop till ett stort tal i ett hörn är att ha som mål att ordna tvåpotenserna på nedre raden i följd. Till exempel vill du ha 64, 128, 256, 512 på nedre raden innan du bygger ihop till 1024.

ordna

Ordna mindre potenser på tredje raden

När du har fått 128, 256, 512, 1024 på nedersta raden, försök att uppnå 64, 32, 16, 8 på tredje raden (just det, i omvänd ordning!). Tal på tredje raden får man till genom att justera den andra raden.

en_rad_klar

Sätt ihop till 2048

Voila! Gör du en 8 till och sätter ihop med 16, 32, 64, 128, 256, 512 och 1024 i ordning, så får du 2048! I hörnet dessutom!

snart

Nu när du klarat spelet kan du ändå fortsätta spela. Samma tekniker funkar ett tag till, men så småningom gör man fel och behöver flytta på sista raden, vilket kan resultera i att 2048 inte är i hörnet längre. Då är mitt bästa tips att låta det hörnet vara, strunta i det fullständigt det vill säga!

Jag har kommit ganska långt men inte fått 4096 än. Har du några tips?

rekord

Bonus: om du inte gillar siffror, men gillar doge-bilder, finns det en rolig bildversion av spelet.

Om du förstår algoritmer bättre i action så kan du inspireras av ett AI som löser pusslet.

Update: Strategierna räckte för att klara 4096!

4096

Update++: Efter 3 veckor med spelet, äntligen:

8912

Spelet tog slut strax efteråt, med uppnått resultat med 106520 poäng. Känner mig klar med detta spel!

8912_game_over

Tre påsar med mynt

Rekommenderad från: 13 år

[kkratings]

Du har tre påsar med hundra mynt i varje. I en av påsarna väger alla mynten 9,9g, i en annan väger alla 10g och en tredje väger alla 10,1g, men du vet inte vilka mynt som ligger i vilken påse. Du har även en våg som kan visa den exakta vikten, men går sönder om du lägger på mer än 50g på den. Hur kan du med en vägning bestämma vilka sorts mynt ligger i varje påse?

myntpåse

Visa lösningen

Centauren

[kkratings]

Två spelare spelar på ett oregelbundet rutigt bräde. De turas om att flytta pjäsen Centauren, som kan flyttas antingen en ruta åt vänster, en ruta uppåt eller en ruta uppåt-höger på ett drag.

Spelaren som inte kan flytta pjäsen på sitt drag förlorar spelet. Vem har en optimal strategi: första spelaren (som börjar) eller andra spelaren?

Visa lösningen

HMT-final 2012 och föredraget om spel

Lördagen den 21 januari var en spännande dag för ca 45 högstadieelever. De tävlade nämligen i junior-sm i matte, det vill säga finalen i Högstadiets Matematiktävling!

Vinnaren blev precis som förra året Lisa Lokteva från Borås, denna gång på en odelad 1:a plats!

Lisa och Valentina — Jag och vinnaren av HMT 2012

Jag är extra stolt, eftersom Lisa har övat lite genom att lösa problemen på mattebloggen. Det har också Toomas Liiv gjort och han kom på delad 6:e plats i år! Grattis till de båda!

Jag var med och rättade problemet om cirklar och olika färger. Tyvärr såg bilden väldigt symmetrisk ut och några deltagare antog att delarna med samma färg hade samma area, men så var det inte nödvändigtvis (problemets text sade inget om saken). Men det var många som löste uppgiften rätt, det vill säga oberoende av de olika färgade områdens form och storlek.

Sedan var det dags för mig att hålla ett föredrag i aulan. Jag valde att prata om lösningstekniken ”att sno strategi” som fungerar i vissa sorts spel. Vissa problem hann jag inte prata om utförligt och du kan ladda ner föredraget och titta på det i lugn och ro.

Det handlar om att bevisa att man kan vinna eller spela oavgjort ett spel där man egentligen inte har någon aning om den optimala strategin. Precis som amatörkvinnan som kunde spela remi mot två förstaklassiga schackspelare (du kan börja kolla från 2:30):

Triell

[kkratings]

A, B och C deltar i en triangelduell med pistoler. Alla vet att A träffar med sannolikheten 0,3. Sannolikheten att C träffar är 0,5, medan B missar aldrig. Deltagarna skjuter en i taget mot en vald person (de skadade får inte längre vara med) tills det bara är en person kvar.

Vad ska A ha för strategi (han börjar skjuta, sedan kommer B respektive C i turordningen)?

Visa lösningen

Spel på en remsa

Rekommenderad från: 15 år

[kkratings]

Det finns en rutig remsa 1xn:

remsa

Anders och Filip spelar ett spel. De turas om att göra drag: Anders får sätta ett kryss i en tom ruta och Filip får sätta en ring i en tom ruta. Dock får inte två kryss hamna bredvid varandra och inte heller två ringar. Spelaren, som inte kan göra ett drag när det är hans tur, förlorar.

Anders gör det första draget. Vem har ett vinnarstrategi, det vill säga vem kan alltid vinna oavsett hur motståndaren spelar?

Observera att svaret kan bero på talen n, som säger hur lång remsan är.

Visa lösningen

För det första är n=1 ett specialfall. Det finns bara ett sätt som spelet kan gå till på, nämligen att Anders sätter kryss och Filip kan inte göra något drag längre och därför förlorar.

Men för alla andra storlekar på remsan så vinner Filip. Det roliga är att hans första drag måste vara speciellt, men efteråt kan han spela hur som helst så länge hans drag är tillåtna och ändå alltid vinna, oavsett hur Anders spelar.

Anders börjar med att sätta kryss någonstans. Det kan vara på remsans ände eller så kan det vara någonstans däremellan. I vilket fall som helst kan Filip sätta ring i en av remsans ändrutor:

lv20 eller

lv20_2 De fortsätter spela under tillåtna regler (aldrig två kryss eller två ringar bredvid varandra). Låt oss säga nu att Filip på något sätt lyckas förlora. Det betyder att han i en viss situation har ingenstans att sätta sin ring och de har precis varit Anders tur.

Eftersom Anders började och det precis har varit hans tur, så har han gjort ett fler drag än Filip, det vill säga det finns ett fler kryss än ringar på remsan.

Men notera att i den här situationen måste två utsatta kryss ha en ring mellan dem. För att två kryss kan inte vara bredvid varandra, och hade det bara funnits tomma rutor mellan dem, så skulle Filip ha haft ett möjligt drag.

Alltså finns det minst en ring mellan varje par av kryss. Om vi börjar räkna upp symboler från kanten där Filip gjorde sitt första drag (första ringen) kommer vi se: ring, kanske fler ringar, kryss, ringar, kryss, ringar, kryss, … , slutar med kryss eller ring. (Här betyder ”ringar” att det kan vara exakt en ring också). Schematiskt exempel: OXOOOXOOXOOOXOOOXOOX.

Men då ser vi att varje kryss har minst en ring strax till vänster om sig. Det betyder att antalet kryss kan i den här situationen inte vara fler än antalet ringar. Vårt antagande om att Filip inte kunde göra drag var fel, därmen kommer Filip alltid att kunna göra drag efter att Anders har gjort sitt. Alltså är det Anders som först inte kommer kunna göra drag och förlorar för n>1.

Pyramiden

Bombdesarmeringen

Pusselduellen

Flottbygge: Planering och materielinköp

Flottbygge: Första omgången

Flottbygge: Andra omgången

Laser och speglar

Pentago

Rekommenderad från: 15 år

Lösning 1 (Krånglig, men Valentinas egna)

Lösning 2 (Snygg och praktisk, min vän Mikkes lösning)

Lösning 3 (För datavetare)

Vill du få extrainfo om problemlösning via e-post från Mattebloggen?

Rekommenderad från: 12 år

Vill du få extrainfo om problemlösning via e-post från Mattebloggen?

Välj ett hörn

Justera tredje raden

Ordna potenserna på en rad

Ordna mindre potenser på tredje raden

Sätt ihop till 2048

Rekommenderad från: 13 år

Triell

Rekommenderad från: 15 år