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

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?

Related General Discussion News on Phys.org
AKG
Homework Helper
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.

AKG said:
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
Staff Emeritus
Gold Member
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.

Kurdt said:
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!

NeutronStar said:
...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
Staff Emeritus
Gold Member
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.

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.

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
Staff Emeritus
Gold Member
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.

Kurdt said:
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
Staff Emeritus
Gold Member
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.

Last edited:
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.

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

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?

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.

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

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

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?

Last edited:
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?

Last edited:
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?

Last edited:
cristo
Staff Emeritus
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?

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.

Last edited: