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

[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 anyone 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 anyone 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 a lot 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 a lot 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

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.

 

[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 a lot 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 realize 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

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 realized 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 persistent 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 into make sure people understand your ideas. Plus, you've also got to separate 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]

Hey man. They are prisoners after all.

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.

 

[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 don't 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 don't 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. (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 each other 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, completely 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).

 

[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 don't 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 won't 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.