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 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. I am not telling you their present positions.  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 anyone of you may declare to me, 'we have all visited the switch room' and be 100% sure.

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

 What is the strategy they come up with so that they can be free?

"given time, everyone will visit the same number of times as everyone else" 

so the key here is to figure out how many times at a minimum it will take for this to happen. And then find  a way to track it. 

So my plan goes something like this: you can have all the prisoners only flick the right switch until they reach a certain number of visits (more than 2), so everyone knows the initial position of the left switch.  Then when whoever reaches the magic number of visits to ensure that everyone has had at least two goes,  they can change the position of the left one, and the next will know for sure.  We've all been here. 

But how to reach the magic number? It has to be the minimum number of visits any prisoner will have to take to satisfy the conditions: 23 people, approaching equal number of visits, minimum 2 visits each. Random selection.

So if he chooses prisoner #1 three times in a row, that prisoner would somehow have to know on which of those visits his count totals everyone else's count?  In fact, even if any of  the prisoners know they have all visited the switch room, it is highly unlikely they will have visited it the exact same amount of times.

Saying this another way, from the time when all prisoners have visited the room the same amount of times, it's not possible for that condition to apply for the next 22 visits, and double that should he at any time decide to take the same prisoner twice to the room.

Am I understanding this problem correctly?

first thought: holy hell....

i was kinda along the same lines as ratsy, but haven't figured out how to really know especially if you don't know the original position. you can't guarantee how much time, which is the whole point.

my thought is: all flip the one switch (say A) their first time, any subsequent times would flip the other switch (B). but how to determine 23 flips? trying to think of a turing kinda thing, but not enough data to go with.

The other approach I had, but couldn't think all the way through was to split the prisoners into groups that reflected the switch positions. 

So the groups would be:

A up B up

A up B dwn

A dwn B up

A dwn B Dwn

And then, if you made it so that a group could only change the switches in a certain way, it could signal the next group as to what to do. Or signal which person was there before (numbered prisoners) or whatnot. But my brain can't handle the permutations and find a linear path through them....

The first time each prisoner visits the switch room, he: spits on the floor, makes a mark on the wall, drops a match, or in some other agreed way leaves an indication he's been there.  When a prisoner enters the room and sees 23 such signals already in place, he makes the declaration.

The switches are a red herring.

Thoughts (other than I believe I've heard this before, but really don't know the answer)

- there are 4 possible settings U/U, U/D, D/U, D,D

- U/U can't be turned into D/D, U/D can't be turned into D/U and vice-versa on each.

- The prisoners don't need to know they have all been there the same # of times, just that each one was there at least once.

- Each prisoner knows the number of times they have been there.

NewlyIdle wrote:

The first time each prisoner visits the switch room, he: spits on the floor, makes a mark on the wall, drops a match, or in some other agreed way leaves an indication he's been there.  When a prisoner enters the room and sees 23 such signals already in place, he makes the declaration.

The switches are a red herring.

This works depending on how you interpret this line of the problem..

"But after today, you will be in isolated cells and will have no communication with one another."

Granted, throwing the switches is a form of communication.  So either the problem is poorly worded, or your answer finds the loop-hole.

I guess I am not sure of the rules, the setup suggests that someone could visit the switch room 3 times before someone has visited once.  Can you clarify this Boris?

If everyone must visit before someone visits twice, then you can tell everyone on their first visit to put the switch up if you can. (so after the first vist the switched will either be both up or one up and one down, it will not happen that both switches are down) 

On your second visit put the switch down if you can.  The first prisoner that sees both switches down knows that everyone has been there at least once and makes the announcement.

Here's one of my favorites from my youth. I've modified it a tad to make it more difficult (I think). Use straight logic to answer - no tricks. 

There are 4 inmates with long sentences ahead of them. The prison warden is dealing with an overpopulation problem.

