> once the leader has seen the light be on a sufficient number of times he can definitively say that they have all been in the room.
Ah, but what's a sufficient number of times? The unknown initial state is what tripped me for a bit. :)
n-1, where n is the number of prisoners. -1 to account for the leader.
It's actually 2(n-1), because the designated switch can start in either state.
Re:Prison Switcharoo
by linux_devil on Sunday February 23, 2014 @12:08PM
(#7286535)
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the on or the off position. I am not telling you their present positions. The switches are not connected to anything.
The switches are not connected to anything, correct me if I am wrong but how will you find out light is on sufficient number of times
Re:Prison Switcharoo
by jaltekruse on Sunday February 23, 2014 @12:12PM
(#7286550)
The person tallying keeps a count in their head.
Re:Prison Switcharoo
by rokhayakebe on Sunday February 23, 2014 @02:31PM
(#7287195)
Good luck if the leader is the 22nd person to go in.
The prisoners meet together and designate a leader. The leader will maintain a tally. They also designate one of the switches to not matter. The prisoners then use the following strategy:
When a prisoner is lead to the room, if the designated switch is off and it is the prisoner's first time flipping the relevant switch, it is turned on. Else, flip the irrelevant switch. If the prisoner is the designated leader, and the relevant switch is on, he adds a count to his tally and turns the relevant switch off. Otherwise he just flips the irrelevant switch. This way, once the leader has seen the light be on a sufficient number of times he can definitively say that they have all been in the room.