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 :biggrin: )

[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 -- :wink:

[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. :wink:


This is my program (krme.curvedspaces.com/prog/prison.zip), 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]

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. :frown: Prison is rough for light bulbs.

A pin-up (http://bulbcollector.com/gateway/Incandescent_Lamps/Carbon_Filament/1901-1960/Shelby/image/c0141.jpg&img=&tt=) 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.:smile:

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 :smile: 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 :smile:

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 :eek:

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 :smile:

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 :eek:

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 sytem 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 :smile: 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 in to 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:wink::smile: and the man:smile: because I am the man:wink::smile:.

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 sorta 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 sorta 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?

[davee123]

Trust the experts: do both: my all counters and one counter. See what you get?

Ok, I still don't understand what your method is-- could you explain it a little more clearly?

It seems like you're saying you leave the switch on or off depending on:

1) if it was up when you entered
2) if you've been in the room before

If it was UP and you HAVE been in before, then you flip DOWN
If it was UP and you have NOT been in before, then you flip DOWN
If it was DOWN and you HAVE been in before, then you flip UP
If it was DOWN and you have NOT been in before, then you flip DOWN

And when any one prisoner has seen 50 consecutive *downs*, they make the assertion that they've all been to the room.

If that's the method you're proposing, it won't work. One example of how not: if the first 200 (or whatever) picks are prisoners #1, #2, #1, #2, #1, #2, etc, then:

Day 1 - Prisoner 1 - flips DOWN
Day 2 - Prisoner 2 - flips DOWN
Day 3 - Prisoner 1 - flips DOWN
Day 4 - Prisoner 2 - flips UP
Day 5 - Prisoner 1 - flips DOWN
Day 6 - Prisoner 2 - flips UP
Day 7 - Prisoner 1 - flips DOWN
Day 8 - Prisoner 2 - flips UP
Day 9 - Prisoner 1 - flips DOWN
Day 10 - Prisoner 2 - flips UP
etc.

So, by day 100, prisoner #2 has seen 50 consecutive DOWN's, even though only 2 prisoners have ever been to the room, and incorrectly asserts that everyone's been to the room.

But maybe I'm missing something about your proposed system...

DaveE

[moose]

Kurdt, I sincerely hope that you are joking with your posts. You know how low the odds are that if you have 100 distinc things, that they all get chosen with 100 choosings? The probability that the same thing gets chosen twice IN A ROW, is 1 in 100^2, but not just twice in a set of 100. Let's narrow this set down to a set of 3 prisoners.
A,B,C
Here are the ways they can be chosen.
A,A,A A,A,B A,A,C A,B,A A,B,B A,B,C A,C,A A,C,B A,C,C

B,A,A B,A,B B,A,C B,B,A B,B,B B,B,C B,C,A B,C,B B,C,C

C,A,A C,A,B C,A,C C,B,A C,B,B C,B,C C,C,A C,C,B C,C,C

That means 3^3 different ways, or in the prisoners case 100^100 different ways. Here, the probability that ALL THREE are chosen in the first three days is 6/27 = 2/9
A,B,C A,C,B B,A,C B,C,A C,A,B C,B,A

So.... Are you tired?

[grant9076]

I am not sure but think that this might work (I hope).
One prisoner (leader) will flip the switch off and is the only one allowed to do so.
For the other 99, each one is allowed to turn the switch on once and only once and is not allowed to turn it off (as stated before). This way, when the counter (leader) sees that the light is on, he will know that someone new entered the room since the last time that he went there. After he has turned off the switch for the 99th time, he can make his announcement and set everyone free.

[Schrodinger's Dog]

Ok, I still don't understand what your method is-- could you explain it a little more clearly?

It seems like you're saying you leave the switch on or off depending on:

1) if it was up when you entered
2) if you've been in the room before

If it was UP and you HAVE been in before, then you flip DOWN
If it was UP and you have NOT been in before, then you flip DOWN
If it was DOWN and you HAVE been in before, then you flip UP
If it was DOWN and you have NOT been in before, then you flip DOWN

And when any one prisoner has seen 50 consecutive *downs*, they make the assertion that they've all been to the room.

If that's the method you're proposing, it won't work. One example of how not: if the first 200 (or whatever) picks are prisoners #1, #2, #1, #2, #1, #2, etc, then:

Day 1 - Prisoner 1 - flips DOWN
Day 2 - Prisoner 2 - flips DOWN
Day 3 - Prisoner 1 - flips DOWN
Day 4 - Prisoner 2 - flips UP
Day 5 - Prisoner 1 - flips DOWN
Day 6 - Prisoner 2 - flips UP
Day 7 - Prisoner 1 - flips DOWN
Day 8 - Prisoner 2 - flips UP
Day 9 - Prisoner 1 - flips DOWN
Day 10 - Prisoner 2 - flips UP
etc.

So, by day 100, prisoner #2 has seen 50 consecutive DOWN's, even though only 2 prisoners have ever been to the room, and incorrectly asserts that everyone's been to the room.

But maybe I'm missing something about your proposed system...

DaveE


I changed my idea from that to the original one plus 100 counters. So in essence it's just that, after thinking about it I thought that the original solution plus 100 counters would be optimised, then when I saw the 5 years solution I thought both together would be optimised, ie if you were "lucky" you'd be out before 5 years.

Quite apart from the fact that the prisoner would know by counting how may times he's been in and so would not assert that all had been in as probability would not be anywhere near 100%, but anyway that's beside the point.

[davee123]

I changed my idea from that to the original one plus 100 counters. So in essence it's just that, after thinking about it I thought that the original solution plus 100 counters would be optimised, then when I saw the 5 years solution I thought both together would be optimised, ie if you were "lucky" you'd be out before 5 years.

