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.