23 Prisoners
I'm a big fan of logic puzzles, and I'm always looking for good ones...Here's one that I particularly enjoyed -- try it out on your next break from website building... (If you've already heard the answer, don't spoil it for everyone else! And don't just cheat by googling for the answer either ...
)
The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison there is a switch room which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. The switches are not connected to anything.
"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell."
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back."
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time any one of you may declare to me, 'We have all visited the switch room.'
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
The question is: What is the strategy the prisoners devise?
Have a good 4th of July holiday and be safe.
Brian
)The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison there is a switch room which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. The switches are not connected to anything.
"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell."
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back."
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time any one of you may declare to me, 'We have all visited the switch room.'
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
The question is: What is the strategy the prisoners devise?
Have a good 4th of July holiday and be safe.
Brian
Does it depend on how much of a risk they want to take?
Reply to this
Adam -
There is a solution that works for sure...so I'd have to say no, it doesn't depend on the degree of risk they want to take.
Brian
Reply to this
Do we know what position the switches start out at?
Reply to this
You can simplify the problem by assuming you do know the switches' starting position, but once you have that problem solved, it doesn't take too much more to extend the solution to the case that you don't know the starting position of the switches.
Brian
Reply to this
each prisoner can write their names on the walls after they visit the room
Reply to this
heres a summery of my sollution
Solution:
1) Select a spokesman. He sets a prisoner count of “0”
2) A switch is a counter, b switch is irrelevant.
3) Switch up is on. Down is off.
4) First prisoner must turn on switch a. if switch is on. Switch b.
5) If you are not the speaker and if switch a is off and you have not turned on switch a, then turn switch a on. If not switch b.
6) If the speaker sees switch a on then he turns it off and adds 1 to the prisoner count, If not he switches b.
7) When the count is 22 then the speaker may declare “We have all been in the room” safely.
Reply to this
There can be no spokesman, because there can be no further communication after the initial meeting. Unless there is one cell that can watch the rest, but I feel we are thinking too hard about it now.
Reply to this
There has to be one person who does the count. call him whatever you want.
call him the counter. I call him a speaker only cause he is the one who who know the count. I have prefected the formula and i know im right
heres a summery of my sollution
Solution:
1) A switch is a counter, b switch is irrelevant.
2) Select a spokesman. He sets a prisoner count of “0”
3) Switch up is on. Down is off.
4) Only the speaker can turn off switch "A".
5) First prisoner must turn on switch "A", Unless switch is already on then he switches "B".
6) If you are not the speaker and if switch "A" is off and you have not turned switch "A" on, then turn switch "A" on. If not switch "B".
7) If the speaker sees switch "A" on, then he turns it off and adds 1 to the prisoner count, If not he switches b.
8) When the count is 22 then the speaker may declare “We have all been in the room” safely.
Brian. Am I correct?
wlnelson@theluvband.com
http://www.theluvband.com/forums
Reply to this
William -
Yes, that's the solution. Nice job! A fun puzzle, eh?
One detail to refine is this: what if you do not know the starting positions of the switches? Your solution assumes that (in step 7) if the speaker sees switch "A" on, it means that one of the other prisoners has already been in the room and can be counted. But if the switch "A" starts in the on position, then there are a couple ways that the count can get off.
Brian
Reply to this
NO SOLUTION IS POSSIBLE, AND THE ONE YOU STATED IS INCORRECT.
If only we could assure that either 0 or 1 first-time visitors occurred between times of counter-guy visiting, but we can't. He only knows there were 0 new, or there were 1 or more new, but not how many.
To be totally safe, wait forever. Else, use some statistical combination of
1. raw amount of time,
2. the count (probably will stick too low),
3. amount of time or visits with no new visitors.
You could do statistics on this with the relative desirability of
1. alligators,
2. being in prison,
3. being free.
The jailer is a criminal (he doesn't have authority to release or to kill those he holds). He could easily lie in any fashion, besides.
Reply to this
R. D. Flowers -
Note that the end goal is to declare: 'We have all visited the switch room.' So, it's ok if someone has been to the room multiple times -- just so long as everyone has visited once. So, let's say the counter-guy has just been to the room, and so flips his counter switch "off." Then, say five prisioners come into the room, and each is on his/her first visit. The first of the five will flip the counter switch to "on", and the rest will flip the other switch back and forth. When the counter-guy returns, he will only count 1 new visitor. But that's ok, b/c the game continues...Eventually, every prisoner will get their chance to flip the counter switch to "on."
But I agree with you that this jailer is overstepping his authority...
Brian
Reply to this
I was wrong.
You were right.
The original solution WAS correct.
Reply to this
I am curious here. What if the so-called COUNTER GUY is the first person to be taken to the room and he is taken in the reqired number of times before anyone else starts being taken in?
Reply to this
According to William's solution, (and assuming switches both satrt in the "off" position), then the speaker will see switch "A" in the off position on every visit, and so (per step #7) will not count any prisoners yet, but will just flip switch "B."
Brian
Reply to this
There is no "required number of times." If the warden isn't very inclined to bring people into the switch room, the prisoners may be looking at a long stay.
Reply to this
Paul - it's true that the warden can keep the prisoners waiting a long time, but the clause in the problem statement that says "But, given enough time, everyone will eventually visit the switch room as many times as everyone else" is supposed to ensure the warden will *eventually* bring everyone in the room.
Reply to this
Solution:
1) A switch is a counter, b switch is irrelevant.
2) Select a spokesman. He sets a prisoner count of “0”
3) Switch up is on. Down is off.
4) Only the speaker can turn off switch "A".
5) First prisoner must turn on switch "A", Unless switch is already on then he switches "B".
6) If you are not the speaker and if switch "A" is off and you have not turned switch "A" on, then turn switch "A" on. If not switch "B".
7) If the speaker sees switch "A" on, then he turns it off and adds 1 to the prisoner count, If not he switches b.
8) When the count is 22 then the speaker may declare “We have all been in the room” safely.
Yes I did make an asumption but it was not about switch "A", it was about who's first. by realizing this, I have deduced that if the speaker WAS the first prizoner and the switch was on. his count would be off by 1 and he would DIE. Ill have to rethink this.
here the dilemma as i see it.
we know if the speaker is not the first person no matter what position the switches are in works. that i can prove.
for discussion assume the following:
a) first person is the speaker.
b) he does NOT know if he is first.
c) "A" is on.
when you assume these facts, the solution is INCORRECT. we would have to figure out how to determine this fact. When the speaker enters the room, Is he or is he not the first person? solve this we solve the puzzle.
BRIAN. I DID NOT SOLVE IT YET
wlnelson
Reply to this
Well he can also don't count his first visit that way he makes sure they don't die.
Reply to this
why not write your initials on the wall, your already in jail.....
and when all the initals are on the wall just say we've all been here.
Reply to this
I figured out the solution. I was on the right track.
same solution as stated above with 2 changes. each prisoner must switch "A" twice, and the count must be 44 bo 22.
this will account for the fisrt switch in any position. Damn I thought I had it the first time. and yes this would make for a very long stay but not a perminate one.
wlnelson
Reply to this
Now I only skimmed most of this, but I think I get the jist of it and I think your most recent addition was overkill.
Why not just have the speaker/counter ASSUME he is first, even though he is likely not. Therefore if the switch is on, he turns it off and doesn't count one, he simply assumes that the switch started at on and he was first. So the first time he visits the only person he counts as visting hte room is himself. From there it would continue exactly as the original solution, which I believe would be adequate to solve the problem.
Reply to this
You all missed the easy solution.
Learn to wrestle alligators...!
(OK, so I'm not a programmer. I'm married to one, and you learn to avoid these things at all costs.)
Reply to this
William, why not just use your first solution, but use 23 (instead of 22), to account for the possibility that the switch was on to begin with. Then you've counted everyone, plus the one (to be safe) in case the switch was on to start with. And then your first solution works, with only 1 switch per person.
Reply to this
to answer the last two
this is the easiest solution i can come up with, Because ONLY THE JAILER KNOWS WHOS FIRST.
wlnelson
Reply to this
William:
The two that posted before you are correct. The first time the guy keeping count visits the room, he does not know if the switch started on, so he switches it off but does not add to his count. Then your solution continues as stated, since every time after his first visit, the switch will have been turned on by one of the other prisoners. Your "count to 44" solution is overkill.
Reply to this
Well I previously suggested simply not counting hte first one would work, but it just dawn on me, that it does not.
IF the switch starts down, a prisoner comes in, flips it up, then the counter comes in, flips it down, and doesn't count the first prisoner (he assumes the switch started up), and hte first prisoner never flips the switch back up because he thinks he's already been counted. So... I guess the count to 44 answer is the only logical answer I can think of anyway
Reply to this
Feed them to the alligators anyway they are prisoners and times are a changing.
Reply to this
Unfortunately your solution just assumes the designated counter will be escorted to the switch room at least 44 times. Imagine the anguish of entering the switch room & repeatedly having to just flip B because A never moves...
Reply to this
All of the answers overlooked the instructions of the warden. They were allowed to talk to each other at the beginning to plan strategy. One was designated the official counter. Then, the rest of the solution was correct. When he got to 22, he knew everyone had been there, but he waited until 24,just to make sure.
Reply to this
Hi Brian,
where did you find such clever guard and such an intelligent prisoners?
Reply to this