Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Depends entirely on the values of the outcomes (freedom, death) and cost of another day in prison. –  Alex Becker Mar 4 '12 at 15:39
1  
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. –  steadyboy Mar 4 '12 at 15:46
1  
@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. –  Tanner Swett Mar 4 '12 at 15:53
1  
That SIAM link is a bit unhelpful, steadyboy! Can you be more specific? –  TonyK Mar 4 '12 at 16:33
1  
@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<n<99$ 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. –  Henning Makholm Mar 4 '12 at 16:34

3 Answers 3

The "standard" solution for the puzzle is the following. Prisoners choose one of them, lets call him "The Counter". The job of The Counter is to count the prisoners who have been in living room. Other prisoners' job is to give a signal to The Counter that they have been in the living room. This is done as follows. The Counter is the only person who can turn the light off. Others can only turn the light on and do it only once. That is if a prisoner walks into the living and the light bulb is off and he has never turned the bulb on, then he turns it on. The bulb will stay on, until The Counter comes and turns it off. When The Counter has turned the bulb off 99 times, he knows all prisoners have been in the living room.

I don't know what is efficiency of this solution, but in your link it is stated that the standard solution takes 27-28 years on average. So I suspect that is efficiency of this solution.

share|improve this answer
    
Back of the envelope calculuation: Each time the bulb is off we have to wait until a yet uncounted prisoner comes around. This takes longer as time goes by, but in total we should expect about $$\frac{100}{99}+\frac{100}{98}+\frac{100}{97}+\cdots+\frac{100}{1} \approx 100\log 99$$ days of waiting in this phase. Once it is on we must wait for the counter to show up, on average 100 days per prisoner we count. This works out to between 28 and 29 years, but the logarithmic estimate may be slightly inflated. –  Henning Makholm Mar 4 '12 at 17:11
    
@Henning: Each time the Counter is waiting to go to the living room, the probability that the light will be turned on is the probability that one of the uncounted prisoners gets to the living room before the Counter. If there are $u$ uncounted prisoners, this probability is $\dfrac{u}{u+1}$. Thus, the number of passes needed for the Counter to see the light on is $\dfrac{u+1}{u}$. –  robjohn Mar 4 '12 at 23:56
    
@Henning: Therefore, the expected number of days to count all $99$ other prisoners is $$\left(\frac{100}{99}+\frac{99}{98}+\frac{98}{97}+\dots+\frac32+\frac21\right) \cdot100$$ and this is approximately $(99+\log(99)+\gamma)\cdot100\approx10417$ days, which is about $28.5$ years. –  robjohn Mar 4 '12 at 23:56
    
@Henning: now that I reread your answer, I notice something I missed before, and I believe that our answers are the same. Sorry for the interruption :-) –  robjohn Mar 5 '12 at 0:19

Here's one way to improve on Levon's solution. I don't have time to do a full probability analysis just now, but my very rough estimates suggest that with careful tuning, techniques like this should be able to get the average running time down to around 4000 days:

It's not certain but "pretty likely" that every prisoner gets to visit the living room at least once during the first, say 800 days. So divide the strategy into several phases:

  • Day 1 to 800: Everyone toggles the lamp the first time they see the living room. If we're lucky, after day 800 there will be 50 prisoners who have ever turned off the lamp. They are the "active" prisoners. (If we're unlucky and there's someone who hasn't been in the living room yet, there will be less than 50 active prisoners).

  • Day 801 to 1600: Ever prisoner who is active after the first phase toggles the lamp the first time they see the living room during this period. (The prisoner who enters on day 801 makes sure the lamp is already off before he does his part -- if so, something will have gone wrong but proceed according to plan anyway). The prisoners who turned the lamp off during this phase are still active. If we're lucky there are 25 off them.

  • Day 1601 to 2400: Halve the number of active prisones once again. This time those who turned the lamp on stay active; there are now 13 active prisoners unless something went wrong.

  • Day 2401 to 6000: Count the 13 still active prisoners using the standard algorithm, with a Counter selected in advance.

If anybody finds themselves still in prison on day 6001, everyone shrugs and starts the entire algorithm over from day 1. Since 3600 days should be plenty of time to count 13 active prisoners, the main risk is that someone who needed to didn't get to participate in one of the first three phases, and since the risk of that is small, it won't affect the expected running time of the algorithm much.

With the parameters given here (and several approximation shortcuts in the calculation) this strategy has an average running time of 4353 days. But there's room for some optimizations by tweaking the numbers. It appears that 800 days is close to optimal for the first halving, but the later halvings can be shortened a bit without incurring quite as large a total risk of missing an active prisoner and having to restart.

EDIT: After a semi-systematic search for better parameters it seems that the best this method can get is an average running time of 4227 days (about 11½ years), which is achieved by three halving phases of 840, 770 and 700 days, followed by a counting phase of 2200 days. Neither more halving phases nor fewer ones improved the overall efficiency. Back to the drawing board ...

share|improve this answer

A survey of various strategies can be found at https://www.math.washington.edu/~morrow/336_11/papers/yisong.pdf. It describes a strategy ("two-stage counting") which is believed, based on simulations, to yield expected run times between 3500 and 4000 days, and references a hybrid strategy by a Bertram Felgenhauer which is supposedly proved to run in 3949 days average.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.