7

I saw this riddle ealier today on 9GAG (and it's found on multiple news sites), I have found 2 answers with my collegues, but i'm wondering if someone else can solve it.

'One hundred prisoners have been newly ushered into prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst each other. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The prisoner will be able to observe the current state of the light bulb. If he wishes, he can toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves and the prisoners huddle together to discuss their fate. Can they agree on a protocol that will guarantee their freedom?'

If time wouldn't matter, this would be a flawless solution

Step 1:

Together will all prisoners, choose 1 leader.

Step 2:

Whenever a prisoner enters the interrogation room he will turn on the light IF the light is OFF AND he hasn't turned on the light before. IF the light is ON, he ignores it (and will wait for his next turn)

Step 3:

every time the Leader steps in the room he makes sure he turns the light OFF and counts

Step 4:

When the leader has entered the room 99 times while the light was on, it means everyone has been in the room. And he will call the guard.

Mathieu Brouwers
  • 193
  • 4
  • Correct again, im terrible at searching.. – Mathieu Brouwers Mar 11 '16 at 12:30
  • This is the original riddle though, and not a variation. – Mathieu Brouwers Mar 11 '16 at 12:48
  • This should not have been marked as a duplicate. It is a significantly different question than the one linked, which is about probabilistic strategies to get out faster. While that question was inspired by this puzzle, this puzzle itself is not found on this site. – Paul Sinclair May 14 '16 at 03:33
  • I first encountered this puzzle on William Wu's puzzle site back in 2002. Somebody (not me) came up with a token passing strategy that allowed intermediary collectors, which sped up the process of getting the final message to the leader. I don't remember for sure, but I think it cut the expected time down from ~30 years to something like ~17 years. – Paul Sinclair May 14 '16 at 03:37

0 Answers0