Originally posted by vicki
Another one to keep the brain juices flowing 
100 prisoners are locked up in prison. Each prisoner in his own cell. They cannot communicate with each other, except for the one afternoon when they all arrived in prison.
Every day, the warden picks one prisoner at random and brings him to a
room with a lightbulb and a lightswitch. The lightbulb is in whatever
state it was left the day before. The prisoner can now choose from 3
things:
1) he leaves things as it is
2) he toggles the lightswitch
3) he states that all 100 prisoners have been in this room at least
once.
After option 1 or 2, the prisoner is brought back to his cell. If the
prisoner decided to go for option 3, but he is wrong, they are all
executed. If he is right, they all go free.
Given that the prisoners are aware of this evil game that the warden is
going to play with them, what is the strategy they should decide on the
day they arrived in prison, when they could still talk to each other?
Assume the prisoners know the bulb is initially at the off position.
Note: random means random. It may happen that the same prisoner is
chosen 2, 3, or more days in a row.
100 prisoners are locked up in prison. Each prisoner in his own cell. They cannot communicate with each other, except for the one afternoon when they all arrived in prison.
Every day, the warden picks one prisoner at random and brings him to a
room with a lightbulb and a lightswitch. The lightbulb is in whatever
state it was left the day before. The prisoner can now choose from 3
things:
1) he leaves things as it is
2) he toggles the lightswitch
3) he states that all 100 prisoners have been in this room at least
once.
After option 1 or 2, the prisoner is brought back to his cell. If the
prisoner decided to go for option 3, but he is wrong, they are all
executed. If he is right, they all go free.
Given that the prisoners are aware of this evil game that the warden is
going to play with them, what is the strategy they should decide on the
day they arrived in prison, when they could still talk to each other?
Assume the prisoners know the bulb is initially at the off position.
Note: random means random. It may happen that the same prisoner is
chosen 2, 3, or more days in a row.
Day 1, decide on one prisoner to be the record keeper.....
When a prisoner comes into the room, if the light is OFF and he has never switched the light on before, he switches it on.
Whenever the record keepign prisoner comes into a lit room, he flips it off and adds to his mental count.
When he has flicked the switch off his 99th time, he knows they have all been in the room
Comment