De hundre fangene og lyspæra

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
KjetilEn
Dirichlet
Dirichlet
Innlegg: 191
Registrert: 28/02-2007 17:30
Sted: Oslo

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!
Those who know a lot, don't know more about how much they know than those who know less.
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Har løst denne før. Det interessante med denne er egentlig ikke svaret men et spørsmål til svaret.
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

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.
KjetilEn
Dirichlet
Dirichlet
Innlegg: 191
Registrert: 28/02-2007 17:30
Sted: Oslo

Helt riktig sEirik. Da skal vel Magnus få lov å komme til med tilleggsspørsmålet sitt :wink:
Those who know a lot, don't know more about how much they know than those who know less.
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Hva er forventet tid til "lyskapteinen" kan si med sikkerhet at alle har vært der?
mrcreosote
Guru
Guru
Innlegg: 1995
Registrert: 10/10-2006 20:58

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!
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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.
Svar