Fog Creek Software
Discussion Board




23 Prisoners !!

The key to this puzzle seems to be in designating one of the prisoners as the "counter" and one of the two switches, say switch 2 as the one which keeps track of count. The other would just be a toggle switch which people keep toggling, in case they dont have an option

Strategy:
Initially,when a player Y enters the room for the first time, he handles switch 1 and remembers the state of switch 2. None of the players handle switch 2 till they know that the counter is listening(which means they start noticing a change in the switch state) and even then, they handle switch 2 once and only once !!
1. If switch 2 is off, turn in on and never touch it again
2. If switch 2 is on, toggle switch 1 and wait for the next turn.

Strategy for the counter:
The counter keeps track of the number of times he's flipped the switch and knows he's done when count reaches 23.
1. If switch 2 is on, he switches it off and adds 1 to the count
2. If switch 2 is off, he switches it on and subtracts 1 from the count
(This, I think would ensure that after a certain number of times, people would know that the counter is listening)

However, I can't seem to find a simple way to prove mathematically that it works (or) find the expected number of toggles,days for it to work.

Ideas,anyone?

-asita.

asita anche
Friday, September 19, 2003

The answer is really simplier than that:

The prisoners write on the wall next to the switches in whatever device they have at hand.

Write their name, or make a single mark the first time they visit. 

When there is 23 marks, they're done.

T.J.
Tuesday, September 23, 2003

The hardest part of this riddle for me is not knowing the initial condition of the two switches.  I agree with the first post, that a counter is certainly the way to go, but there is a non-trivial issue left to address.

The strategy outlined in the first post seems logical, though I would suggest some changes.  First, if switch B is designated as the counting switch, instruct all of the prisoners to enter the room and look at switch B.  If B is off, switch it on once and only once.  Wait for the counter to come in.  He will notice the switch is on, add one to his tally, and reset it to the off position.  Once he gets to 22, he knows everyone has been in the room at least once.

Anytime a prisoner enters and sees switch B in the on position, that indicates that the counter has not yet tallied a prisoner.  They will toggle switch A and wait, albeit a long time, until thier next opportunity to flip the switch.

This would work just fine except that we don't know where switch B is initially.  Consider this situation: the counter is the first person in the room.  He sees that switch A is up and resets it to down so that the counting procedure may begin.  This would be ideal, except the counter has no way of knowing whether he's first or not.

Here's another scenario: the first prisoner comes into the room and notices that switch B is off so he switches it on like he's been instructed to do.  So at some later time, the counter enters.  He sees that the switch is up, but he cannot know why it's up.  Is it up because that was the switch's initial position, or is it up b/c someone came before him and switched it up?

Perhaps my statistics are off here, but it seems like there is a very large chance (about 97.8%) that when the counter comes into the room, switch B will be on.  Either switch B will have been on in the very beginning (and no one would have touched it) or someone will have entered before him (there is only a one in 23 chance that the counter will be first) and will switch B from off to on.  This means there is about 50% uncertainity in the beginning.  We cannot know if the first person to toggle the switch has been counter or not.

