30
$\begingroup$

100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?

http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml

I was wondering does anyone know the solution for the 4,000 days solution. Also, anyone got any ideas on how to solve this?

Just wanted to know if anyone got any ideas how to solve this. http://www.siam.org/ is offering prize money for a proof of a optimal solution for it. I suppose to make it clear the people want a plan that would mean on average it would take least amount of time to free the prisoner. The point is the average run time is as low as possible.

  • 2
    Depends entirely on the values of the outcomes (freedom, death) and cost of another day in prison.2012-03-04
  • 3
    Why did someone downvote this. The riddle is well defined and if you click on the link it's okay. Plus there is a riddle tag.2012-03-04
  • 0
    @AlexBecker no . The point is on average you want a strategry that takes the least amount of time so everyone is freed.2012-03-04
  • 2
    @Alex The cost of death is infinity; the cost of another day in prison is 1; and the value of freedom doesn't matter, because any strategy that avoids infinite punishment will result in freedom.2012-03-04
  • 1
    That SIAM link is a bit unhelpful, steadyboy! Can you be more specific?2012-03-04
  • 2
    @AlexBecker, it's a hard condition that failure must he impossible. Here's a simple strategy that provides a small postive chance of success and zero risk of failure: prisoner 0 turns the lamp on on days divisible by 100 and off on all other days. No other prisoner ever turns it on. Prisoner $n$ for $0 turns the lamp off if he's in the living room and it's _not_ day $n$ modulo 100. Prisoner 99 declares success if he's in the living room on day 99 modulo 100 and sees the light being on. Expected running time about $100^{101}$ days; will succeed eventually with probability 1.2012-03-04
  • 1
    @TonyK: Indeed. Google turns up only one other mention of this and the wording is almost identical with no link to any "prize". Color me skeptical for various reasons.2012-03-04
  • 0
    This question is highly flawed. You state no prisoner can see the light bulb from his/her own cell but I am wondering can they see the light? If so, then any of the $100$ prisoners that can can be a "counter" and any "new" person that enters the central living area can toggle the light to indicate it is their first time in the room. Problems are you didn't mention if the warden can also toggle the light to mess up the system. You also stated prisoners can be shot but you didn't say with what. Perhaps a camera?2015-01-03
  • 0
    I have a hard time thinking of a [nice] plan. But if I were forced into this I would advise each prisoner to decline a second invite. Remove random, 101 days minimum. Sounds like Alcatraz.2017-07-11

6 Answers 6