5 Star Logic Problem (100 prisoners and a light bulb)

[Tigers2B1]

Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, 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. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

 

[AKG]

One person is chosen as the counter. If the light switch is on, no prisoner will touch it. If it is off, and a prisoner who has never flicked the switch enters, then he flicks the switch on. It stays like that until the counter returns. The counter never flicks it up, only flicks it down. Once he notices that it's been flicked up 99 times, he says that 100 prisoners have visited, and they go free.

 

[NeutronStar]

One person is chosen as the counter. If the light switch is on, no prisoner will touch it. If it is off, and a prisoner who has never flicked the switch enters, then he flicks the switch on. It stays like that until the counter returns. The counter never flicks it up, only flicks it down. Once he notices that it's been flicked up 99 times, he says that 100 prisoners have visited, and they go free.

Ok, so here's some math questions now.

What's the least possible number of days that the prisoners will serve (the least would be if the counter was randomly chosen every other day).

Also, statiscally speaking, what is the most probable number of days that the prisoners will serve? (show all work )

 

[Kurdt]

Te first prisoner in takes the bulb and then counts to 100 days as soon as he is picked after the 100 days has elapsed he replaces the bulb and the next prisoner in will declare all people have been in the room. Thats the only way I can see it working because they'd be very unlucky if all of them hadn't been in. Anyway they could leave the bulb on if they wished until the first prisoner returned after 100 days cos I wouldn't like to change one in pitch black.

 

[NeutronStar]

Te first prisoner in takes the bulb and then counts to 100 days as soon as he is picked after the 100 days has elapsed he replaces the bulb and the next prisoner in will declare all people have been in the room. Thats the only way I can see it working because they'd be very unlucky if all of them hadn't been in. Anyway they could leave the bulb on if they wished until the first prisoner returned after 100 days cos I wouldn't like to change one in pitch black.

By your logic they would get out in 101 days no matter what. Why bother doing anything other than counting days?

I think that the original poster didn't make it clear about whether or not any given prisoners could be chosen twice. For AKG's logic to work prisoners would need to be picked at total random meaning that many of the prisoners would go to the room many times. Otherwise AKG's counter would not be able to go into the room more than once.

Using AKG's method the least amount of time they could possibly serve would be 198 days (and this assumes that the counter got picked every other day, and each of the other prisoners only got pick once each.) That would be extremely unlikely if they were picking prisoners at random.

That's why, in my last post, I asked someone to calculate what the most probable number in days of time they would serve. I'll bet it would be in the thousands of days! I'm not good with probability math so I'm not sure how to calculate that. It might be tens of thousands of days!

 

[Tigers2B1]

...I think that the original poster didn't make it clear about whether or not any given prisoners could be chosen twice...

A prisoner can be selected any number of times --

 

[Kurdt]

Tigers2B1 did make it clear. He said they were chosen at random, which by any logic means that they can be chosen any number of times depending on what number is drawn from the lottery machine that day. Also thousands of days is probably an exaggeration the probability for each prisoner to get chosen is 1/100. The probabbility one is chosen twice is 1/10,000. So technically it is not 101 days it is 100 days then any time he gets chosen after that.

 

[TENYEARS]

Certainty is the key. There is no way you can be certain, because if one of the prisoners does not go along with the plan what certainty do you have? Here are two options: If you allow that the light bulb will not be touched by anyone other than the prisoners(not likely), you measure the rotation of the bulb from firm fit to where it will turn out when lit. You divide that by 100, and if it was your first time in the room, you turn the bulb your share(allowing that the prisoners have a method of valid measuremeant) when the 100 new person comes in they test the light first(to see if the bullb was burn out, if so the plan is done) if the bullb lights he makes his turn and test the switch, if it does not light all 100 have seen the room.

Other option, each new person places some mark on a not so visible area, when there are 100, the assertion can be made. This idea may go outside the required parameters.

 

[aychamo]

When the light is on the prisoners see a door that is accidently left open and the prisoners escape. Whenever the warden comes in and says "Where is eveyrone" the last prisoner knows they are all gone.

:)

 

[Kurdt]

that plan is fine but you can not logically assume a screw fitting light bulb. If it is a bayonet fit then the plan becomes redundant.

 

[NeutronStar]

Tigers2B1 did make it clear. He said they were chosen at random, which by any logic means that they can be chosen any number of times depending on what number is drawn from the lottery machine that day. Also thousands of days is probably an exaggeration the probability for each prisoner to get chosen is 1/100. The probabbility one is chosen twice is 1/10,000. So technically it is not 101 days it is 100 days then any time he gets chosen after that.

Well, I didn't know how to do that math, but I do know how to program a computer. So I wrote a simulation of AKG's method. After running the program several times (each time the program averages 1000 runs) I got a pretty consistent result.

The most likely number of days that the prisoners would serve would about 10,420 days. That a little over 28 years. That's the most likely amount of time they would serve using AKG's method.

If you'd like to see my program I'll be glad to post it. I wrote it in Visual Basic and it's quite short.

There's probably some way to do this directly using probability mathematics.

 

[Kurdt]

That happens to be the standard answer for the problem and is a testament to your programming skills if you managed to come up with such an accurate answer.

 

[pig]

I apologize for topic necromancy, but I haven't been on PF much in recent months and I have a solution to this problem that, on average, beats the 1 counter method.

The prisoners divide themselves into several groups.

The first group has 69 guys, who start with one pointA each. The second group consists of 25 guys, who will be collecting the pointAs. Each of them needs to collect 3 pointAs to "get" a pointB, except for 6 guys who have to collect only 2. The next group has 5 guys, each of whom needs 5 pointBs to get a pointC. We have 1 guy left, the leader, who has to collect 5 pointCs.

"to pass on a pointX" = to get into the room in phase X, and if the light is turned off and it's not the last day of the phase, turn it on and substract 1 from your pointX count.

"to collect a pointX" = to get into the room in phase X, and if the light is turned on, turn it off and add 1 to your pointX count.

In phaseA, which lasts for 1500 days, the 69 guys pass on the pointAs, and the 25 guys collect them. In phaseB, which lasts for 1800 days, the 5 guys collect pointBs. In the third phase, which lasts for 1100 days, the leader collects pointCs.

At the end of the third phase, if he has 5 pointCs, he informs the guards that they have all been in the room and they go free. If he didn't collect them - we repeat the whole cycle, but with reduced phase periods (for example, halved every time the cycle repeats, but never below predetermined minimum durations, because for example a 2 day phase isn't very effective, i used 400/600/300 as minimums).

The only problem happens when, on the last day of a phase, a guy who is NOT supposed to collect points in that phase is selected, and finds out the light is on. The problem is, the light HAS to be turned off for the beginning of the next phase is tomorrow, and for example a left over pointA from phaseA will be misinterpreted as a pointB in phaseB. But if he turns off the light, a point will be "lost", and they will never get out.

The solution is simple - whoever the guy on the last day of the phase is, he turns off the light and collects the point in question. If it's the last day of phaseA, and the leader comes in - he collects the pointA and passes it off when the whole cycle repeats - he plays a double role. If it's one of the 69 guys, he does the same. If he still has his own pointA, he now has 2. And so on.

The number of groups/phases, the number of people in each group, the durations of phases, the formula for reducing the durations of phases if the cycle repeats, and so on - are variable. If you make the cycles longer, the minimum possible time becomes longer, but the probability that the cycle will have to be repeated decreases, and so on. This is just an example, and I'm sure there are better solutions (this one lasts ~4300 days on average, judging by the simulation I made).

This could perhaps even be generalized into a gigantic average time function of many variables, and a minimum found. But it would require an insane amount of math, and knowledge I don't possess. It still wouldn't prove this as the optimal solution, but at least we'd have optimal numbers to use with this method.


This is my program, it allows you to type in the number of prisoners, groups, sizes of groups, etc. "Divide by" is the number by which to divide the phases after an unsuccessful cycle. If you put in groups = 1, group A = 99, you get the original 1 counter solution, except for the last-day-of-cycle-difference, but you can get around that by putting some huge number like 10000000 as the phase lenght, and divide by 1. By playing around with numbers you could probably get an average time below 10 years.

 

[wsingaram]

Finally a solution

The first prisoner leaves the light switch off. For the duration of the game, the first prisoner will always leave the light switch as is. When a different prisoner enters the room he will turn it on. For the duration of the game this prisoner along with the first prisoner will leave the light switch as is. The newest prisoner, different from the first two, is designated the counter. His job is simply to turn off the light switch everytime the light is on. Upon entering, he realizes that there have been two prisoners who have been inside the room. This prisoner will work cooperatively with his fellow prisoners as follows:
If it is the first time a prisoner enters the room the prisoner will turn the light on. Otherwise the prisoner will do nothing. (So the second time a prisoner enters the room he does nothing). Everytime the Counter Prisoner sees the light bulb on, he realizes a new prisoner has entered the room (then switches the light off). There is, however, one catch. In the case where two prisoners enter the room before the Counter prisoner and neither of the prisoners have entered the room before, we say the first prisoner turns on the light switch while the latter prisoner does nothing. That is, a new prisoner shall only turn on the light if the light was off to begin with.
Following this method, the Counter prisoner can count to 100. Once he is chosen he calls out. No complicated math needed, just pure logic.
--Special thanks to my homies for cranking this one out with me.

 