Ok, I've gone through and read and re-read each of your posts now, and now I'm even MORE confused. You talk about assigning people as a "foil" (whatever that means) and as counters (whatever that means in your system since everyone's always a counter?) and you talk about a "pattern"? And someone who will have been in the most?

Anyway, I'm interested in understanding your method, but I seriously have no clue what you're talking about. Could you just explain your method start to finish, as though you hadn't posted anything on the subject already?

DaveE

[Schrodinger's Dog]

Ok, I've gone through and read and re-read each of your posts now, and now I'm even MORE confused. You talk about assigning people as a "foil" (whatever that means) and as counters (whatever that means in your system since everyone's always a counter?) and you talk about a "pattern"? And someone who will have been in the most?

Anyway, I'm interested in understanding your method, but I seriously have no clue what you're talking about. Could you just explain your method start to finish, as though you hadn't posted anything on the subject already?

DaveE

Ok sorry the method is in post 2, but instead of using 1 counter everyone is a counter so that the first person to get to 100 downs announces to the prison guards that they should go free, if however this takes longer than five years then they call the warden anyway and go free on the grounds of probability, this may not be exactly 100% either but I think given that choice I'd go for it or you can just say the 100 counters, or you can just say the length of time it takes all of them but 1 to die, either way it is a solution which is 100%.

I'm also discussing it in the set theory section, but I'm getting nowhere there either. Apparently no one accepts that the second post solution is wrong for the reasons given by the man who originally set the question. I don't make the rules.

Any solution given on the internet in the link is fine as well, but in conjunction with 100 counters. Or in other words randomised counter. What is the result if anyone is a counter? It's likely to be much quicker no?

[davee123]

Ok sorry the method is in post 2, but instead of using 1 counter everyone is a counter so that the first person to get to 100 downs announces to the prison guards that they should go free

Ok, this won't work. Let me summarize what you're saying to make sure that I've gotten it correctly:

- If a prisoner sees the switch DOWN, he adds it to his personal tally, T.
- If a prisoner sees the switch UP, he resets his personal T value to 0.
- If a prisoner has been in the room before, he flips the switch DOWN.
- If a prisoner has NOT been in the room before, he flips the switch UP.
- If, for any prisoner, T >= 99, he announces that all of the prisoners have visited the room.

Ok, this is wrong, but is *likely* to work. It can be fooled in an unlikely case. For example:

Let's suppose that by day 1600, prisoner #66 has never been selected. Unlikely, but possible. In my above simulations, you can see it actually DID happen once out of 100,000 tries-- that is, by the 1600th day, one person really had NOT been to the room.

Now, let's say everyone else has been to the room a lot-- they've all been in as of day 400. And that's actually reasonably likely. Not outrageously likely, but possible. That means between day 401 and day 1600, the light has not EVER been on, and everyone's personal T values are only getting bigger.

The next unlikely event is that prisoner #42 is selected 100 times between day 401 and 1600. Certainly possible, although not really all that likely. Prisoner #42's T count is at 100, and decides that everyone has visited the room. But really, prisoner #66 still has never been there. So #42 ruins it for everyone, and they all die.

Basically, your method appears to be very similar to "wait a long time, and we're probably safe". Except, instead of setting a preset limit, you're looking for an unlikely event-- IE that a single prisoner has seen 100 "downs" in a row. You could just as easily have suggested "after you've been selected 10 consecutive days in a row, you're probably safe". It's an unlikely event that will eventually happen, so the system is LIKELY to work, but MAY not.

If you're interested, a simulation of the above method, run 1000 times is:

Avg: 7685.02 days

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: 39 times
7000-7999 days: 798 times
8000-8999 days: 163 times

So, your average is about 21 years, which is admittedly quicker than the single counter method, but it's not guaranteed to work, whereas the single counter method IS guaranteed to work with 100% accuracy.

if however this takes longer than five years then they call the warden anyway and go free on the grounds of probability, this may not be exactly 100% either but I think given that choice I'd go for it or you can just say the 100 counters, or you can just say the length of time it takes all of them but 1 to die, either way it is a solution which is 100%.

I'd suggest looking at pig's solution in post #13 of this thread. His proposed method sounds like it would result in a faster *average* time, but a slower worst-case time. I'm tempted to try it with several values in simulation, but it's kind tricky to do.

I'm also discussing it in the set theory section, but I'm getting nowhere there either. Apparently no one accepts that the second post solution is wrong for the reasons given by the man who originally set the question. I don't make the rules.

Why do you think the 2nd post solution is wrong? The single counter solution IS a correct solution with 100% accuracy, but a very bad "average time to success" rate, and a possibility of infinite length at infentesimal probability.

Are you proposing that it's not 100% accurate because there's an infintesimal chance that it won't ever reach a conclusion? I'd disagree if so, since "no conclusion" is just as accurate as a correct one. It's only an INCORRECT conclusion that counts against you.

What is the result if anyone is a counter? It's likely to be much quicker no?

It's likely that if you assign "whoever is assigned to the living room on the *second* day" as the counter, that you'll decrease your average time by, I dunno, probably about 50 days. I should clarify that that's about 50 days faster than if you assigned a specific person as the counter BEFORE the 'game' starts. But that's hardly significant-- something like a 0.5% speedup. And really, not even a percentage speedup, because it's a fixed amount of time that it saves you.

DaveE

[Schrodinger's Dog]

By if anyones the counter I mean the counter is everyone, whoever sees 100 downs first calls the warden, Do you see what I mean now? You follow any system that leads to 100 down eventually, the person who does whatever can be a single person but the counter should be anyone.

It's not correct and you can use my method with any of the answers that involves a counter and I bet you'll end up with a quicker time, it's not correct because you have to find the best solution or to opimise the time, since the probability is that in 3 years you'll have had everyone in the room this is one solution although not 100% it is the solution the maths professor was looking for, I guess if you wait five years your probably looking at a 1 in a ?trillion chance of failure which to all intense and purposes is close enough to 100% so as to not warrant remark. The answer that optimises both however and returns 100% is any method you like but with infinite counters, to stop the possibility that the counter is never chosen which obviously is not 100%.

3 years is alot faster than an average of 26 years, but it is not 100%, where as the no fixed counter method is 100%, so a combination of both IMO is optimised, if you get lucky then you may be out before the 3 years is up.

Post 13 assumes that x will be chosen at all as well so it falls down here too, the only solution that is 100% fool proof is any method you like as long as it doesn't involve a single counter or introduces the chance of no solution till everyone but 1 is dead. With 100 counters. One involves a three year stay and a slim possibility of being wrong the other involves a probably longer stay but a 100% possibility of being right.

[davee123]

By if anyones the counter I mean the counter is everyone, whoever sees 100 downs first calls the warden, Do you see what I mean now? You follow any system that leads to 100 down eventually, the person who does whatever can be a single person but the counter should be anyone.

So, did I summarize your system correctly, then?

It's not correct and you can use my method with any of the answers that involves a counter and I bet you'll end up with a quicker time, it's not correct because you have to find the best solution or to opimise the time

Ok, here's the problem. You're assuming that an "optimal" answer can sacrifice accuracy, and that's not correct. You're speaking a different language. Everyone else is looking for *perfect* solutions, you're apparently looking for probable ones.

An optimal solution MUST be 100% perfectly accurate, not capable of failure even at 1 in a googolplex probability. That's because it has to be:

1) a solution (meaning NO chance for error)
2) optimal (meaning NO other solution has a faster average time)

For example, here's a solution which is correct, but not optimal:

----------------------
The "flizmar" method:

One prisoner is designated as the counter. The remainder of prisoners are designated countees. Each time a countee enters the room, they will not touch the switch if it is on. If the switch is off, they will switch it on ONLY if they have done so 9 times or less. This means that eventually, each countee will have flipped the switch 10 times. If the counter enters the room and the switch is on, they add 1 to their tally (which starts at 0), and turns the switch off. The counter will always flip the switch down when he leaves the room. When the counter's tally reaches 990, he may guarantee that all 100 prisoners have visited the room, and make the assertion.
----------------------

So... That's correct, but not optimal. It is GUARANTEED to get a correct answer, it's just that the average time is about 100,000 days. If I was willing to go through great mathematical lengths, I could PROVE that the average time for this method is LONGER than the average time for the "AKG" method, meaning that this solution is definitely NOT optimal.

However, it says nothing about whether the "AKG" method is optimal. All we can prove is that the "flizmar" method is NOT optimal. As I've mentioned a couple times, check out pig's solution he started proposing in post #13 of this thread. It is another valid solution, but I'm not sure if it's optimal. Only way to test is to figure out what its average time would be, and see how it compares to the "AKG" method, which is the fastest proven solution we know about.

Post 13 assumes that x will be chosen at all as well so it falls down here too, the only solution that is 100% fool proof is any method you like as long as it doesn't involve a single counter or introduces the chance of no solution till everyone but 1 is dead. With 100 counters. One involves a three year stay and a slim possibility of being wrong the other involves a probably longer stay but a 100% possibility of being right.

Ok, I think you're putting in too much reality into the problem. For the sake of the problem, prisoners don't die, they're 100% loyal to the system, the lightswitch never breaks, etc.

For all intents and purposes, pretend this has nothing to do with prisoners and light switches. Let's instead pretend that this is a computer problem:

"Bob the hacker is hacking into the bank. In order to properly hack the system, Bob needs to verify that his virus has infected every single instance of the bank's 100 server processes. If even a single server process has not been infected, his hack attempt will be detected, and he will be sent to jail. If, however, all 100 servers are infected, then he may hack the system successfully.

In order to infect a server process, Bob sends "infect" commands to the bank, which are undetected, and may happen 1000's of times a second. Unfortuantely, Bob cannot control WHICH server process is accepting his infection commands. For all he knows, he may have infected the same server 20 times in a row-- the servers are infected randomly.

However, each time he sends an "infect" command, the server which is infected may flip a protected bit in reserve memory to "0" or "1". No other processes will be flipping this bit, and infected servers flip can flip the bit ONLY when they receive "infect" commands. Bob can instigate rules about whether the infected server should flip the bit or not, and any infected server has the option of responding with the message that all 100 servers have been infected. But if it does so and is incorrect, he's detected!

How does Bob arrange the bit-flipping logic of the infected servers so that he won't get caught but can hack the system?"

Well, ok, it's strangely worded, but you get the idea. Essentially, at 1000 times per second, 10000 iterations (AKG's solution on average) is pathetic and insignificant-- 10 seconds. No problem. And the "flizmar" solution would be 100 seconds. Kinda long, but meh, what's a minute and 40 seconds? Not much.

In other words, ignore all the "real" constraints like prisoners dying and being bored and disloyal and impatient, and ignore all the stupid-but-real possibilities like "make scratches on the walls" or "we're willing to accept a 0.000001% chance of dying".

If you're going for a "pretty likely" solution, it's all a matter of how much is "pretty likely". If it's not 100%, it's not 100%, end of story.

DaveE

[Schrodinger's Dog]

So, did I summarize your system correctly, then?



Ok, here's the problem. You're assuming that an "optimal" answer can sacrifice accuracy, and that's not correct. You're speaking a different language. Everyone else is looking for *perfect* solutions, you're apparently looking for probable ones.

An optimal solution MUST be 100% perfectly accurate, not capable of failure even at 1 in a googolplex probability. That's because it has to be:

1) a solution (meaning NO chance for error)
2) optimal (meaning NO other solution has a faster average time)

