115. There Are 100 Prisoners.
There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room unchanged.
After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers 'Yes' and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer 'I don't know' without any consequences.
Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician.
Submitted by tartle · Added 29 August 2016
Solution:
The prisoners designate one as the 'leader' (or 'counter') and the others as 'visitors.' Each visitor will turn the lamp on the first time they enter the room if it is off, and they will not touch the lamp again after that. The leader will switch the lamp off if it is on, or do nothing if it is off. The leader counts how many times they have switched the lamp off. Once the leader has switched off the lamp 99 times, they can confidently declare that all prisoners have visited the room at least once. This strategy assumes the lamp starts in the off position; if the initial state is unknown, the logic remains similar but requires adjustment in the counting method.
Comments (1)
During the strategy time, they assign a leader. Only the leader can ever answer the question as yes, everybody else will say no, always.
Now, everytime a prisoner(other than the leader) goes into the room, he'll switch on the light provided he hasn't done so once already.
If the light is on, he'll simply come back and wait for the next turn. If he has switched on the light once in the past, then he'll again walk back without altering the state of the light.
Everytime the leader goes into the room, he'll switch the light off if it's on, or else come back without doing anything.
Once the leader switches off the light 99 times, everybody would have visited the room with the lamp/light at least once.
PS: This is based on the assumption that the light is initially known to be off. If the initial state of the light Is unknown, the solution will be slightly different, but the logic will be same. Give this a try too.
Add a Comment or Suggest an Answer