Freedom or aligators use switches for code.

[westgrant88]

I was wondering if anyone had seen this logic problem in a different form or knows how a solution to this. Thanks

Freedom or Alligators
Once upon a time, a prison warden was responsible for 22 prisoners on Death Row. These prisoners were students who had done terrible things: some illegally downloaded movies and music, some texted during classes, some were addicted to Facebook, and some watched Glee.
One day, the warden offers the prisoners one chance at freedom. After a brief discussion period in which they could plan their strategy, each of the prisoners will be placed in solitary confinement (in completely soundproof cells) with absolutely no way to communicate with one another. The warden will arbitrarily take one prisoner at a time to another room containing two light switches side by side. The switches are not connected to anything, but the warden tells the prisoners that at the beginning of the entire process both switches will begin in the “Off” or “Down” position. The rules are that each time one of the prisoners enters the room he or she must flip exactly one of the switches.
The warden tells the prisoners that if one of them ever correctly announces that all 22 prisoners have been in the room that they will all be released. However, if any of the prisoners ever incorrectly claims that all 22 have been in the room, then all 22 will be fed to the warden’s pet alligators.
The warden makes it clear to that prisoners may be returned to the room any number of times, but there is no way for the prisoners to communicate with one another other than by way of the two light switches. The room with the switches will be thoroughly cleaned after each prisoner leaves.
The prisoners are given some time to come up with a plan before they are to be placed in solitary confinement.
How do they ensure their freedom?

 

[thedr520]

If it was me I would have everyone turn off the light in there cell after they had been in the room but that's assuming the prisoners are on the same floor.

 

[jedishrfu]

the switches can have four states: 00 01 10 11 which isn't enough to count prisoners.

The prisoners select a leader to announce to the warden when they've all visited the room and decide on rules for flipping the switches.

What might the rules be?

 

[westgrant88]

I thought using the first switch as the key. the first one in flips it on and all leave it on until the last 21 person who flips the first back down. the 22 knows that means 21 has been by thus meaning he os the 22. Will that work?

 

[Evo]

I thought using the first switch as the key. the first one in flips it on and all leave it on until the last 21 person who flips the first back down. the 22 knows that means 21 has been by thus meaning he os the 22. Will that work?

Since they are all kept in solitary confinement, they would have no way of knowing who went before them.

Also according to the rules

The rules are that each time one of the prisoners enters the room he or she must flip exactly one of the switches.

So, no.

Plus

The warden makes it clear to that prisoners may be returned to the room any number of times, but there is no way for the prisoners to communicate with one another other than by way of the two light switches.

 

[jedishrfu]

A clever solution along the lines of captain Kirk on star trek would be to notice the light switch has two screws one on top and one on the bottom. You could turn them a quarter or half turn to indicate a switch. That would give you 4 more bits enough to count to 32. But of course e warden is secretly watching you and would foil the plot.

 

[Dead Boss]

All prisoners except one:
If switch B is off and you are first time in the room, turn it on. Otherwise flip switch A.

One selected prisoner:
If switch B is on, turn it off. Otherwise flip switch A. Once you count that B was on 21 times, you're free to go.

 

[phillip1882]

Similar to the single light switch with 100 prisoners;

For this it can be done quite quickly.
Using the gray code:
00
01
11
10

Each prisoners come in and changes the one light switch to the next state unless its the same state as when he left on. Once a prisoner realizes that 22 people must have been in the room, he can declare victory.

 

[Rogerio]

Similar to the single light switch with 100 prisoners;

For this it can be done quite quickly.
Using the gray code:
00
01
11
10

Each prisoners come in and changes the one light switch to the next state unless its the same state as when he left on. Once a prisoner realizes that 22 people must have been in the room, he can declare victory.

Wrong.
When a prisioner (who has already been at the room) enters the room, he doesn't known whether everybody has already been there or whether only 18 prisioners, for instance.
Dead Boss's answer is ok.

 

[phillip1882]

