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?
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.
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).
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.