[kant]

We only need one person as the counter. Assuming that at each pick, each prisoner has equal chance.

 

[planish]

Before the random picking begins, the prisoners are allowed to get together to discuss a plan.

Prisoner #17: "Okay guys, where do we have the get-together to plan our strategy?"
All others (in unison): "THE LIVING ROOM!"

Is that it?

 

[heusdens]

It's far more simple:
Every time a prisoner enters the room and turns on the light.
If he is there for the first time, he scratches a line on the wall.
If the count of scracthes becomes 100 when he has done that, he can certify all prisoners been in the room, and they can be set free.
Otherwise, he does nothing.
Then he turns off the light an leaves the room.

 

[davee123]

It's far more simple:
Every time a prisoner enters the room and turns on the light.
If he is there for the first time, he scratches a line on the wall.
If the count of scracthes becomes 100 when he has done that, he can certify all prisoners been in the room, and they can be set free.
Otherwise, he does nothing.
Then he turns off the light an leaves the room.

That's sort of missing the point of the problem. For all intents and purposes, the question ought to stipulate that "The only thing they may alter in the room is whether the light switch is on or off." Otherwise the problem is so trivial (as you point out) that it's not worth asking.

DaveE

 

[light_bulb]

in a real prison no one would be screwing/unscrewing the light bulb unless they were trying to make fire, they would find ANYTHING and leave a mark around the light bulb.

 

[BobG]

in a real prison no one would be screwing/unscrewing the light bulb unless they were trying to make fire, they would find ANYTHING and leave a mark around the light bulb.

I understand. Prison is rough for light bulbs.

A pin-up for your wall should make you feel better.

 