For example, here's a solution which is correct, but not optimal:

----------------------
The "flizmar" method:

One prisoner is designated as the counter. The remainder of prisoners are designated countees. Each time a countee enters the room, they will not touch the switch if it is on. If the switch is off, they will switch it on ONLY if they have done so 9 times or less. This means that eventually, each countee will have flipped the switch 10 times. If the counter enters the room and the switch is on, they add 1 to their tally (which starts at 0), and turns the switch off. The counter will always flip the switch down when he leaves the room. When the counter's tally reaches 990, he may guarantee that all 100 prisoners have visited the room, and make the assertion.
----------------------

So... That's correct, but not optimal. It is GUARANTEED to get a correct answer, it's just that the average time is about 100,000 days. If I was willing to go through great mathematical lengths, I could PROVE that the average time for this method is LONGER than the average time for the "AKG" method, meaning that this solution is definitely NOT optimal.

However, it says nothing about whether the "AKG" method is optimal. All we can prove is that the "flizmar" method is NOT optimal. As I've mentioned a couple times, check out pig's solution he started proposing in post #13 of this thread. It is another valid solution, but I'm not sure if it's optimal. Only way to test is to figure out what its average time would be, and see how it compares to the "AKG" method, which is the fastest proven solution we know about.



Ok, I think you're putting in too much reality into the problem. For the sake of the problem, prisoners don't die, they're 100% loyal to the system, the lightswitch never breaks, etc.

For all intents and purposes, pretend this has nothing to do with prisoners and light switches. Let's instead pretend that this is a computer problem:

