En smule inspirert av slashdot sin tråd om kreative fremgangsmåter for Hello World kommer det en utfordring av et helt annet kaliber. Jeg har ikke skrevet denne selv og det er fullt mulig å finne svar på det matematiske problemet om man har litt google-skills (det får dog være en oppgave for hver enkelt). Jeg vil også oppfordre folk til å diskutere løsningsforslag for å hjelpe hverandre.
Oppgaven er som følger:
Oppgaven er altså todelt:
1. Finn en strategi som gjør at det er minst 30% sannsynlighet for
at de blir benådet. (Optimal strategi gir litt over 31% eller så; det er
matematisk veldig utfordrende å faktisk regne ut sannsynligheten, så det er
ikke en del av oppgaven. Det holder å gi riktig strategi, så kan man alltids
simulere den for å vise at det faktisk blir over 30% etterpå.)
2. Implementer denne i selvvalgt programmeringsspråk.
(ps: Dette er ikke et "lurespørsmål", ordlyden i oppgaven har ingen betydning, fangene kan ikke rotte seg sammen for å overmanne vaktene etc. Det er beint frem et problem med en løsning som er vanskelig å finne.)
Jeg gir dere en uke til å tenke over/diskutere problemstillingen før jeg poster en forklaring til hjelp i implementeringen.
Oppgaven er som følger:
Hundre fanger (nummerert 1 til 100) er dømt til døden, men får en sjanse til
benådning. En etter en sendes de inn i et rom, der det er hundre like bokser
(også nummerert 1 til 100). I hver av boksene ligger det en lapp med et tall
fra 1 til 100 på (inklusive, hvert tall brukes en gang). Lappene er helt
tilfeldig fordelt ut mellom boksene.
Hver fange kan bruke så lang tid han/hun vil der inne, men ikke åpne mer enn
femti bokser. Målet er å finne «sin egen» lapp, altså lappen som har samme
nummer som sitt eget fangenummer, på maksimalt femti forsøk (åpning av
bokser, altså). Hvis _alle_ hundre klarer dette, benådes de, mens hvis så mye
som én feiler, skytes hele bunten. (Fangevokterne er alltid ganske diabolske
i sånne oppgaver...)
Nå til det som gjør oppgaven vanskelig: Så fort førstemann har gått inn i
rommet, er det absolutt ingen kommunikasjon, hverken implisitt eller
eksplisitt, mellom noen av fangene. Med andre ord, så fort man har funnet sin
lapp går man ut av rommet og snakker ikke med noen av de andre, og rommet
settes tilbake til den tilstanden det var i (alle bokser lukkes igjen, evt.
lapper som er tatt ut legges tilbake igjen, evt. skribling på veggen vaskes
bort, osv.). Du kan med andre ord ikke bruke ting som «første fange var der
i 14 minutter om han fant lappen sin i boks nummer 14» eller tilsvarende.
benådning. En etter en sendes de inn i et rom, der det er hundre like bokser
(også nummerert 1 til 100). I hver av boksene ligger det en lapp med et tall
fra 1 til 100 på (inklusive, hvert tall brukes en gang). Lappene er helt
tilfeldig fordelt ut mellom boksene.
Hver fange kan bruke så lang tid han/hun vil der inne, men ikke åpne mer enn
femti bokser. Målet er å finne «sin egen» lapp, altså lappen som har samme
nummer som sitt eget fangenummer, på maksimalt femti forsøk (åpning av
bokser, altså). Hvis _alle_ hundre klarer dette, benådes de, mens hvis så mye
som én feiler, skytes hele bunten. (Fangevokterne er alltid ganske diabolske
i sånne oppgaver...)
Nå til det som gjør oppgaven vanskelig: Så fort førstemann har gått inn i
rommet, er det absolutt ingen kommunikasjon, hverken implisitt eller
eksplisitt, mellom noen av fangene. Med andre ord, så fort man har funnet sin
lapp går man ut av rommet og snakker ikke med noen av de andre, og rommet
settes tilbake til den tilstanden det var i (alle bokser lukkes igjen, evt.
lapper som er tatt ut legges tilbake igjen, evt. skribling på veggen vaskes
bort, osv.). Du kan med andre ord ikke bruke ting som «første fange var der
i 14 minutter om han fant lappen sin i boks nummer 14» eller tilsvarende.
Vis hele sitatet...
1. Finn en strategi som gjør at det er minst 30% sannsynlighet for
at de blir benådet. (Optimal strategi gir litt over 31% eller så; det er
matematisk veldig utfordrende å faktisk regne ut sannsynligheten, så det er
ikke en del av oppgaven. Det holder å gi riktig strategi, så kan man alltids
simulere den for å vise at det faktisk blir over 30% etterpå.)
2. Implementer denne i selvvalgt programmeringsspråk.
(ps: Dette er ikke et "lurespørsmål", ordlyden i oppgaven har ingen betydning, fangene kan ikke rotte seg sammen for å overmanne vaktene etc. Det er beint frem et problem med en løsning som er vanskelig å finne.)
Jeg gir dere en uke til å tenke over/diskutere problemstillingen før jeg poster en forklaring til hjelp i implementeringen.