Plan to Escape?
Written on 11:49 pm by Vja Students
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?
Answere
One person is chosen as the Counter. When a prisoner enters the living room, if the light is off they turn it on - but only if they have never switched it on before. When the Counter enters the room, if the light is on, they will turn it off. When the Counter has turned the light off 99 times, they will know that 99 prisoners have turned it on, and therefore every one of them has visited the living room and this will allow them all to be set free. QED.
