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. What is their best plan to determine when all 100 prisoners have visited the living room?

 [Ref: ZAWX]

Design © Kevin Stone 2009 | About | Contact | RSS | Links | Disclaimer | Postcards | Use Material