I suppose given enough time, the counter could wait after counting 21 switches (he needn't count himself) and then just hope that he sees a 22nd switch.  This would guarantee everyone's been in the room.

The prisoners could also wait a significant period of time (perhaps a year or so, based on the disposition of the warden) before agreeing to start the counting process.  This would allow the counter to be reset to the off position and not be toggled until a specified amount of time passes.  Therefore, as time goes on, the probability becomes larger than at least one person has been in the room.  That person just needs to make sure that switch B is reset to off.  After the specified amount of time is over, the prisoners have essentially manipulated the initial conditions to their liking, and the counting procedure can begin as outlined.

If anyone knows a more fullproof of figuring this out, please let me know.

Michael Specian
Friday, September 26, 2003

I don't understand why the counter would ever have to subract from the count. If he arrives with switch 2 Off, then its his turn that he's counting (which he doesn't have to) or everyone since his last visit is making a repeat visit as well! Just make him flip switch one again.

The down side to this technique is that it's gonna take about 23x23 trips to the switches to get free.

I think there might be a way to bring it down to about (3 or 4)x23 trips. God knows I don't want to be in prison even that long <grin>. But for saftey sake. Let's go with your method, I'd hate to think someone would forget my method and we'd all die..

Bill Bingham
Friday, September 26, 2003

Add 1 more iteration to the counter, and stop worrying about the initial B switch on condition.

Bill Bingham
Friday, September 26, 2003

I think 23x23 would be the lower bound. It has to be atleast that many times. Since the problem does not present any particulars with respect to regularity, number of times etc., the logic would be something like this:

The first  time any prisoner other than the counter goes in, he has to toggle switch 1 only and remember the state of switch 2. In one of the later n times, when he sees the state of switch 2 changing, he knows that the counter is listening in. That time or the subsequent times, whenever the switch is off, he turns it on. After that, he never touches switch 2 again.

As per the counter, intuitively it seems right that to speed up the time in which everyone knows that the counter is in - every time he goes in,if the switch is off, he turns it on so people notice the toggle - thats when he substracts a 1.

asita anche
Friday, September 26, 2003

asita..you Moron! Can't you think of a better answer? the prisoners gotta make 23trips each? And by the time they do it-- they are losing their precious youthhood. What if the warden picks one every year??  I can't believe such dumbasses like you solve puzzles...

Sha

Cshah
Friday, September 26, 2003

All right, Mr. Cshah; there is no need to mask incompetence and frustration with offensiveness and abuse.

Anyway, here is potentially a more optimal solution, for prisoners whose life-expectancy is less than 23*23 years. And to be fair, everybody is a counter in this solution.

Let's represent the two switches by a two-bit string.
eg. 00 means both switches are off
      01 means switch one is off; switch two is on, and so on...

Now, there are 8 possible transitions. Out which, I call four of them the default set. They are :
00 -> 10
10 -> 00
01- > 11
11 -> 01

Notice that, with these transitions, the switches will either cycle between 00 and 10 or between 01 and 11 .

All the prisoners will have to follow this default set of transitions. However, each one of them (excpet one who, let's say is called X) is given a joker that they can use once and only once. A joker allows them to make one of the following transitions only :
00->01
10->11

X is given 23 jokers and each joker allows him(or her) to make one of the following transitions only:
11->10
01->00

Each prisoner (including X) maintains count. They increment their counter by 1 when they see (or do) a transition from the 00-10 combination to the 01-11 combination. Such a transition occurs only when a person uses a joker. They know that all the prisoners have been to the switch room at least once when one of the following occurs :
a. Their count is 44 and the switches are at 11 or 10
b. Their count is 45

Once one of the prisoners has his count satisfy one of the above conditions, he says "We've all been there, done that. Now let's all go home and switch our lives to a more righteous path".

The lower bound for the solution seems to be 45 trips. I shall leave to the reader to work out the average number of trips.

Anaaaand
Monday, September 29, 2003

Based on the random switch + counter switch

Shouldnt the required count be 43 rather than 22/23/44/45?

Case 1 - switch initially ON:
Nothing happens The Counter toggles the switch OFF.  If each person toggles the Counter ON once, with The Counter the only one who can toggle a switch OFF.  After The Counter reaches 22, he can be assured that everyone has switched at least once.

Case 2 - switch initially OFF:
Prisoner A toggles the switch ON.  The Counter then toggles the switch OFF.  If we knew the initial condition, then The Counter would need to reach 21 to realize that everyone has switched.  However, since we didn't know the initial condition, allow each prison to toggle twice.  Assume the warden is evil and picks the intial person first, then allows 20/21 of the remaining prisoners to toggle the Counter twice.  Then we have a count 20 * 2 + 1 = 41.  Once the 22nd person toggles, @ 42 then we're golden.

However, we will have to modify the original case then.  Since a count of 42 toggles allows 21 people to flip the switch twice, then we need an additional toggle to make sure that the 22nd person has toggled the count switch.

Clarence
Monday, October 06, 2003

ARGH!!  All of these "solutions" have holes in them.  Honestly, the solution that I proposed is still the best of the options presented.  Let's look at the alternatives:

I argue that not knowing the initial condition makes things difficult and that the initial switch condition would have to be manipulated in some way so that we don't neglect counting somebody.  Bill Bingham repsonds:

"Add 1 more iteration to the counter, and stop worrying about the initial B switch on condition. "

He misses the point.  What if switch B was up initially because somebody flipped it up (48.9% chance of this being the case if Switch B is up when the counter gets into the room)?  In that case, waiting for the last person to flip means you could be waiting forever!!  You only have a 51.1% chance that the thing will get flipped a final time.  In that case, my solution of waiting a year to manipulate the conditions seems far more statistically sound than the coin flip with the prinsoners' lives Bill suggests.

What else do we read?  Anaaaand suggests a method of using "jokers".  All one needs to do to disprove a theory is show one example when it won't work.  This is what I will do.  He writes:

"All the prisoners will have to follow this default set of transitions. However, each one of them (excpet one who, let's say is called X) is given a joker that they can use once and only once. A joker allows them to make one of the following transitions only :
00->01
10->11

X is given 23 jokers and each joker allows him(or her) to make one of the following transitions only:
11->10
01->00

Each prisoner (including X) maintains count. They increment their counter by 1 when they see (or do) a transition from the 00-10 combination to the 01-11 combination. Such a transition occurs only when a person uses a joker. They know that all the prisoners have been to the switch room at least once when one of the following occurs :
a. Their count is 44 and the switches are at 11 or 10
b. Their count is 45"

This actually makes no sense.  He gives 23 jokers to one guy.  What good will that do??!!  Just because one guy flips a switch 23 times does not mean that all 23 people have been in the room!  Furthermore, it is HIGHLY unlikely that anyone will ever reach the 44 or 45 counts Anaaaand suggests.  Those counts would necessarily be spread amongst the group.  At the point where the joker is used a finite number of times, no one will ever get to the state where they know certainly that everyone has been in the room at least once.

Michael Specian
Wednesday, October 22, 2003

COMPLETE 23 PRISONERS SOLUTION!

COMPLETE 23 PRISONERS SOLUTION!

COMPLETE 23 PRISONERS SOLUTION!

    The 23 prisoners are going to have to select one of the group to be the "counter".  The counter's job is to keep track of how many people have been in the room.  He will be the individual to finally tell the warden when everyone's visited the room at least once.  Here's the strategy they must outline:

THE COUNTER

    The group will establish one of the two switches as the "counting switch".  We'll call this Switch B.  The other switch is Switch A.  When the counter enters the room, he will look to Switch B.  If Switch B is in the on-position, he will switch it back down and increment his count by one.  He will not count the first time he switches B to the down-position.  If Switch B is down, he will flip Switch A and his count will remain the same.  Once his count reaches 43, he will be certain that everyone has visited the room at least once.

THE OTHER PRISONERS

    The other prisoners will be instructed to flip Switch B into the on-position twice and only twice.  Therefore, if Switch B is in the down-position when a prisoner enters the room, he will flip it up, assuming he hasn't already flipped it up his allotted two times.  If Switch B is up, he knows that the counter hasn't yet had the opportunity to count another prisoner's presence, so he will flip Switch A.

WHY THIS WORKS

    There have been a number of solutions suggested for this problem.  Many don't work.  The real question is where can the prisoners store information within this system?

    Some have suggested storing the information in the room, that they can use the light switch positions as some form of code.  Unfortunately, the limitations of the problem make this impossible.  There are only four states that the light switch combination can be in and each state can only turn into two other states (The states are Down-Down, Down-Up, Up-Down, and Up-Up).  To use computer science terminology, there are not enough bits of data to establish a numerical value of 1 through 23 to the switches, nor is there enough flexibility in changing the switches position to make this viable.

    We see, therefore, that the information cannot be stored in the room.  Another alternative is storing the information in the minds of individual prisoners.  Sadly, since the prisoners cannot come into contact with one another, there is no way for this information to ever be linked up in a way that is useful.

    The only remaining possibility is to store the information in the mind of one prisoner using the room as his tool.  My solution does that.

    Some may ask, "Why have everyone flip Switch B twice?  Shouldn't once be enough?"  While that objection seems reasonable on face, the answer is, "No, once is not enough."  Here's why: When the counter first enters the room, chances are, he will not have been the first one in there.  In fact, the chances of his being first are only 1 in 23, making the chance of his not being first 22 in 23 or about 95.7%.

    Chances are when the counter enters the room for the first time, Switch B will be up.  The problem, however, is that the counter has no idea *why* that switch is up.  Is it up because that was the switch's initial condition or is it up because a previous prisoner flipped it up?  There's really no way of knowing.

      So consider the problem that arises if prisoners only have to flip Switch B once.  The counter comes in for the first time and finds Switch B up.  Statistically, it's more likely that the switch's initial condition was up rather than another prisoner having put it up.  The counter flips the switch down, but keeps his count at 0, just to be safe.  He cannot be sure anyone has flipped Switch B yet.

    In this situation, one of either two things must be true.  Either a prisoner did flip Switch B and thought he was being counted, or no one flipped Switch B yet.  In the first scenario, the counter would eventually get to 21, yet 22 would never take place.  The 22nd prisoner would have been the first individual to flip Switch B but he would have gone uncounted.  The counter could wait a hundred million years, but Switch B will never be flipped again and he would have no way of knowing whether that final prisoner had ever entered the room.

    This ambiguity is troubling, but there is a way around it.  Have every prisoner flip Switch B twice.  This way, all the prisoners' flippings (excluding the counter, of course, who knows he's been in the room) *might* eventually tally to 44.  The fortunate thing is that the counter never has to wait that long for a 44th flip that might never happen.  When flip 43 takes place, he knows absolutely that everyone's been in the room at least once.

    The other 21 prisoners can flip Switch B a maximum of 42 times.  The only way flip 43 can ever happen is if the final 22nd prisoner does it.

      This procedure, though slow, is a fullproof method of guaranteeing that every prisoner has visited the room.

Michael Specian
Thursday, October 23, 2003

sorry, I didnt seem to understand, what if the counter's first visit was after 2 visits performed by a prisenor?

I mean wont he miss a count?

The rest of the presinors could have gone twice and the counter hadnt been there yet to count!!!

Hussam
Friday, October 24, 2003

The first post by Asita is the correct solution. I have come up with the same solution myself. =)

Let me call the 22 prisoners who are not Counter be "simple prisoners".

Please note that the true initial state of the switches is not important, since no simple prisoners will touch the switch 2 unless they are sure the Counter has come before. Hence, the Counter must be the first  person who toggles switch 2.

The solution has been quite clear but I wonder why Asita thought the lowerbound is 23*23???

The fastest case happens when :
(0) The switch 2 is at "On" state initially
(1) all 22 simple prisoners enter the room once (observed switch 2)
(2) Counter enters (Switch 2 toggled, to "Off")

(3) Simple prisoner No.1, has come, detected change of switch 2. He turned on switch 2.
(4) Counter enters, increment the count from 0 to 1. Switch 2 is turned to "Off"

(5) Like (3), for the simple prisoner No.2
(6) Like (4), counter reaches 2

(7) Like (3), for the simple prisoner No.3
(8) Like (4), counter reaches 3

......

(45) Like (3), for the simple prisoner No.22
(46) Counter enters and yell, "Free us all!"

Total number of room entering is :
22 + 1    +  22*2    = 67
(1)  (2)      (3)-(46)

which should be the lower bound! =)

LOS
Thursday, November 06, 2003

There is a slight supplement to  Asita's solution:

"If switch 2 is "on" when the Counter enters the room for the first time, he should not increment the count from 0 to 1."


It is because no other prisoner will touch the switch 2 unless they detect the Counter has come already, the "On" state of switch 2 must not be triggered by any other prisoner, but is the true initial state.

The essence of the strategy is let the Counter to count the number of "Off"-to-"On" transitions of switch 2 not made by him!

LOS
Thursday, November 06, 2003

In response to LOS:
"It is because no other prisoner will touch the switch 2 unless they detect the Counter has come already"

There is no way for the prisoners to know if the Counter has already come.  If the Counter comes he will turn switch 2 down.  If a prisoner sees swith 2 in the down position he will assume the Counter has been there even if he has not and it is just down because that was its initial position.

Michael Specian's October 23 answer is correct (it is the only correct answer).

Joanna Deitch
Tuesday, November 11, 2003

can't someone just call the A-Team to break them out?

barf
Wednesday, November 19, 2003

None of these solutions seem to tackle this part of the problem...

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else"

Which seems to dictate that every prisoner has to have visited the room as many times as each other. Given that there are 23 prisoners being taken at random to this room seems fairly unlikely to happen in the first place. Hmm 1 in 23!/23 ... maybe ? I give up :)

