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.