while i agree it wouldn't be 100% certain, there are some cases where this plan would fail, you would be about 99.999% certain, given the conditions of the problem.

 

[Rogerio]

Similar to the single light switch with 100 prisoners;

For this it can be done quite quickly.
Using the gray code:
00
01
11
10

Each prisoners come in and changes the one light switch to the next state unless its the same state as when he left on. Once a prisoner realizes that 22 people must have been in the room, he can declare victory.

And, in this case, what is he supposed to do?
(we know he has to flip exactly one switch.)

while i agree it wouldn't be 100% certain, there are some cases where this plan would fail, you would be about 99.999% certain, given the conditions of the problem.

According to your plan, I don't see how could any prisioneer realize everybody has already been there.
What about explain your reasoning with an example?

 

[phillip1882]

ah i see, i was under the assumption that the prisoner could leave the state as is rather than change it.
however i still think my strategy would work in a majority of cases.
let's assume only 10 prisoners.
here's 30 random numbers between 1 and 10
5 7 9 4 5
4 10 6 5 9
10 9 8 8 6
6 7 2 6 9
4 2 10 1 7
7 1 8 1 2
so 5 will enter first. he'll change the state to 01.
7 enters he see the state at 01, so can conclude 1 prisoner has been in the room.
9 enters, he sees state 11, so starts his count at 2.
4 enters, starts count at 3 state 10
when 5 enters again, he'll see state 00, an can therefore conclude that 3 people have been in the room.
and so on.
all prisoners except 3 have entered by 30 days. at the end of this 30, here would be the count of each prisoner.
1: 6
2: 7
3:
4: 4
5: 6
6: 7
7: 6
8: 1
9: 8
10: 8

with 22 prisoners, the chances of success using this method are even higher.

 

[Averagesupernova]

I never spend a lot of time on these if it looks like the OP does not know the answer. Several reasons is that the OP could simply be trolling, or if they have copied the puzzle from elsewhere, did they leave out a very significant piece of the puzzle? For instance,

How do they ensure their freedom?

Maybe the original puzzle said: How do they ensure they are not fed to alligators?
Of course the simple answer is no one ever makes an attempt at stating that all 22 prisoners have been in the room.
-
It says a prisoner may be taken to the room any number of times. There is nothing that says all prisoners have to be taken in before there are repeats, and there is no limit on the number of repeats, so it shouldn't take a lot of smarts to realize that the warden could spend the rest of his life simply leading all prisoners except one in and out of the room. Of course there are hundreds of solutions if we get creative, but what are the rules? So, in a way, I am calling BS on this puzzle.

 

[MarcoD]

 

[AlephZero]

All prisoners except one:
If switch B is off and you are first time in the room, turn it on. Otherwise flip switch A.

One selected prisoner:
If switch B is on, turn it off. Otherwise flip switch A. Once you count that B was on 21 times, you're free to go.

That is nearly right, but the first sentence isn't very clear IMO.

For all the prisoners execpt one, If you go into the room and this is the first time that you see switch B is off, switch it on. Otherwise, flip switch A. (Note, this "the first time you see switch B is off" is not the same as "the first time you go into the room".)

The logic is that each of the 21 prisoners only switches B on once. So when the selected prisoner has seen it was on 21 times, everybody has been in the room at least once.

 

[Rogerio]

ah i see, i was under the assumption that the prisoner could leave the state as is rather than change it.
however i still think my strategy would work in a majority of cases.
let's assume only 10 prisoners.
here's 30 random numbers between 1 and 10
5 7 9 4 5
4 10 6 5 9
10 9 8 8 6
6 7 2 6 9
4 2 10 1 7
7 1 8 1 2
so 5 will enter first. he'll change the state to 01.
7 enters he see the state at 01, so can conclude 1 prisoner has been in the room.
9 enters, he sees state 11, so starts his count at 2.
4 enters, starts count at 3 state 10
when 5 enters again, he'll see state 00, an can therefore conclude that 3 people have been in the room.
and so on.
all prisoners except 3 have entered by 30 days. at the end of this 30, here would be the count of each prisoner.
1: 6
2: 7
3:
4: 4
5: 6
6: 7
7: 6
8: 1
9: 8
10: 8