AllDayBreakfast
Thursday, November 20, 2003

OK, so I read through it.  There's no way possible for any one person with no communication to have any idea that the other guys have been in that room, even once.  The most you could ever be sure of is 2 distinct people.  After reading it again carefully, the warden says, "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."

Therefore the only way for all the men to know that they have all visited the switch room is to **hold their strategic meeting IN THE SWITCH ROOM**.

That is what I would do to keep away from the gators.

Eric Mims
Friday, November 21, 2003

The correct solution has already been posted, but here is another quick way of looking at it if you still don't believe it.

Using the method of the counter and having each prisoner flip it twice has to work.  As soon as someone flips it, they are assured that the counter will enter before it is ever flipped again.  Therefore, there are only 3 possibilities at this time when the counter first goes to the switch room.

1) the switch was up to begin with and nobody has used either of their 2 flips
or
2) the switch is up and 1 person has used 1 of their 2 flips and nobody else has
or
3) the switch was down to begin with.

In any case it is necessary for the counter to count 43 further flips (not counting the one if it is up the first time he enters).  2 for each prisoner not counting himself plus 1 for the last prisoner.  This 43rd flip in case 2) will be the final flip possible, in case 1) will guarantee that everyone has flipped it at least once since the 43rd will be equal to the max number of 21 prisoners flipping plus 1 for the 22nd and final, in case 3) will be the same as case 1) reasoning.

There may be a better way to solve it, but this has to work for sure (Again, this was already posted but I wanted to confirm that it has to be a solution).

e
Wednesday, November 26, 2003

Careful. I think that the whole "counter" idea has a serious flaw. Please read this carefully:

"At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure."

Any of the prisioners can answer the question. Not just one "counter" guy.

James Delacour
Wednesday, December 17, 2003


If the initial position of the switches is important,

or you want the counter to be the first one in,

just define it that way.  Say "the counter is the first person in."

Or "First person, turn switch A off if not already there,"

Or "Second person, turn switch B off if not already there."

Fred Is Dead
Thursday, February 19, 2004

*  Recent Topics

*  Fog Creek Home