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!
De hundre fangene og lyspæra
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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.
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.
-
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Sannsynligvis lenger tid enn ei lyspære kan holde.Magnus skrev:Hva er forventet tid til "lyskapteinen" kan si med sikkerhet at alle har vært der?
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.
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.