"Bob the hacker is hacking into the bank. In order to properly hack the system, Bob needs to verify that his virus has infected every single instance of the bank's 100 server processes. If even a single server process has not been infected, his hack attempt will be detected, and he will be sent to jail. If, however, all 100 servers are infected, then he may hack the system successfully.

In order to infect a server process, Bob sends "infect" commands to the bank, which are undetected, and may happen 1000's of times a second. Unfortuantely, Bob cannot control WHICH server process is accepting his infection commands. For all he knows, he may have infected the same server 20 times in a row-- the servers are infected randomly.

However, each time he sends an "infect" command, the server which is infected may flip a protected bit in reserve memory to "0" or "1". No other processes will be flipping this bit, and infected servers flip can flip the bit ONLY when they receive "infect" commands. Bob can instigate rules about whether the infected server should flip the bit or not, and any infected server has the option of responding with the message that all 100 servers have been infected. But if it does so and is incorrect, he's detected!

How does Bob arrange the bit-flipping logic of the infected servers so that he won't get caught but can hack the system?"

Well, ok, it's strangely worded, but you get the idea. Essentially, at 1000 times per second, 10000 iterations (AKG's solution on average) is pathetic and insignificant-- 10 seconds. No problem. And the "flizmar" solution would be 100 seconds. Kinda long, but meh, what's a minute and 40 seconds? Not much.

In other words, ignore all the "real" constraints like prisoners dying and being bored and disloyal and impatient, and ignore all the stupid-but-real possibilities like "make scratches on the walls" or "we're willing to accept a 0.000001% chance of dying".

If you're going for a "pretty likely" solution, it's all a matter of how much is "pretty likely". If it's not 100%, it's not 100%, end of story.

DaveE


The human part of the equation is put in precisely to counter this, using Bayes theorem as I linked and explained you will be out with 1/1000000 chance of being wrong in 5 years or 1/1000 for 3 years. The point of the problems using "real" people is precisely to make simple mathematical solutions wrong, only if you know probability maths can you hope to get the right answer. If you're not happy with the tennants of the puzzle then there's not alot I can suggest accept you contact the proffessor and say he is wrong.

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

Personally I think the difference between being right and being optimally right is pretty important, but obviously no one else does. Although I'm sure the prisoners would happily ignore you too :smile:

Being 100% right though and in theory at least if you get lucky you'll be out sooner than 5 years, and having the option of working with probability and being out in 5 years sounds fine by me.

Ask Stuart Anderton?

Or buy the related book in which this appears?

I'm not trying to anoy anyone I just wanted to make people aware of the flaws in the solutions.

And suggest ways in which we could have both the 100% correct and optimal answers in one technically.

Isn't Amy Wong the flismar of oh no that's something different...smismar of Kif that's it.:smile:

[davee123]

The human part of the equation is put in precisely to counter this, using Bayes tehorem as I linked and explained you will be out with 1/1000000 chance of being wrong in 5 years or 1/1000 for 3 years. The point of the problems using "real" people is precisely to make simple mathematical solutions wrong, only if you know probability maths can you hope to get the right answer. If you're not happy with the tennants of the puzzle then there's not alot I can suggest accept you contact the proffessor and say he is wrong.

Ok-- maybe you're missing the sarcasm in there. The quoted answer that he's giving is intended to be silly. "Wait 5 years" is NOT an optimal solution by ANY means.

Personally I think the difference between being right and being optimally right is pretty important, but obviously no one else does.

Ok, the reason for that is you're being inaccurate. "right" and "optimally right" are NOT what you're talking about. You're talking about the difference between being "right" and being "reasonable". Your proposed method is NOT right, and is NOT objectively optimal. But it IS reasonable!

Being 100% right though and in theory at least if you get lucky you'll be out sooner than 5 years, and having the option of working with probability and being out in 5 years sounds fine by me.

Well, here's the problem:

By your method, you should wait 5 years, and then say "ok, we've all been in!". But why not wait 4 years and 364 days? Isn't that more optimal? Why not wait 4 years and 361 days? How on Earth are you going to objectively justify that 5 years is long enough or short enough to wait? What if one of the prisoners figures that he'll ignore you because 90% is good enough for him, so he waits 2 years instead? It's totally subjective.

None of these are solutions, they're just likely to work. As I pointed out before, "optimal solution" has two parameters: "optimal" and "solution".

I think everyone involved is happy to accept that your suggested method is LIKELY to work, and that if they were in the prisoner dillemma, they'd be HAPPY to accept it, because it would (in all probability) get them out sooner. But the entire reason this is a logic problem is that we're not looking for "reasonable", we're looking for "accurate". This isn't an excersize in social morality or personal tolerance-- it's an excersize in math and logic. If you'd like to discuss "what percent chance am I willing to accept that I'll die?", take it to the philosophy forum.

DaveE

[Schrodinger's Dog]

I only wanted to make a point about optimal and logic, what is logical is also optimal in reality,if we're talking hypothetically all the solutions are correct, but if I chose like the person who set the problem did, to say that this is not the optimal answer, but given the original parameters the solutions mentioned are not optimal or logical at least from real world perspective, if you think I'm being a pedant or that this amazing revelation that the one counter system or any other system that relies on chosing one person in a random situation is wrong given the original tennants of must be 100% correct fine, I have no problem with that.

He said this to make people think about the difference between logic and reality maybe, and that was my only intent, to make people think about Stuart Andertons and my answer. Obviously it was not welcome to point out the flaws and I apologise for offending anyone.

You do realise of course that the one counter method is not guaranteed for the reasons stated, ie if it is truly random then this is not 100% sure. But I guess it's beside the point if it's simply a logic puzzle, as they decide to murder Alice for keeping them in jail for this time then use a combination of the most logical and most optimal solutions? Is that fair to say? Does it make it more or less logical, the philosophy thread beckons :smile:

The truth is with no fixed counter and the Bayesian solution eventually you will be 100% correct, even if it does take x years and some pretty complicated p math.

So in effect the only correct solution with a time limit I suppose is that you wait until everyone is dead but you and then wait to see if your chosen 100 times with the paramaters of putting the switches up everytime your in, so that it destroys the always down solution, of course if your not picked on one day you can start again, then you are 100% correct, assuming you don't die before you see 100 ups; or you could just hedge your bets and go for 5 years. Or you could use the one counter method in combination and forgo the chance that you may be wrong? Of course this is wrong logically as no one ever dies, but then is that really that logical?

[Hurkyl]

For fun, I worked out a theorem.

We already know that it is impossible to devise a system where the prisoners can guarantee they'll be released after N days.

This can be strengthened: it is impossible to devise a system where the prisoners will secure a release after N days in every scenario where they have all been picked at least once.



Anyways, Schrodinger's Dog, I think the whole problem is that you changed the problem without telling people. When people are solving the original puzzle set forth, it's inappropriate to criticize them because they weren't solving the variation that you invented, especially because I don't think you've explicitly stated the problem in which you're interested.

[Schrodinger's Dog]

For fun, I worked out a theorem.

We already know that it is impossible to devise a system where the prisoners can guarantee they'll be released after N days.

This can be strengthened: it is impossible to devise a system where the prisoners will secure a release after N days in every scenario where they have all been picked at least once.



Anyways, Schrodinger's Dog, I think the whole problem is that you changed the problem without telling people. When people are solving the original puzzle set forth, it's inappropriate to criticize them because they weren't solving the variation that you invented, especially because I don't think you've explicitly stated the problem in which you're interested.


That's why I preceeded both posts with the new problem, if people didn't read it that's their problem surely? The professor said I like these problems but their not right because of a, Anderton asked why?

Because the problem was set so that it could only be answered in a realistic way.

So the formula in my book is the bayesian model, I then went on to say that on a technicality that is wrong too, and explained why. I also outlined a time based solution,and a non time based solution, but it was wasted as no one read the links.

Essentially because, no one had read the original problems solution as layed out by the man who wrote it I was talking to myself, so it was kind of like, essentially you were all wrong because of x, but no matter what I said no one would accept it, not even when the person who originally set it out said yeah they're right, but what I wanted was something like x.


I wrongly obviously thought it might be a bit of fun to bring this to peoples attention, I truly am sorry that I bothered. Sorry but it's not my fault if people don't understand what I mean because they are too lazy to read the links provided; I assumed people knew what I meant, but obviously this is not the case, I have realised that in general though people are lazy and will completely miss the whole idea of your proposition if you put up links, so at least this has been beneficial in my understanding why I had to repeat myself about 10 times.

[davee123]

I don't mean to be rude, but you've practically accused me (and others) of not reading the links you posted to (which I did read!), and accused me of not understanding what you were talking about (which I didn't!) merely because I was being lazy. However, I happen to consider myself to have been very persistant and forgiving in this thread, because I felt that you weren't doing a good job explaining yourself, and I thought maybe you were on to something with your "everyone's a counter" theory, so I was very anxious to hear more.

That's why I preceeded both posts with the new problem, if people didn't read it that's their problem surely?

Ok I don't get it. I DID read what you posted, AND what you linked to, multiple times. The problem listed at the beginning of this thread was:

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?

The problem that you posted later was a rewording of the above:

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

Now, look at each question VERY CLOSELY:

From the first problem:
"what plan should they agree on, so that eventually, someone will make a correct assertion?"

From the second problem:
"What plan should they agree on, so that eventually, someone will make a correct assertion?"

The question is actually NOT about getting released at all! The question is about making a correct assertion. Plus, note the authors' use of the word "eventually", underscoring that yes, it may take a LONG time.

Now, admittedly, the second thing you posted asked ANOTHER question, which is "what is the optimal solution?", and posited (incorrectly) that "wait 3 years" was a solution, which it is NOT.

So, everyone involved in our discussion at the PF was answering "what is a solution?" and "what is the optimal solution?", and people were NOT answering "what is the best reasonable solution?", which is apparently what you thought everyone ought to be discussing. It wasn't until late in the discussion that I finally caught on that that's what you were really trying to get at, at which point I tried to offer you the distinction between what you were saying and what everyone else was saying.

Note that at the beginning, you said, in response to my analysis of waiting a fixed length of time:


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.

Now, I was rather lost by your phrasing, but I verly clearly got the impression that you were saying "you can't be 100% certain if you wait for 5 years", which is totally true.

However, later, you said something totally contradictory:

the method is in post 2, but instead of using 1 counter everyone is a counter so that the first person to get to 100 downs announces to the prison guards that they should go free, if however this takes longer than five years then they call the warden anyway and go free on the grounds of probability, this may not be exactly 100% either but I think given that choice I'd go for it or you can just say the 100 counters, or you can just say the length of time it takes all of them but 1 to die, either way it is a solution which is 100%.

Let me reiterate the important contradictory parts:
"this may not be exactly 100%"
"either way it is a solution which is 100%"

So, you were looking for a 100% accurate solution... but... you weren't looking for a 100% accurate solution? I was lost. But at least you finally made it clear to me that by "100%" I think you meant "99.9999999999999999999999999994%"

The professor said I like these problems but their not right because of a, Anderton asked why?

Ok, you keep saying this, but that's not what I see when I read this. This guy (Alexander Bogomolny, who's a professor I guess?) answered with the following solution:

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.

Then, Alexander was replied to by Stuart Andersen, stating:

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.

So, Stuart is saying that Alexander's solution was CORRECT (and yes, it actually was a solution), but that it is not an OPTIMAL solution. Alexander's solution is clearly NOT an optimal solution because (as he proceeds to try and proove mathematically), Stuart's solution is faster.

However, Stuart continues in *playful jest* suggesting that they should just wait 5 years and probably get out much faster. Note that this is NOT a solution to the problem, and therefore, not an "optimal solution", because it is not a solution. It's also not "optimal" because "optimal" in this case is subjective.

Because the problem was set so that it could only be answered in a realistic way.

Please re-read it again, because the problem is very clearly stipulating that the goal is NOT for the prisoners to be released, but instead to make a correct assertion that all 100 prisoners have been in the room. Further, it also does NOT suggest that you need an optimal solution, despite the fact that I agree it's an interesting question, and it's been addressed in this thread already (by pig as early as post #13) and also in Stuart Anderson's reply in the context you quoted.

Essentially because, no one had read the original problems solution as layed out by the man who wrote it I was talking to myself

I have to say, I simply didn't understand a lot of what you were saying. It seems like you were doing a lot of thinking-while-typing, getting ahead of your words and communicating in tidbits and phrases that didn't make sense to anyone because you were assuming everyone understood all the tidbits. And it seemed like you didn't want to slow down for a minute and explain things all the way through. Further proof of that is in the fact that 14/15 of your posts in this thread were later edited by you.

If it seems like people aren't on the same page as you are, please, take a while to organize your thoughts, and then write them out completely.

I wrongly obviously thought it might be a bit of fun to bring this to peoples attention,

Actually, I think it's quite a lot of fun to discuss things like this, but seriously, you've got to put the time in to make sure people understand your ideas. Plus, you've also got to seperate your ideas out. If you're talking about "solutions" versus "strategies", be sure to be clear about it. When you stop talking about one and start talking about the other, be sure to draw the distinction.

it's not my fault if people don't understand what I mean because they are too lazy to read the links provided

As I stated, I DID read the links you provided as well as nearly the entire thread that was secondarily linked to on the "CTK Exchange". And I still didn't understand what you were saying, which I why I asked you three times to explain what you were talking about.

However, I will agree that in general people ARE lazy. So if you want to discuss things with them, especially in an online format, YOU'VE got to be the one to put in the time make sure you're clear and thorough.

DaveE

[Craigh00000]

The answer to the original post is obvious. These are after all prisoners and can't really be expected to tell the truth. It does not state that the warden keeps track of which prisoners are chosen. Therefore, The plan they decided on was after 101 days, they all agree that they have been in the room.:devil: :biggrin:

[Wizardsblade]

I think I found a way to optimize the time it takes to be sure all 100 prisoners have been in the room. (For simplicity though I’m going to use 128 prisoners but this is easily simplified, just not easily explained) This gets a little complicated so Ill do my best. This idea is based off another posters idea. This idea uses a binary technique. There will be 8 “levels” in this method and we will use the idea of handing off counters (just imaginary objects to keep track of how far along hey are.) Only designated people can “keep” a counter. Once a designated person has 2 counters they can hand off their counter. Anyone can “take” a counter that is not supposed to “keep” the counter (this gives them an extra counter to keep track of.) First off there are 8 designated days 1 for each level. One person is the level 1 keeper. The level 1 keeper and 1 another designated person are level 2 keepers. Those 2 plus 2 others are level 3 keepers… Those 32 plus 32 more are level 7 keepers. Everyone is given a level 8 counter.

On the first day of the cycle if the random person has not given away their level 8 counter they turn on the light. If they have they leave the light off.

On the second day of the cycle:
If the light is on and the prisoner is a level (L) 7 keeper, he keeps the L7 counter and turns off the light.
If the L7 keeper now has 2 L8 counters he leaves the light on.
If the light is on and the prisoner is not a L7 keeper they “take” the L8 counter for later and turns off the light.
If the light is off the prisoners do nothing.

On the third day of the cycle:
If the light is on and the prisoner is a L6 keeper, he keeps the L6 counter and turns off the light.
If the L6 keeper now has 2 L7 counters he leaves the light on.
If the light is on and the prisoner is not a L6 keeper they “take” the L7 counter for later and turns off the light.
If the light is off the prisoners do nothing.

On the (9-x) th day of the cycle: (this is tricky because on day 4 x=5 ect.)
If the light is on and the prisoner is a Lx keeper, he keeps the Lx counter and turns off the light.
If the Lx keeper now has 2 L(x+1) counter he leaves the light on.
If the light is on and the prisoner is not a Lx keeper they “take” the L(x+1) counter for later and turns off the light.
If the light is off the prisoners do nothing.

After 8 days the cycle starts all over again with day 1.

When the designated level 1 keeper has both his level 2 counters he can declare all 128 have been in the room.

(Let me know if I need to explain better)

Making this for only 100 people you simply give 28 prisoners an extra L8 counter. If given to the correct people this can greatly reduce the amount of handoffs that need to take place.

[AngeloG]

Uhh, the plan will be before anything the first person picked will assert that they know not everyone has gone. Thus, their assertion is correct.

[vuk]

Wizardsblade, could you explain your algorithm better? For instance:
"If the light is on and the prisoner is not a L7 keeper they “take” the L8 counter for later and turns off the light."
Who are they?

What if a designated L3 keeper (keeps one L4 counter) was randomly choosen to enter the room 8 times, and the ninth time he follows an L8 level prisoner choosen for the first time to enter the room?

[rewebster]

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?

At this meeting, 100 cards are made, numbered from 1 to 100, and passed out to each prisoner. When they go to the central room, they leave the card. When all 100 cards are there, that last person to place in that missing, last card, calls the warden.

[blade_922]

okay i registered just there. I think the answer is pretty obvious. :p its got nothing to do with a lightbulb

Each time somebody goes in there, they take off there top and leave it in the living room. And if they return for a second third or fourth time they still leave it there. If any prisoner ever returns more than once they dont do anything, just leave there top there. Everytime someone returns they count the number of tops in the living room. Once someone who hasnt been in there counts 99 tops + takes off there own top then that means all 100 have visited. creative thinking eh? :p

[BobG]

At this meeting, 100 cards are made, numbered from 1 to 100, and passed out to each prisoner. When they go to the central room, they leave the card. When all 100 cards are there, that last person to place in that missing, last card, calls the warden.

okay i registered just there. I think the answer is pretty obvious. :p its got nothing to do with a lightbulb

Each time somebody goes in there, they take off there top and leave it in the living room. And if they return for a second third or fourth time they still leave it there. If any prisoner ever returns more than once they dont do anything, just leave there top there. Everytime someone returns they count the number of tops in the living room. Once someone who hasnt been in there counts 99 tops + takes off there own top then that means all 100 have visited. creative thinking eh? :p

The only means of communication is the light bulb, so both solutions are wrong.

Interesting discussion. In deciding whether the 99.999% probability or the 100% single counter method is 'best', consider that it only took 19 years for Andy Dufrene to tunnel out of Shawshank with a 6" rock hammer. :rofl: (I just happened to watch that movie on TV today)

This is an old problem, but I'd never considered how long it would take for the 'correct' solution to pan out. Time puts a whole new spin on the problem.

[Strilanc]

I saw an interesting solution to this problem. You consider turning on the light bulb as depositing souls and when one prisoner has all the souls he announces. Then a series of periods is defined, where the value of the light bulb is 2^n souls.

Initially, all prisoners have one soul. If they enter the room and there is no soul (the light bulb is off) they deposit their soul. Otherwise they take the soul and hold on to both until the next period starts. During the second period the light bulb is worth two souls and prisoners with two souls deposit them/take them. This continues until it is likely that one prisoner has all the souls.

If no one announces, the cycle of periods starts over. I don't remember the length of each period, but the estimated escape time was much better than the single counter scenario.

[Macc410]

It's quite simple really. Since all the prisoners can meet together and discuss whatever they want before the pickings, I decided to make them discuss their plan. Well what happens is that they tell eachother that when thy go into the room they will mark their initials onto the wall in the room. To make sure that the guards do not see them doing this they will turn off the light and then mark the wall with whatever they have at hand whether it be fingernails or whatever. In the even that a person has the same initials as another person then he/she will just mark a line under those intials. If a person gets picked multiple times the prisoner will not do anything to the wall. Every time someone goes into the room they will check the wall to see how many intials are on the wall. When someone goes in and see all 100 initials on the wall they will then say that all 100 prisoners have been in this room. This process can take any amount of days between 100 and beyond with there being no limit tohow many times a prisoner can be picked. resulting in some prisoners not being picked for a possibly long time. But in the end once all 100 HAVE been picked then the next person to go in WILL know that all 100 have been picked.

[davee123]

when thy go into the room they will mark their initials onto the wall in the room.

Nope, disallowed. They have two options when they are in the room:
1) Toggle light
2) Make the assertion

That's it. No writing initials, no tapping in morse code, no removing clothing, no nothing, apart from toggling the light and making the assertion. I suppose it's possible that they aren't even allowed to breathe while in the room (they just can't stay in very long). From the original problem:

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

