matematikk.net

Kom over en liten nøtt jeg fikk på forkurs i matte.

De hundre fangene og lyspæra

100 fanger sitter i hver sin isolerte celle, uten mulighet til å se eller høre noen utenfor cellen. I et eget rom i fengselet er det en lyspære som opprinnelig er slått av. Hver dag velger fangevokteren tilfeldig ut en av fangene, og sender ham inn i rommet med lyspæra. Der inne kan fangen slå lyset av eller på, eller la det være som da han kom. Ingen andre enn fangene endrer noen gang på lyspæra. Når fangen kommer ut fra rommet kan han si til fangevokteren: "Nå har alle de hundre fangene vært inne i rommet med lyspæra". Hvis han har rett, slipper alle fangene fri. Hvis han derimot tar feil, blir alle hengt. Påstanden om at alle har vært inne i rommet må derfor kun sies dersom fangen er 100% sikker i sin sak.

Før de blir satt i cellene sine, får fangene bruke en kveld til å rådslå. Kan du foreslå en strategi de blir enige om slik at det er mulig for en av fangene en dag å væra sikker på at alle har vært inne i rommet?



Hvis du har sett den før, la noen andre bryne seg på den først!

Har løst denne før. Det interessante med denne er egentlig ikke svaret men et spørsmål til svaret.

Her er en mulig, men noe langtrekkelig måte å gjøre det på:

De utnevner en person til lyskaptein.
Når en annen fange enn lyskapteinen kommer inn i rommet, og ser at lyspæra er på, skal den være forlatt på. Dersom lyspæra er av, skal den skrus på. Men hver fange skal bare skru på lyspæra hvis denne fangen ikke har skrudd på lyspæra før en gang.
Når lyskapteinen kommer inn i rommet, skal han la lyspæra være av hvis den stod av. Hvis den derimot er på, skal han notere seg dette, og så slå den av.
Når lyskapteinen har notert seg 99 antall tilfeller av påslåtte lyspærer, er han sikker på at alle har vært innom rommet.

Helt riktig sEirik. Da skal vel Magnus få lov å komme til med tilleggsspørsmålet sitt

Hva er forventet tid til "lyskapteinen" kan si med sikkerhet at alle har vært der?

Magnus skrev:Hva er forventet tid til "lyskapteinen" kan si med sikkerhet at alle har vært der?

Sannsynligvis lenger tid enn ei lyspære kan holde.

Fin oppgave!

Jeg fant et interessant paper som tar for seg Magnus' spørsmål:

Paul-Olivier Dehaye, Daniel Ford, Henry Segerman - One hundred prisoners and a lightbulb

Med Eiriks strategi er forventningsverdien ca 29 år - men det finnes en bedre strategi.