Hi Friends,

100 prisoners are locked up in individual cells, unable to see, speak or communicate in any way with each other.

There is a central living room with a single light bulb, the bulb is initially off and no prisoner can see the light bulb from their own cell.

Every day, the warden picks a prisoner at random, and that prisoner goes to the central living room.

While there, the prisoner can toggle the bulb if they wish (off to on, or on to off).

At any point, any prisoner can claim that all 100 prisoners have been to the living room. If they are wrong then all 100 prisoners will locked up forever! However, if they are correct all of the prisoners are set free.


Before the random picking begins, the prisoners are allowed to discuss a plan.

Then guys.......

The Question........

What is their best plan to determine when all 100 prisoners have visited the living room?

Thanks,
Riju

A sufficient condition for all of the 100 prisoners having been to the CLR would be that 100 days go by without any prisoner having been there twice. This results in the following plan for a prisoner visiting the CLR:
- If the light is off, turn it on and start counting the days, this day being day zero.
- If the light is on, and your counter is 0, start counting the days, this day being day zero.
- If the light is on, and your counter is greater than zero, but < 100, turn the light off and stop counting days.
- If the light is on, and your counter is 100: inform warden that the liberating condition has been met!
- If the light is on, and your counter is >100, reset the counter to 0, but keep counting.

On a day where you don't visit CRL and are counting days, then increment the counter.

For a truly random selection sequence of prisoners, chances for success are extremely small!