## Brain Teaser - Prisoners and Switches

It’s been pretty quiet here lately – my posting has been limited by business at work. So I’ve shamelessly ripped a brainteaser from braingle.

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. Both switches are in their OFF positions now. 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.”

Similarly tagged OmniNerd content:

- Mystery of Sailing Stones Solved, by VnutZ 2 months ago
- CSAW CTF 2013 - MISC 100 "Black & White", by VnutZ about 1 year ago
- GCHQ Cyber Challenge, by VnutZ almost 3 years ago
- Wind Powered Car Outpaces Wind, by VnutZ over 3 years ago

## Cannot answer by Anonymous

I don’t think you can answer that question since the guard says: “or I may jump around and come back”

Which means he can basically just choose between two prisoners and rotate their turns forever…unless I’m missing something here.

-EOS

## Counting is the key... by Anonymous

To me, all the description points to a somehow binary counting… if they can move 1 switch at a time it means they can count 01, 11, 10, 00 over and over again, I think the key is the number of prisoners “23” because then there must be a way to find out a match between the counting of the switches with the counting of the prisioners multiplied by X number of repetitions (remember the end is when each prisioner visited the room as many times as everyone else) it means it can be 23, 46, 69, 92… and so on.

I will keep trying to figure out how to do it :-D

## A on the first time in by Anonymous

What if everyone agrees to only toggle A the first time they’re brought there. The second time they come they’ll toggle B to ON. So if you go into the room for the first time and B is ON, then someone else must have already been in there a second time. I haven’t gotten any farther yet…

## Programmatic Demo - (Spoiler Alert!) by gnifyus

O.K. it’s been a while on this one, so since anyone can look at the answer (I finally did), I decided to come up with a basic computer program to try and demonstrate this puzzle. There is one statement which seems misleading:

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

It probably should read : But, given enough time, everyone will eventually visit the switch room

at leastas many times as everyone else.This is a C# program hastily done in MS Visual Studio, but it can be easily adapted (and hopefully improved by some of you) to any computer language. If you don’t want look at the answer quite yet, maybe just follow the logic to see how this puzzle works.

It’s interesting how different random sequences affect how many times the guard has to bring prisoners to the room.

## Simple Answer by wyldeling

I’ll admit that I have not looked through the other answers, so don’t kill me if this is a repeat.

The simplest method is for each person to toggle switch A if it is their first time in the room, and toggle switch B every subsequent time. Then you only have to count the number of times switch A changed state. I think this is the only method that will guarantee success.