with 22 prisoners, the chances of success using this method are even higher.

Ok, 7 sees the state at 01. Why couldn't he conclude 9 prisoners has already been in the room?
When 5 sees the state 00, he could conclude nothing since the sequence 5,7,9,7,5 (only 3 prisoners, instead the 4 prisoners from the original sequence 5,7,9,4,5) gives the same result.
Using your plan, no one can conclude everybody has already been in the room.

 

[Averagesupernova]

All prisoners except one:
If switch B is off and you are first time in the room, turn it on. Otherwise flip switch A.

One selected prisoner:
If switch B is on, turn it off. Otherwise flip switch A. Once you count that B was on 21 times, you're free to go.

Actually at first this seems excellent. But, the first prisoner who is not the selected one goes in the room and flips switch B on. Then the second prisoner goes in who is also not the selected one goes in and finds switch B already on. What is he/she to do?
-
Scenario one: Flip switch A but that means it will take a very very long time to get through it since the rule is now to flip switch B on only if you have never flipped it and you find it in the off state. There are no guarantees of multiple entries nor are there guarantees of even a single entry for each prisoner so if the second prisoner only goes in that one time his entry will never be counted. Also, based on my above scenario, everyone could have gone in multiple times and the selected one still not have counted 21 complete cycles. If the selection of prisoners were truly random then eventually everyone would cycle through enough times so that the selected one would finally count 20 flips of switch B.
-
Scenario two: Flip switch B off but that means the second prisoner who goes in will NEVER be counted. It means not getting eaten by the gators but it also means not getting freedom.
-
I still stand by my original comment about calling B.S. on this puzzle.

 

[AlephZero]

Prisoner B does what it says in the solution.

You are right, there is no guarantee that they will ever get their freedom, depending on the order they visit the room. For example the "counter" must obviously make at least 21 visits for this method to suceed.

You might like to consider what are necessary or sufficient conditions on the visiting pattern so they do eventually get their freedom, rather than calling BS on the puzzle...

 

[phillip1882]

Ok, 7 sees the state at 01. Why couldn't he conclude 9 prisoners has already been in the room?

the starting state is 00. any prisoner who enters the first time will see one of four states. 00, 01, 11, 10. when 7 enters, ha can only conclude that 1 prisoner must have entered because that state is 1 away from the starting state.

When 5 sees the state 00, he could conclude nothing since the sequence 5,7,9,7,5 (only 3 prisoners, instead the 4 prisoners from the original sequence 5,7,9,4,5) gives the same result.

when prisoner 5 left, he left the state 01, so when he enters again and sees 00, that's 3 states away from 01. that how he concludes 3 prisoners must have been in. you're right that 57975 give the same result. my point with this solution is that its likely to solve the problem in a reasonable amount of time.

 

[Averagesupernova]

I will call B.S. until I am told that the warden will continue picking all prisoners in a truly random fashion indefinitely. It all works as dead boss described as long as the warden doesn't decide to simply quit picking a particular prisoner.

 

[nashsur]

Perfect answer:

One prisoner designated as counter. That person is the only one allowed to turn switch B OFF otherwise they must toggle switch A. Everyone else will only turn switch B on IF IT IS THE FIRST TIME they see it off. Otherwise they must toggle switch A. No one is to turn switch B on more than once. Once the counter has turned off switch B 21 times, he/she can announce that all prisoners have entered the room. Assuring their freedom.

Averagesupernova is correct that a corrupt warden could hold back one prisoner. But in my solution each prisoner only has to enter the room one time, so the counter and all the rest will just have to wait for that last person to enter. A solution to that would be to require the warden to cycle the prisoners within a certain time frame, but that was not stated in the original problem and therefore can not be factored in.