Otherwise, yeah, it's simple.

DaveE

[Macc410]

This is why I said they will turn off the light and then do it to remove any suspicion. If the guards cannot see what is going on then how will they stop them? Unless this is disallowed by the rules of the riddle and not necisarrily the guards rules then it is wrong.

[davee123]

Unless this is disallowed by the rules of the riddle and not necisarrily the guards rules then it is wrong.

Exactly. Rules of the riddle. The important parts of the riddle were that you have a light bulb (really a light switch) that you can flip, and you have to use that (and only that) to make the assertion on whether or not all the prisoners have visited the room.

For all intents and purposes, for the sake of the riddle, you can pretend that these stipulations were made:

1) The guards do not approve of the warden's decision, and will try at every opportunity to keep the prisoners from successfully making the assertion that all prisoners have been to the room.

2) In between inmate visits, guards can alter the room in any way they see fit EXCEPT that the switch MUST be in exactly the same position for a newly arrived prisoner as it was when the previous prisoner left.

3) The guards are allowed to listen while the prisoners develop their plan.

Dave

[Macc410]

Well in all i thought it was a pretty good answer but if it wasnt against the riddle rules then it could have possibly been right. But oh well ill try coming up with another answer later.

[thankz]

you almost gave me a shudder, completly forgot about this question but my answer has changed. i'd say each prisoner trys to mind meld with the light bulb while it wheels (see taylor-wheeler theory). o:)

