Monday, 14 September 2009

A problem for real engineers

On the first of september 100 immortal prisoners with a life sentence are suggested an early release if they can find a solution to a problem.

 There's a room with a hanging lightbulb. Every day, starting on the 1st of September, warder will let one prisoner into this room. When prisoner is in, he can see, whether lamp is on or off, or switch it. Each prisoner will be asked a question: "Whether every prisoner has been here?". If he says "no", game goes one. If he says yes and this is a correct answer, everyone is released. If he says yes and he's wrong - everyone is executed.

 Warders can choose prisoners randomly, one prisoner can be choose as many times as warder wants. Prisoners do not see each other, cannot talk and cannot see the lightbulb; they can talk only once - on the 1st of September, before the game starts.

 Find an optimal strategy, estimate, how long it may take for prisoners to be released.