The warden shows 4 inmates 4 green hats and 3 blue hats, which are identical in every other way.  The warden then blindfolds the inmates and randomly lets them pick a hat and put it on their heads, disposing of the unused hats.  Then one by one he lets them take their blindfolds off and gives them one chance to guess what color hat they have on. No mirrors are in the room etc.

The prisoner's options are:

1. correctly guess what color hat you have on your head and go free
2. guess wrong and it's off to the gas chamber
3. Pass and live out your sentence.

The inmates don't particularly like each other so they are not likely to cheat with signals, but they are all very smart, know their fellow inmates are very smart, know each other's voices, want to go free, and none of them want to die.

The warden lets inmate #1 take off his blindfold.  Inmate #1 views the other 3 inmates and Passes.

The warden lets inmate #2 take off his blindfold.  Inmate #2 views the other 3 inmates and Passes.

The warden lets inmate #3 take off his blindfold.  Inmate #3 views the other 3 inmates and Passes.

The warden lets inmate #4  take off his blindfold, but inmate #4 declines to take off his blindfold and is able to confidently and correctly tell the warden the color of the hat on his head. 

What color is his hat, and how did he do it?

SquintGnome wrote:

I guess I am not sure of the rules, the setup suggests that someone could visit the switch room 3 times before someone has visited once.  Can you clarify this Boris?

If everyone must visit before someone visits twice, then you can tell everyone on their first visit to put the switch up if you can. (so after the first vist the switched will either be both up or one up and one down, it will not happen that both switches are down) 

On your second visit put the switch down if you can.  The first prisoner that sees both switches down knows that everyone has been there at least once and makes the announcement.

this can't guarantee that all have visited. if you have 3 inmates (A,B,C) and A & B both visit twice before C visits the first time, then they'll both be down. or if A visits twice before B or C, and the switches start both down...

weathertop wrote:

SquintGnome wrote:

I guess I am not sure of the rules, the setup suggests that someone could visit the switch room 3 times before someone has visited once.  Can you clarify this Boris?

If everyone must visit before someone visits twice, then you can tell everyone on their first visit to put the switch up if you can. (so after the first vist the switched will either be both up or one up and one down, it will not happen that both switches are down) 

On your second visit put the switch down if you can.  The first prisoner that sees both switches down knows that everyone has been there at least once and makes the announcement.

this can't guarantee that all have visited. if you have 3 inmates (A,B,C) and A & B both visit twice before C visits the first time, then they'll both be down. or if A visits twice before B or C, and the switches start both down...

Agreed, i was asking for clarification of the setup.  My solution is preceded by the caveat that someone can not visit twice before everyone else has visitedvomce

M57 wrote:

Here's one of my favorites from my youth. I've modified it a tad to make it more difficult (I think). Use straight logic to answer - no tricks. 

There are 4 inmates with long sentences ahead of them. The prison warden is dealing with an overpopulation problem.

The warden shows 4 inmates 4 green hats and 3 blue hats, which are identical in every other way.  The warden then blindfolds the inmates and randomly lets them pick a hat and put it on their heads, disposing of the unused hats.  Then one by one he lets them take their blindfolds off and gives them one chance to guess what color hat they have on. No mirrors are in the room etc.

The prisoner's options are:

1. correctly guess what color hat you have on your head and go free
2. guess wrong and it's off to the gas chamber
3. Pass and live out your sentence.

The inmates don't particularly like each other so they are not likely to cheat with signals, but they are all very smart, know their fellow inmates are very smart, know each other's voices, want to go free, and none of them want to die.

The warden lets inmate #1 take off his blindfold.  Inmate #1 views the other 3 inmates and Passes.

The warden lets inmate #2 take off his blindfold.  Inmate #2 views the other 3 inmates and Passes.

The warden lets inmate #3 take off his blindfold.  Inmate #3 views the other 3 inmates and Passes.

The warden lets inmate #4  take off his blindfold, but inmate #4 declines to take off his blindfold and is able to confidently and correctly tell the warden the color of the hat on his head. 

