A problem for real engineers

comments6 comments    usersigizmund

September 14th, 2009 

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.

Posted in: Uncategorized



This website uses IntenseDebate comments, but they are not currently loaded because either your browser doesn't support JavaScript, or they didn't load fast enough.

6 Comments

rssComments RSS transmitTrackBack Identifier URI


Prison repr. turns light off.Each of the others toggles it on just once.If light on whn repr. back,add +1 to num of prisoners.

Comment by Siddhu Warrier on September 15, 2009 10:12 am


I assume prisoners can talk to each other to elect/select a leader before the thing starts.

Comment by Siddhu Warrier on September 15, 2009 10:13 am


Yep, that’s a correct answer :)

Comment by Roman Kirillov on September 15, 2009 10:15 am


How long will it take? Too f*ckin long! ;)

Comment by Siddhu Warrier on September 15, 2009 10:19 am


They’re immortal – and all serve their life sentences, so don’t think they care as long as it’ll get them out eventually!

Comment by Roman Kirillov on September 15, 2009 10:21 am


Well I guess you could calc the time by assumin a uniform distrib of call freq to the leader,n using Bayesian inference.But cant be bothered.

Comment by Siddhu Warrier on September 15, 2009 11:52 am

addLeave a comment