[Schrodinger's Dog]

Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, 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. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

Not a logical answer but a correct one given the limitations of the problem, since you never mention how long each sentence is for the prisoners, the most simple answer is, only when the last prisoner is left can he make that assertion. It's not logical but it is lateral.

They simply agree not to play the game until there is only one prisoner left.

All one hundred prisoners must of been there, since it's a central room. Even if by chance one prisoner never went there it is true, since it's random this is a possibility. We don't know the duration of their sentences, and even if we did it doesn't matter. Even if they died, they would be carried out through the central room to be buried. In this situation and given the fact that the light bulb is irelevant, it's a possible answer. because the only remaining prisoner is taken out every day.

Or this is my logical answer: every prisoner records if they have never been in the room before by saying: never = down position light off, if you see a down you note it and then proceed by either leaving it down meaning you also have never been in the room before, or by flipping it up(light on) Saying the previous person had not been in the room before but you have: unless you have been in the room before and the light switch was in the up position, then you flip it down as if you have never been in the room before.

Once you have been in the room 50 times and seen 50 consecutive up(light on) and then not necessarily after that but when you see 50 consecutive light down(off) Then you make the assertion that everyone has been in the room.

It came to me in a dream well not really I just figured it out, do I win a prize?

 

[Schrodinger's Dog]

The first prisoner leaves the light switch off. For the duration of the game, the first prisoner will always leave the light switch as is. When a different prisoner enters the room he will turn it on. For the duration of the game this prisoner along with the first prisoner will leave the light switch as is. The newest prisoner, different from the first two, is designated the counter. His job is simply to turn off the light switch everytime the light is on. Upon entering, he realizes that there have been two prisoners who have been inside the room. This prisoner will work cooperatively with his fellow prisoners as follows:
If it is the first time a prisoner enters the room the prisoner will turn the light on. Otherwise the prisoner will do nothing. (So the second time a prisoner enters the room he does nothing). Everytime the Counter Prisoner sees the light bulb on, he realizes a new prisoner has entered the room (then switches the light off). There is, however, one catch. In the case where two prisoners enter the room before the Counter prisoner and neither of the prisoners have entered the room before, we say the first prisoner turns on the light switch while the latter prisoner does nothing. That is, a new prisoner shall only turn on the light if the light was off to begin with.
Following this method, the Counter prisoner can count to 100. Once he is chosen he calls out. No complicated math needed, just pure logic.
--Special thanks to my homies for cranking this one out with me.

This fails as it's competely random so the first prisoner could also be the second and how would he know? Third could be the first? What about if the light switch is off and the first prisoner leaves it off, and your prisoner that has chosen to always leave it as it is is the first. Throws it out. Since it's random, you can't chose who is who. And since no one knows if the first prisoner wasn't picked four times, or the second five, or the third eight or the fourth twenty four times. You can count the days but how do you know which prisoner is which and who's doing what?

What if the counter is the first third or fourth in this situation. What if the counter is picked the first five times? Since it's random your counter will completely upset the system. He's picked first and the light switch is on, how would he know what the situation is? Your counter could be the first second and third person picked, then who would know? The counter can count as much as he likes but if he's unfortunate enough to be chosen the first five times, and then is never chosen? how would he know? Assuming the light switch could of been either, although it works it's if a it is not infalable and not 100%. Remember none of the prisoners know what has happened. There's a spanner here, if you have randomness and the counter is picked every time for the first 100 times. What now?

 

[Schrodinger's Dog]

My answer is this simply the first prisoner to see x amount of down switches, calls the warden. As he knows then everyone has been in the room. Simple solution?

Well am I right? Is submitted my name to some forum who are rattling around trying to solve this, soon find out?

Who submitted it? Am I right?

 

[cristo]

My answer is this simply the first prisoner to see x amount of down switches, calls the warden. As he knows then everyone has been in the room. Simple solution?

What are you taking x to be?

 

[Schrodinger's Dog]

What are you taking x to be?

I'm not a probability expert I was hoping a mathemetician could work it out

Looking at the forum it seems that Wisingrams answer is already given and the professor who divised the problem said it is wrong pretty much for the reasons given in the original puzzle and the reasons I give.

Something like 100/100 chance of being right with seeing 100 down switches in row probably. but you'd have to factor in the previous events. Too much for me I'm afraid

With the preconditions eventually the light will always be off. So you can say x is whenever it becomes statisticlly likely for this to mean 100 prisoners have been in the room. as the probability tends to 1.

 

[cristo]

I'm not a probability expert I was hoping a mathemetician could work it out

Looking at the forum it seems that Wisingrams answer is already given and the professor who divised the problem said it is wrong pretty much for the reasons given in the original puzzle and the reasons I give.

Something like 100/100 chance of being right with seeing 100 down switches in row probably. but you'd have to factor in the previous events. Too much for me I'm afraid

With the preconditions eventually the light will always be off. So you can say x is whenever it becomes statisticlly likely for this to mean 100 prisoners have been in the room.

I agree that there will be some number x such that when the counter counts the switch down for x consecutive times, then he can say, without doubt, that all prisoners have been in the room. However, it seems to me that this number must be rather large; for example, if x=100, since the prisoners are being chosen randomly, one prisoner could go in, say, 8 times during this counting process, which would mean that all 100 had not been in when the counter reaches 100.

I suspect that there's some other solution to this, which would enable x to be much less than the value of x required in the above solution. However, I can't quite think of another method (yet!)

 

[Schrodinger's Dog]

I agree that there will be some number x such that when the counter counts the switch down for x consecutive times, then he can say, without doubt, that all prisoners have been in the room. However, it seems to me that this number must be rather large; for example, if x=100, since the prisoners are being chosen randomly, one prisoner could go in, say, 8 times during this counting process, which would mean that all 100 had not been in when the counter reaches 100.

I suspect that there's some other solution to this, which would enable x to be much less than the value of x required in the above solution. However, I can't quite think of another method (yet!)

Yes but of course there is more information here, if a prisoner goes in fifty times and sees a certain pattern of switches he knows the trend, so you can adjust your probability accordingly, this I feel is close to a solution. But there's just one more element I think such as the counter proposal, but the counter is chosen so that if he goes in first he leaves the light switch in the off position if up,or up if it was down. Then we can be sure the counter is 100% reliable. anyone not the counter could leave the contrary message according to the first message, he now becomes the counter and adjusts accordingly,

Thus we have an n=0 or 1 starting proposal and everyone knows what the first person was, counter or non counter, from here if we apply my system and use trend analysis of all 100 prisoners with a counter, sooner or later whoever is chosen the most is going to have a statistically viable solution according to probability.the one who calls the foreman would become the person who was chosen the most in essence and could be assigned as the counter, now you have either one counter or two, and you can afjust accordingly for either, one pattern will show up for 1 or 2, if one then says he will always leave the switch up and the other down, then you know from the pattern whether there is a counter or not, because he would have the most stistically viable imput, we then just have to set the counter a task of doing somehing which will reveal a pattern and bobs your uncle, prediction with almost certainty.

Eventually when you come to the point where you can predict what position the switch will be in with 100% accuracy you call the warden.

I'm thinking as I type.

hmm if the counter always changes the result regardless, then couldn't he observe a pattern forming. Say you used the first part, then the counter when he saw all positions as they should could change one switch to up and predict with certainty how long it would take for the switches to all be down, no probability just logic.

I feel I'm getting close?

if the counter is up to start, assuming he is the counter, how many times would he have to visit before he was sure? How about the new counter who was assigned only on the basis of being very frequently their? How could he inform the original counter?

hehe I'm going round in circles.

Oh wait you have a counter and a foil, if you are the counter the following person is the foil, this person will if he sees always down x times change it to up, thus alerting erm?

I have it use this in line with my first proposal

Wait a minute, if we have a situation where we have up as the first position 1 and down as the second 0, and then we assign a foil, then as soon as all the lights are off 100 times in a row or up you know everyone has been there? since down becomes more prevalent, and up to down by the counter assigned before they enter, are you a 1 on or 0 off, 50/50 would mean a solution in line with days you'd been there right? If you can predict 50 of 50 you've cracked it.

the counter will see a pattern then he can adjust again, when he only sees the foil doing the opposite of what he is meant to do, he calls for the warden, the counter is simply anyone who has been in there enough times to have derived a solution. You can do this in 100+x days by probability alone, in fact it becomes certainty.

The original counter follows the rules to the letter, except if he is first in the room as above. The foil always switches to the opposite value regardless. If he does this eventually all the siwitches will always be down.

The first person to see this x times can call the warden, or the counter can after he can predict what each outcome will be.

Is that better?

I'm sure if you analysed up or down, with this system there would be a precise point were either would be up or down, and when you saw the foil in the system, after you had observed all down which of course would happen more quickly with the foil in there. Then you have your solution.

The first person to see all down say x times and then 1 up. What is the probability of this leading to a solution?

If you start with 1 and use this system, if your the counter and have been in 100 times, you will know the solution, the first person if the counter, knows how the switching will progress because he knows absolutely the start position, the second person, knows absolutely the start position, the third and so on. Now when the first person to have been in the room x times knows the exact pattern he calls for the warden, this can be all down with 1 up out of nowhere, but I'm pretty sure with this system, the counter knows precisely what will happen with the switches given probability. Eventually as well with this system it settles down to a point where they are always down and the person who's first to see 100 downs, calls the warden, what is the probability of this?

Another thought if you assign everyone as odd and even, and an odd person always puts the switch off if it is off and leaves it on if it is on unless this is his first time in the room, then he leaves it off and an even only puts it on if he has been in the room for the first time, this would also lead to all the switches being off at one point, 100 of theese and you could call the warden.

 

[cristo]

I didn't see that this was 3 years old, and I didn't see the first reply. What's wrong with AKG's answer?--it works!:

One person is chosen as the counter. If the light switch is on, no prisoner will touch it. If it is off, and a prisoner who has never flicked the switch enters, then he flicks the switch on. It stays like that until the counter returns. The counter never flicks it up, only flicks it down. Once he notices that it's been flicked up 99 times, he says that 100 prisoners have visited, and they go free.

 

[Schrodinger's Dog]

I didn't see that this was 3 years old, and I didn't see the first reply. What's wrong with AKG's answer?--it works!:

If the counter goes in the first 100 times then the system is screwed, that is pretty much it and a few other things, but since the counter goes in randomly it could take about 800 years to get an answer.

This is not correct. We are talking about a system which is fool proof.

AAMOI I don't think anyone has found an answer yet.

With my answer the counter is the person who goes in most often, and he also knows what the start condition was. Thus he will on average find an answer quicker than a non random assigned counter. As he is the most frequent visitor, of course no one knows for sure, but by proabbility and knowing the initial position of the switch you can work out what the likelihood is of all down. and when you see it call the warden. Should in theory be quicker and not subject to freak systems such as the counter never being put in the room.

There's probably a simple elegant answer as well, but I don't have the maths skill to assign probability to patterns.

 

[cristo]

If the counter goes in the first 100 times then the system is screwed, that is pretty much it and a few other things, but since the counter goes in randomly it could take about 800 years to get an answer.

Why is it screwed? The counter is the first person in the room, and so he leaves the switch down. Every other person that goes in the room puts the switch up if it is his first time in the room, and it is already down, otherwise, he leaves it on. On his return to the room, the counter flicks the switch down (if it is up) and adds one to his tally. He repeats until he flicks the switch down 99 times.

If he enters for the first 100 times, this makes no difference, since he will not have an up switch to flick down.

 

[Schrodinger's Dog]

Why is it screwed? The counter is the first person in the room, and so he leaves the switch down. Every other person that goes in the room puts the switch up if it is his first time in the room, and it is already down, otherwise, he leaves it on. On his return to the room, the counter flicks the switch down (if it is up) and adds one to his tally. He repeats until he flicks the switch down 99 times.

If he enters for the first 100 times, this makes no difference, since he will not have an up switch to flick down.

What about the first 4 thousand times?

If the counter never returns to the room, then it could be long after everyone is dead thus the only survivor is the last man standing, and is it worth it? What is the probability in ten years that the counter is not repicked?

The solution must be without contradiction, he must be 100% certain.

To be honest I only read the last three posts anyway as the others were about 3 years old.

Then later I read the whole thread.

What you want is an answer that's going to be 100% correct in every situation, after all their lives hang on it, I think I gave one, but without maths I couldn't do any better I'm sure a maths wiz could come up with the fewest possible days passing whereby someone could call the warden.

a 100% chance of everyone living is better than a 1% chance of everyone dying.

EDIT:

http://www.cut-the-knot.org/Probability/LightBulbs.shtml

100 Prisoners and a Light Bulb

Some time ago, Ilia Denotkine has posted the following problem on the CTK Exchange
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

He then added a background to his question:


I have seen this problem on the forums, and here are some of the best solutions (to my opinion):

1.

At the beginning, the prisoners select a leader. Whenever a person (with the exception of the leader) comes into a room, he turns the lights on. If the lights are already on, he does nothing. When the leader goes into the room, he turns off the lights. When he will have turned off the lights 99 times, he is 100% sure that everyone has been in the room.
2.

wait 3 years, and with a great probability say that everyone has been in the room.

Does anyone know The optimal solution?

I have taken this problem from the www.ocf.berkeley.edu site, but I believe that you can find it on many others.

As I had a recollection of seeing this problem in [Winkler], I replied


The problem is indeed popular. It's even included in P. Winkler's Mathematical Puzzles, which is a recommended book in any event. Winkler also lists a slew of sources where the problem appeared, including ibm.com and a newsletter of the MSRI.

The solution is this:

The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room.

As it happened, I was wrong. This may be immediately surmised from Stuart Andersen's response. In my wonderment I contacted Peter Winkler who kindly set things straight for me. The formulation in his book is somewhat different, but this difference proves to be of major significance:


Each of n prisoners will be sent alone into a certain room, infinitely often, but in some arbitrary order determined by their jailer. The prisoners have a chance to confer in advance, but once the visits begin, their only means of communication will be via a light in the room which they can turn on or off. Help them design a protocol which will ensure that some prisoner will eventually be able to deduce that everyone has visited the room.

If someone can find a solution I'd be interested, I say use probability with my above suggestions, ie formulate a mathematical equation that is infallible regardless of x. But I am not up to the task, my maths isn't that good, I'm sure though that my answer is correct it just isn't the best mathematical way to do it.

I would surmise though that the most frequent flyer could formulate the best probability based equation, but now your assuming you'd have to teach everyone enough probability maths, my assumption is that the answer is a mathematical formula that is so simple that it is proven, I have no idea how to set about doing this though.

 

[davee123]

With the one-counter solution, I wrote a simulator and ran it 100,000 times. Of course, this assumes that the prisoner assignment is totally arbitrary and the random numbers are "truly" random (no clustering, but evenly distributed).

Results:

0-999 days: 0 times
1000-1999 days: 0 times
2000-2999 days: 0 times
3000-3999 days: 0 times
4000-4999 days: 0 times
5000-5999 days: 0 times
6000-6999 days: 10 times
7000-7999 days: 459 times
8000-8999 days: 6806 times
9000-9999 days: 27676 times
10000-10999 days: 37769 times
11000-11999 days: 21085 times
12000-12999 days: 5461 times
13000-13999 days: 681 times
14000-14999 days: 52 times
15000-15999 days: 1 time

On average, that means you're looking at about 24 to 33 years before you're POSITIVE that everyone's been in the room. Being overly optomistic, you might actually wait 16 years. And there's about a 0.001% chance that you'll be waiting 42 years or more.

Now, comparaitvely, here's how many days it ACTUALLY took to get all 100 people in the room:

0-99 days: 0 times
100-199 days: 0 times
200-299 days: 409 times
300-399 days: 14543 times
400-499 days: 35987 times
500-599 days: 27511 times
600-699 days: 13046 times
700-799 days: 5353 times
800-899 days: 1998 times
900-999 days: 755 times
1000-1099 days: 266 times
1100-1199 days: 89 times
1200-1299 days: 33 times
1300-1399 days: 5 times
1400-1499 days: 3 times
1500-1599 days: 1 time
1600-1699 days: 1 time

So, if you wait 4 years and then assert that everyone's been in the room, you have around a 99.997% chance of being correct. That means chances are, you're pretty safe NOT using the technique, and just waiting, say, 5 years for a 99.9999% chance of safety, rather than 16-42 years for a 100% chance of safety.

DaveE

 

[Schrodinger's Dog]

With the one-counter solution, I wrote a simulator and ran it 100,000 times. Of course, this assumes that the prisoner assignment is totally arbitrary and the random numbers are "truly" random (no clustering, but evenly distributed).

Results:

0-999 days: 0 times
1000-1999 days: 0 times
2000-2999 days: 0 times
3000-3999 days: 0 times
4000-4999 days: 0 times
5000-5999 days: 0 times
6000-6999 days: 10 times
7000-7999 days: 459 times
8000-8999 days: 6806 times
9000-9999 days: 27676 times
10000-10999 days: 37769 times
11000-11999 days: 21085 times
12000-12999 days: 5461 times
13000-13999 days: 681 times
14000-14999 days: 52 times
15000-15999 days: 1 time

On average, that means you're looking at about 24 to 33 years before you're POSITIVE that everyone's been in the room. Being overly optomistic, you might actually wait 16 years. And there's about a 0.001% chance that you'll be waiting 42 years or more.

Now, comparaitvely, here's how many days it ACTUALLY took to get all 100 people in the room:

0-99 days: 0 times
100-199 days: 0 times
200-299 days: 409 times
300-399 days: 14543 times
400-499 days: 35987 times
500-599 days: 27511 times
600-699 days: 13046 times
700-799 days: 5353 times
800-899 days: 1998 times
900-999 days: 755 times
1000-1099 days: 266 times
1100-1199 days: 89 times
1200-1299 days: 33 times
1300-1399 days: 5 times
1400-1499 days: 3 times
1500-1599 days: 1 time
1600-1699 days: 1 time

So, if you wait 4 years and then assert that everyone's been in the room, you have around a 99.997% chance of being correct. That means chances are, you're pretty safe NOT using the technique, and just waiting, say, 5 years for a 99.9999% chance of safety, rather than 16-42 years for a 100% chance of safety.

DaveE

The chance has to be 100%, that's the point otherwise it's easy to solve. Now the only method I know that does this in an optimised and 100% situation is to have no counter, but everyone as a counter, the first person to get enough results to call the warden calls the warden, in the unlikely event that the counter is never chosen, here at least you will be 100% corrrect in your assumption not 99.9999996 but 100% as the question asks. This is the point.

You have to bear in mind in the one counter situation if the counter is never chosen, all prisoners will be dead before the counter can make an assumption.

http://www.cut-the-knot.org/Probability/LightBulbs.shtml

This would work of course, but is it optimal? For instance, this would also work, I think:

Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room.

What does optimal mean here? It could only reasonably mean that the prisoners are freed in the shortest time. So what is the expected time they must wait until Alice has counted to n-1? This is a rather elaborate calculation in probability, so the prisoners turn to the actuary (who is in prison for embezzlement) for some answers.

He explains that using Bayes theorem,
P(X|Y)·P(Y) = P(X&Y) = P(Y|X)·P(X)

and the linearity of expected value,
E(X|Y)·P(Y) + E(X|~Y)·P(~Y) = E(X)

you can calculate the expected time in prison like this:

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K) = n - 1, P(K=k) = 1/n·((n-1)/n)k, P(K = k & OFF) = 1/n·(c/n)k, which are fairly obvious.

Summing the last formula over all k gives P(OFF) = 1/(n-c). Bayes theorem then gives P(K = k|OFF) = (1-c/n)·(c/n)k, and from this you can calculate E(K|OFF) = c/(n-c) and linearity gives

E(K|ON) = ((n-1)(n-c)-c/(n-c))/(n-c-1).

Now let m be the number of times Alice visits and L be the number of days that pass before she next finds it on. Each time she finds it is off, c does not change, so all the calculations regarding the time until her next visit also do not change.

Therefore, the expected number of days until she next finds the light on is found by summing over all possible m to get the expected total time wasted on visits where the light is off, plus the expected time for the one visit where it was on. This gives

E(L) = (1+E(K|ON))P(ON) + sum(m(1+E(K|OFF))P(OFF)m
= n(1/(n-c-1) - 1/(n-c) + 1 - 1/(n-c)2).

Now we know how long we expect to wait from count = c to count = c+1. Therefore, we must sum this up from c=0 to c=n-2 to find the total expected time E(T). The result is E(T) = n2 - n/(n-1) - a, where a = S(1/c2) from 2 to n. Putting n=100 into this gives 9935.5 days, which is 26.2 years.

But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c, d), which is obviously equal to P(c-1,d-1)·(1-(c-1)/n) + P(c, d-1)·(c/n). Of course, P(0, 0) = P(1, 1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n, d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

As they are about to kill Alice (who was already a member of Mensa) for coming up with a crazy plan to keep them in prison for 26 years, the game theorist (who is in prison for insider trading on the stock market) steps into point out that this is a losing move. If they kill her now she will never go into the room, and the warden will keep them here forever.

In the happy ending, they let Alice live, and they all get out of prison in 5 years. Strangely, they all decline to join Mensa, preferring to enter actuarial training.

Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, 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. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

This is why your idea and all the others are dismissed, not because it isn't likely, but because it does not meet the criteria of the experiment, read the quote again as for why and how this leads to the only conclusion that a single counter or 99 counters is not viable, only all counters will be 100%. Run your tests with that, is it more or less viable? I think you already know the answer, it not only more quickly leads to a result, but it is 100%. This is why he asid he was wrong because quite simply he was wrong, but this leads to the solution, since no one online appears to have got this technicality I call the prize for being the big I am and the man because I am the man.

There answer is different and I can assure you I didn't read it before I came up with mine, so my answer could also be correct, and in fact, if your lucky it's even more optimised. But their answer is to just wait five years, now what if you have both as a precursor, aren't you optimising the situation still further?

 

[davee123]

The chance has to be 100%, that's the point otherwise it's easy to solve. Now the only method I know that does this in an optimised and 100% situation is to have no counter, but everyone as a counter, the first person to get enough results to call the warden calls the warden in the unlikely event that the counter is never chosen, here at least you will be 100% corrrect in your assumption not 99.9999996 but 100% as the question asks. This is the point.

Ok, I'm not sure I follow. I read your solution in post #21, and that one doesn't seem to work as a solution, but once I got to #27 (where I suspect your solution became fine tuned?) I got rather bogged down in the text. Could you state your solution a bit more concisely?

You have to bear in mind in the one counter situation if the counter is never chosen, all prisoners will be dead before the counter can make an assumption.

Well... if the counter is never chosen, then they're all dead or imprisoned anyway, since it will never be true that the counter himself entered the room, and nobody can correctly assert that all 100 prisoners visited the room!

This is why your idea and all the others are dismissed, not because it isn't likely, but because it does not meet the criteria of the experiment

Oh, maybe you thought I was suggesting that my solution was to wait 5 years and say "ok, we've all been to the room!"? That's not really a solution as you point out-- I was just curious about the distribution of liklihood in the counter situation versus how long it actually took to get everyone into the room. The counter solution is guaranteed to work *eventually* assuming that prisoner selection is truly random (meaning that each prisoner has an equal chance of being chosen on any given day).

Well, ok, it also assumes a wealth of other things like:
- the prisoners don't die
- the prisoners can't escape by any other means than correctly making the assertion that they've all been to the living room
- the prisoners never forget whether they've been in the room or not
- the warden keeps perfect records
- the warden is true to his word
- the lightswitch never breaks
- etc.

read the quote again as for why and how this leads to the only conclusion that a single counter or 99 counters is not viable, only all counters will be 100%. Run your tests with that, is it more or less viable?

I'll be happy to try and run a simulation, but I would need to understand what the method you're suggesting is.

I'm inclined to agree with pig in post #13, or at least trust that his suggestion might be better on an average case. But it's kinda trickier to write a simulator for that solution, so I sort of left it alone.

DaveE

 

[Schrodinger's Dog]

Ok, I'm not sure I follow. I read your solution in post #21, and that one doesn't seem to work as a solution, but once I got to #27 (where I suspect your solution became fine tuned?) I got rather bogged down in the text. Could you state your solution a bit more concisely?
Well... if the counter is never chosen, then they're all dead or imprisoned anyway, since it will never be true that the counter himself entered the room, and nobody can correctly assert that all 100 prisoners visited the room!
Oh, maybe you thought I was suggesting that my solution was to wait 5 years and say "ok, we've all been to the room!"? That's not really a solution as you point out-- I was just curious about the distribution of liklihood in the counter situation versus how long it actually took to get everyone into the room. The counter solution is guaranteed to work *eventually* assuming that prisoner selection is truly random (meaning that each prisoner has an equal chance of being chosen on any given day).

Well, ok, it also assumes a wealth of other things like:
- the prisoners don't die
- the prisoners can't escape by any other means than correctly making the assertion that they've all been to the living room
- the prisoners never forget whether they've been in the room or not
- the warden keeps perfect records
- the warden is true to his word
- the lightswitch never breaks
- etc.
I'll be happy to try and run a simulation, but I would need to understand what the method you're suggesting is.

I'm inclined to agree with pig in post #13, or at least trust that his suggestion might be better on an average case. But it's kinda trickier to write a simulator for that solution, so I sort of left it alone.

DaveE

It assumes reality.

Trust the experts: do both: my all counters and one counter. See what you get? The counter depends only on being the person who is the first to reach the conclusion, but also takes into account the five year probability of 1 in a million of being wrong, this is the only way that you can achieve 100% and the only way you can satisfy the original conditions. You have to be 100% sure and it needs to be optimised so try writing both into the equation: does the five year on it's own work better on average than the 100 counters, which works the best 100 counters or five years? or both? Considering reality?