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

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

Also according to the rules So, no.

Plus

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

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

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

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 alot 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, 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 alot 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

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

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

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.