[jdg812]

PLAN

#1 If light is ON, leader turns light OFF.
#2 If a prisoner sees light OFF for the first time, he turn light ON
#3 After the leader turned light OFF 99 times, he claims (100% sure) that all 100 prisoners have been to the room.

Note: If light is already OFF, leader does nothing. If light is already ON, prisoner does nothing. If prisoner sees light OFF for the second time, he does nothing.

[Kittel Knight]

PLAN

#1 If light is ON, leader turns light OFF.
#2 If a prisoner sees light OFF for the first time, he turn light ON
#3 After the leader turned light OFF 99 times, he claims (100% sure) that all 100 prisoners have been to the room.

Note: If light is already OFF, leader does nothing. If light is already ON, prisoner does nothing. If prisoner sees light OFF for the second time, he does nothing.


Well, this has been already written in post #2...

[jdg812]

Well, this has been already written in post #2...
Wow! I did not see...

[Sauk]

Q: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?

THE ANSWER IS SIMPLE!

During the planning phase, all of the prisoners get together IN THE CENTRAL LIVING ROOM.

Therefore, they would have all been in the room on day 1 and would be able to get out as soon as possible.

[phlegmy]

ok i've sat here for 10 mins thinking about this one.

so far the only way i can see of "solving" it is using probability
however i dont believe this is a valid solution as the question stipulates that the declaration must be 100%
and one thing i know about probability is that if i flip a coin 10^10000000000 times i cannot say 100% that it wont heads every time.

therfore the prisioners could spend infinity^infinity eons locked up and still not be sure 100%

so there must be a soln that does not rely on prob or silly invention
i think this one may drive me crazy

[Macc410]

I think I've figured out the answer. Since they all get to meet together before they go in their cells what they will do is they wil devise a plan where the person who's cell is closest to the room's entrance will be the person who'll know how many people have gone. what happens is even though at the time they may not know who is going to be closest until they receive their cells is that the person going by the cell and into the room with the bulb wil shout out his/her name while walking by. If the person has already gone then they will say nothing. The person in the cell closest will keep track of all the names called in one way or another and when all 100 have called out their names and finally the person closest goes after al names have been said he/she will tell the guards they all have went. Depending on how many days it takes for everyone to go then there is no possible way to tell exactly how many days before their final day in the facility.

[phlegmy]

assuming all prisoners can count the days:

each toggles the switch everyday
if your called on an odd day the switch should initally be on
if your called on an even day the switch should initally be off
if your called twice within 100 days you leave the light bulb as it is
alerting the next guy that someone was called twice by destroying the correspondence between odd-on even-off [we call this guy THE MASTER]

the next guy continues to alert everyone that its a bum deal by continuing to toggle the switch
all prisionsers will know that its bad because on/off dont match with the even odd days.

UNTILL the original guy who was called twice returns having counted at least 100 days since his last visit. he now restores order (off for odd days on for even days).

the system is reset
each prisioner again toggles the switch on for odd days off for even days
again, if one man is called twice within 100 days he leaves the switch destroying the order.[HE BECOMES THE MASTER]

finally when our man [the master] who restored the order returns, again having counted 100 days at least and seeing that odd/even days match with on/off he knows that no one prisioner has been called twice in the last 100 days. and seeing as there is only 100 prisioners this means that each prisioner must have been called at least once.

