100 prisoners and a light bulb

697 Views Asked by At

I'm curious if there is a solution,however ineffective, for the puzzle when the prisoners do not know whether initially the bulb is on or off.

Second, has several bulbs modification of the problem been studied? Where, if yes? There may be for instance two bulbs and prisoners are either randomly or regularly put into one of the two rooms each time, this fact being known to them in advance. Does this modification increase or decrease the average time? I believe that in the case of regularly, then the average time for being them free will decrease, since they can encode more information into two bulbs.

1

There are 1 best solutions below

7
On

I'm curious if there is a solution,however ineffective, for the puzzle when the prisoners do not know whether initially the bulb is on or off.

Assuming that it is known on which day the first prisoner is sent into the room, it is indeed possible: The first prisoner to be sent into the room is chosen as the counter (everyone knows if he was in the room on day one), and if at day one he finds the light on, he switches it off without counting, because he knows that nobody has yet been in the room. After that, the protocol goes on the same way as in the original problem.

If the starting day is not known, the following variation works: Each of the $99$ non-counters is asked to switch the light on two times. If only $98$ of the non-counters have switched the light on twice, the total count is at most $197$ ($196$ switch-ons from the $98$ prisoners, and $1$ count from the initial-on lamp). Thus if the count reaches $198$, then either the lamp was initially off and all non-counters have switched on the light twice, or the lamp was initially on, at least $98$ prisoners have switched the light on twice and the $99$th at least once. In any case, all prisoners have been in the room.