What color is his hat, and how did he do it?

at first i thought its gotta be green. because the only way this will work is if 3 of the 4 have blue or all have green on. if the first 3 only see 2 blue, 1 green; then #4 has the green. 

but then i figured i better plot it out. columns A and E (blue) are my first thought's correct option, where B,C,D (red) would have someone else set free.

but then there's the chance that there are 2 of each color drawn (here there's a 50% chance of #4 having green) and 1 blue/3 green drawn (here there's a 75% chance of #4 having green).  with the first 3 ppl just 'passing' there's no way to guarantee that #4 has a specific color...

i'm confused, is there enough information?

SquintGnome wrote:

weathertop wrote:

SquintGnome wrote:

I guess I am not sure of the rules, the setup suggests that someone could visit the switch room 3 times before someone has visited once.  Can you clarify this Boris?

If everyone must visit before someone visits twice, then you can tell everyone on their first visit to put the switch up if you can. (so after the first vist the switched will either be both up or one up and one down, it will not happen that both switches are down) 

On your second visit put the switch down if you can.  The first prisoner that sees both switches down knows that everyone has been there at least once and makes the announcement.

this can't guarantee that all have visited. if you have 3 inmates (A,B,C) and A & B both visit twice before C visits the first time, then they'll both be down. or if A visits twice before B or C, and the switches start both down...

Agreed, i was asking for clarification of the setup.  My solution is preceded by the caveat that someone can not visit twice before everyone else has visitedvomce

from the OP: 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.

so not all have to visit once prior to any visiting twice 

weathertop wrote:

at first i thought its gotta be green. because the only way this will work is if 3 of the 4 have blue or all have green on. if the first 3 only see 2 blue, 1 green; then #4 has the green. 

but then i figured i better plot it out. columns A and E (blue) are my first thought's correct option, where B,C,D (red) would have someone else set free.

but then there's the chance that there are 2 of each color drawn (here there's a 50% chance of #4 having green) and 1 blue/3 green drawn (here there's a 75% chance of #4 having green).  with the first 3 ppl just 'passing' there's no way to guarantee that #4 has a specific color...

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

1

g

g

b

b

b

b

b

b

g

g

g

g

g

g

b

2

g

b

g

b

b

b

g

g

b

b

g

g

g

b

g

3

g

b

b

g

b

g

b

g

g

b

b

g

b

g

g

4

g

b

b

b

g

g

g

b

b

g

b

b

g

g

g

i'm confused, is there enough information?

 Your approach is not the right one.  It may work, but I don't know how.  These inmates were logisticians before they took up a life of crime.  They only 'guess' with 100% certainty. Death is not an option.  Just don't ask me how they were caught and convicted.

my point exactly. if they only guess when there's a 100% certainty then this puzzle is jacked up.

the above is my proof. its a list of the permutations of what they could possibly be wearing. only the blue and red highlights are the 100% certainties. when you consider F-O, there isn't a certainty thus my confusion and thinking the OP is flawed.

weathertop wrote:

my point exactly. if they only guess when there's a 100% certainty then this puzzle is jacked up.

the above is my proof. its a list of the permutations of what they could possibly be wearing. only the blue and red highlights are the 100% certainties. when you consider F-O, there isn't a certainty thus my confusion and thinking the OP is flawed.

You are neglecting to take into account that every time one of them passes, inferences can be made.

Okay, one more time with inferences:

They will pass if they don't know for sure.  The only way the first guy can know for sure is if he see's 3 blue hats.  So there has to be between 1 and 3 green hats on the head of b,c,and d. 

Which means at least one of them definitely wearing a green hat.  b,c or d.

b sees that at least one of a,c,d is  definately wearing green,

and c sees that at least one of a,b,d is definately wearing green. 

That means that there are at least 2 green hats out there, between a,b,c. 

That leaves potentially 2 green or 3 blue hats on the head of guy d.

The only person they have in common that they can all see is Person D.