100 prisoners and a lightbulb

Question

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.

Answer 1

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.

Answer 2

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 ...

Answer 3

My solution to this was a more generalised version of the above. At any given time, each prisoner has a value. This starts at 1 for all prisoners except one of them that has a value of 29.

On each night the light bulb has a power of two value that is agreed by the prisoners at the beginning. When a prisoner enters the room (on any day except day one), if the light is on they increase their value by the light-bulb value of the night before.

They then expand their value in binary. If they have a 1 in the power-of-two slot for the value on the subsequent night, they ensure the light is left on and subtract this from their own value. If they have a zero in that slot they ensure the light is left off.

The sequencing of light bulb values is chosen by drawing from a random distribution that reflects the expected density of the powers-of-two values present in the prisoner population as a whole given the previous choices. (The prisoners have to have prodigious memories for this algorithm).

If any prisoner finds themselves worth 128, they announce success.