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?
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 )
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 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. :)
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.
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.
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.
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.
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.
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.
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.