4 ms·
Here's the best solution I've heard for this: The prisoners meet together and designate a leader. The leader will maintain a tally. They also designate one of
by sfenu 13y ago
Here's the best solution I've heard for this:
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.
- linux_devil 13y ago"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
- jaltekruse 13y agoThe person tallying keeps a count in their head.
- callahad 13y ago> 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. :)
- gberger 13y agon-1, where n is the number of prisoners. -1 to account for the leader.
- evanb 13y agoIt's actually 2(n-1), because the designated switch can start in either state.
- stefan_kendall 13y agon. You have to account for the case that the light is on and the tallyer is the first to enter the room.
- rokhayakebe 13y agoGood luck if the leader is the 22nd person to go in.