he declares this and is promplty taken out to the back of the pump house and shot!

now where do i collect my prize (probably at the back of the pump house?! :) )

[phlegmy]

also i note from my post above that by the time dude decalers that all prisioner have been at least once, it may be several years since the event actually occuring. but he does not know this, not 100%

[phlegmy]

also i just read akg's post #2 properly and i think if he and i were prisoners i'd rather go with his method!
28 years is easssyyy time

[spidey]

My Solution:

1. First prisoner who goes to central room acts as counter and he leaves the switch as it is i.e off
2. Different prisoner goes to central room turns the light on if it is switched off and he/she
should not turn it on/off from then, even he/she gets chance to enter central room again(goes to infinity)..
3. Different prisoner goes to central room leaves the light as it is, if it is switched on
4. So whenever the first prisoner gets chance to go to central room again,he will count 1 if
the light is switched on and make the switch off.
5. when the first prisoner who is counting gets 99,then he will tell that all 100 prisoners
have been to the central room

This method takes a long long time but will work. please tell me if there are any mistakes

[ty91011]

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.

I've done a script in PHP. Running 10000 Trials the results come out to:

Max: 14348
Min: 6780
Avg: 10010.3376

So this number is very close to 10000 which is correct even intuitively seeing that the counter person has to come back to the room 100 times at a rate of 1/100 of him being chosen. Equals to 100x100 = 10,000 days.

[aragorn1r]

Once a prisoner is called, he goes in and he can either turn the light on or off, it doesn't matter. Once he's done this, he'll kill himself. Since he can't be called again, the warden must call another person. That person will go in, and then kill himself. This will continue, for about 99 days, and on the 100th day the last person will enter and say, "all 100 have entered if you include me." Pretty gruesome, I know, but it works (I think).

[davee123]

Since he can't be called again, the warden must call another person.

I'm not sure that works-- I don't see anything in the OP that restricts the warden into choosing living prisoners:

Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room.

I suppose it would work if one assumed that a dead person was incapable of being a prisoner and was instead a "former prisoner".

DaveE

[The Chaz]

My Solution:

1. First prisoner who goes to central room acts as counter and he leaves the switch as it is i.e off
2. Different prisoner goes to central room turns the light on if it is switched off and he/she
should not turn it on/off from then, even he/she gets chance to enter central room again(goes to infinity)..
3. Different prisoner goes to central room leaves the light as it is, if it is switched on
4. So whenever the first prisoner gets chance to go to central room again,he will count 1 if
the light is switched on and make the switch off.
5. when the first prisoner who is counting gets 99,then he will tell that all 100 prisoners
have been to the central room

This method takes a long long time but will work. please tell me if there are any mistakes

There is a common mistake in many of these plans, namely the assumption that a prisoner will know that he is "first" (or WHO is first).

[aragorn1r]

Doesn't need to know if he's first, once he's been in the living room, he kills himself. This goes on for 100 days. The only person left at the last 100th day is the only one who will walk free.

[aragorn1r]

I'm not sure that works-- I don't see anything in the OP that restricts the warden into choosing living prisoners:



I suppose it would work if one assumed that a dead person was incapable of being a prisoner and was instead a "former prisoner".

DaveE

If he's dead, he's got to buried you know. It's not like you let him rot in his cell.

[davee123]

If he's dead, he's got to buried you know. It's not like you let him rot in his cell.

I figure they'll just cremate him and take his urn into the room.

DaveE

[markmcdo]

Begin with Phlegmy's #71 post of even/odd days for (say) 100 day intervals. The first repeat prisoner will reverse the order. The SECOND repeat prisoner becomes counter and begins "regular" (post #2) strategy, starting at the next 100 day (100 is probably not optimal) interval.
(There MUST be a second repeat prisoner by day 100).
This plan may need some work, but I like the odd/even idea......

[markmcdo]

To clarify, strategy is two parts: days 1-100 use even/odd method and designate Counter (second repeater);
days 101 till end is "regular" (post#2) strategy.
They won't know who Counter is, but they'll know who it ain't (them).
When the first second repeater leaves room, he resets to original even/odd days, so that any future second repeaters know they're not Counter.
Now if I could only figure out the average time till second repeater and.....

[stadevosyan]

English is not my first language so sorry for some mistakes

something isn't accurate with the problem. read this problem and there is some similarity between these 2 problems

The riddle: 100 prisoners. tomorrow will be stood by a line: the 100th one can see other 99, 99th other 98, 2nd-only first one and 1st can't see anybody. each of them will wear a hat either black or white, and nobody can know his color. the count of each color is unknown it can be 50bl 50wh or 100bl 0wh or 73bl 27wh etc., they have to say the color of their hat, using words "black" or "white" no other words and can't prompt others with the intonation. who says wrong will be killed. 1st will begin the 100th one then 99-98-97. . .-1
Q: Knowing all this what plan can they make at night for the tomorrow's issue in order to survive AT LEAST 99 prisoners???

[Snip!]

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.

I know this is an old thread, but it struck me that 'optimal' could be reached by combining more than one strategy. I saw good and other solutions in this thread, but hardly any cooperation between users to reach a more optimal solution.

I suggest a different strategy that happens for only the first 100 days: the first to come into the room switches on the light. The second person leaves the light on unless it is the same person who came in the room the first day. The 3rd person also leaves the light on unless he is the person who was there day one or day two. Same for the 4th, 5th, 6th, etc. In fact they all leave the light on UNTIL someone comes in for the second time while the light is on within those first 100 days. This person switches the light off and becomes the counter.
Once the light is off, the group has to wait for day 101 to indicate to people on later days that the first strategy has stopped working. From day 101 on I use the above AKG strategy. Anyone who was in the room and switched on the light during this first cycle does not switch the light on again, ever. This extra strategy gives the counter a head start. (It even gives the group the possibility, albeit a small one I agree, to get out in 100 days.)

Example: the first 30 people to go in the room leave the light switch on, because they all went in the room only once. Person 31 is in fact the person who went in day 8 so he switches off the light, so next persons know the chain is broken. Everyone now leaves the light off until day 101. Then they start the above AKG strategy with person 31 being the counter, having already 30 on his tally. Only 70 more to go. Without doing the math I think it's quicker to use this extra strategy.