Det fina med dehär nötterna är att det inte nödvändigtvis finns bara ett rätt svar, snarare bättre och sämre lösningar. Så trots att man snabbt kommer på ett svar, kan det hända att det går att modifiera till en ännu effektivare lösning!
Nöt 1:
En båt har blivit kapad. De 21 passagerarna sätts alla i varsin hytt. De har en chans att bli frisläppta, annars sitter de inlåsta till det bittra slutet.
Det finns ett rum i båten med två stycken lampor. Vardera lampa kan vara antingen släckt eller tänd, oberoende av varandra.
Varje enskild gisslan kommer att få gå in i rummet, där han är fri att påverka eller låta bli att påverka lamporna hur mycket och hur lite som helst. Den enskilda gisslan vet inte hur många som varit i rummet före honom, och han får inte lämna några andra synliga märken efter sig i rummet. De har inte möjlighet att kommunicera sinsemellan på något annat sätt än genom lamporna.
Fångarna tas inte in i rummet i någon särskild ordning eller något visst antal gånger, dvs fånge nr 1 kan gå in tio gånger innan fånge nr 13 går in första gången. Tiden mellan varje enskilt besök i rummet varierar också slumpmässigt. Lamporna kan tändas och släckas hur många gånger som helst och brinner aldrig ut.
Om en av gisslan korrekt kan bestämma när alla har varit inne i rummet åtminstone en gång, får alla gå fria. De ges endast en chans att gissa, men det finns ingen tidsbegränsning eller begränsning på hur många gånger en fånge får gå in i rummet.
Gisslan får träffas en gång innan utmaningen börjar för att komma överens om sin taktik. Hurdan taktik skall de ha för att bli frisläppta?
Nöt 2:
En kung skall ha fest, och har köpt in tusen flaskor vin. Till sin förfäran får han veta dagen innan (24h innan festen börjar) att en av flaskorna är förgiftade. Dessutom vet han att giftet tar kål på den som smakar på vinet inom 10-20 h efter att man druckit. Nu måste han ju hitta den förgiftade flaskan!
Som tur har han till sitt förfogande hundra slavar, som offrar sig genom att smaka på vinet om kungen så ber. Kungen tror dock att de som väljs ut för smakproven mister lite förtroende för kungen, så han vill helst utsätta så få slavar som möjligt för faran. Hur skall han göra?
(Om du löst den gåtan, försök då med att omskriva den så att kungen är rädd för att han skall förlora för stor del av sin arbetskraft, så han borde hitta den förgiftade flaskan med det minsta antalet döda fångar.)
Fråga om något blev oklart. Lycka till!
Kommentarer (12)
I nöt 1 är vi ju intresserade av om en av gisslan varit inne i rummet eller inte, och inte så av hur många gånger en fånge varit inne i rummet. Därmed är det i allmänhet en bra ide att en fånge endast påverkar en lampa en gång, första gången han är inne, och efter det låter bli lamporna.
I nöt 2 finns det som sagt två olika infallsvinklar, beroende på om man vill minimera antalet inblandade fångar eller antalet fångar som möjligen dör.
För att lösa det första problemet lönar det sig att bekanta sig med det binära talsystemet.
Det andra problemet löser säkert lättast med gammal god kombinatorik.
Wikipedia är ofta ett säkert kort, då man vill uppfriska sin kunskaper i matta;)
2b. Kungen placerar vinflaskorna i en 32x32 matris (i den sista raden blir det bara 8 flaskor i stället för 32 men det gör inget). Han tvingar därefter 62 slavar att smaka på vinet enligt följande: 31 slavar smakar på kolumnerna och 31 slavar smakar på raderna. En rad och en kolumn lämnas osmakade, detta innebär alltså att det igen finns en flaska som ingen smakar på. Jag menar alltså att en slav smakar på en rad om han smakar på alla flaskor i en viss rad, samma sak gäller för kolumnerna. Om två slavar dör så vet man att flaskan finns på radslavens rad och i kolumnslavens kolumn. Om bara en slav dör så vet man att flaskan finns i den döde slavens rad (eller kolumn) och i den osmakade kolumnen (eller raden). Om ingen dör så vet man att det är flaskan som är både i den osmakade kolumnen och i den osmakade raden. Denna lösning kräver alltså att 62 slavar deltar och i värsta fall (vilket är ganska troligt) så dör två av dessa. Om man vill öka lite på sannolikheten att mindre än två slavar dör så kan man ändra lite på matrisstorleken så att man använder sig av alla 100 slavarna, t.ex. kunde man använda sig av en 11x91 matris i stället.
Den stora nackdelen med bägge lösningarna är ju att kungen kommer att ha 999 öppnade vinflaskor och endast en oöppnad flaska. Jag kan i.a.f. inte komma på något sätt att säkert hitta giftflaskan utan att öppna minst 999 flaskor.
Själv är jag inte så bra på binärtal, så jag räknade ut det med vanlig kombinatorik, i b-fallet som så att alla först smakar på varsin flaska, vilket innebär att det finns 900 kvar, och då kan man räkna ut att ”43 över 2” är 903 (man kan alltså göra kombinationer med 2 stycken på 903 olika sätt av 43 slavar). Men jag tänkte inte på att man kan lämna en flaska helt osmakad, och matrisen beskriver lösningen på ett vackrare sätt.
Problemen med 999 öppnade flaskor samt etanolförgiftningen var ju spännande synpunkter, men inget vår kung oroar sig över i dethär fallet. :)
Finns det ännu något förslag på nöt 1?
T.ex. vore det roligt att veta om alla i gisslan har en personlig gissning eller om de bara har en tillsammans, vem som tar initiativ till gissandet, om det går att skilja lamporna åt, om man vet hur lamporna är ställda i början, om man kan anta att efter tillräckligt lång tid så har en godtycklig medlem av gisslan varit N gånger inne i rummet och om någon i gisslan t.ex. har bråttom till bussen ;-)
Lamporna går att skilja åt.
Gisslan vet hur lamporna är ställda i början.
Fördelningen av antal besök per fånge efter en lång tid påverkar väl inte lösningen i sig, utan snarare hur snabbt de kommer ut? I den ursprungliga nöten sades det ingenting om fördelningen, men kanske vi kan anta att den är likformig.
Samtliga fångar har brottom till bussen och otroligt rädda om sitt eget och sina vänners liv;-)
Lamporna kan alltså vara i fyra olika lägen:
läge 0, då bägge lamporna är i ursprungsläge
läge 1, då bara lampa A har ändrats
läge 2, då bara lampa B har ändrats
läge 3, då bägge lamporna har ändrats
20 personer utses till adderare och de skall agera enligt följande:
Om [och endast om] lamporna är i något av lägena 0, 1 eller 2 och adderaren inte har ändrat på lamporna tidigare, så skall han manipulera dem så att de flyttas fram ett steg i tabellen ovan. Varje adderare skall alltså bara ändra på lamporna en gång. Ingen av personerna i denna grupp får försöka sig på att gissa.
En person utses till nollställare. Nollställaren skall manipulera lamporna endast om de befinner sig i läge 3, då skall han återställa dem till läge 0. Han skall hålla reda på hur många gånger han nollställer lamporna. Lamporna skall nollställas 6 gånger. När han har nollställt lamporna 6 gånger skall han invänta att lamporna intar läge 2, då vet han att alla de andra har varit inne i rummet minst en gång och kan därför använda den enda gissningen.
Finns också versioner av den här nöten, där den som besöker rummet MÅSTE påverka lamporna, men det blir inte någon svårare lösning, bara sannolikt längre tid före de hinner till sin arma buss.
Tack Viktor, och alla andra, som tog sig tid att fundera!
Nya nötter, eller andra klurigheter mottages med tacksamhet!
mera gospel! :)
Skriv en kommentar