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:

This article was edited after publication by the author on 07 Jul 2010. View changes.
-1 Vote

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…

1 Vote
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 least as 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.

``````using System;
using System.Collections.Generic;
using System.Text;
namespace Prisoners
{
class Program
{
static void Main(string[] args)
{
bool A = false; //switch A
bool B = false; //switch B
Random r = new Random(DateTime.Now.Millisecond); //Random Seed with time
int[] Prisoner = new int[23]; // 23 prisoners
int x = 0;
int c = 0;
while(Prisoner[0] < 22) //Prisoner 0 is the scorekeeper, when 22 is reached were done.
{
x = r.Next(0, 23);  // Get next random prisoner
c++;
if (x == 0)    //"counter" prisoner is in room
{
if (B == true)
{
B = FlipB(B);
Prisoner[0]++;     //counts that switch B was turned off
}
else
{
A = FlipA(A); //just flip A
}
}
else // any other prisoner enters room
{
if (B == false && Prisoner[x]==0) //if B switch is off and prisoner hasn't already switched it once
{
B = FlipB(B);
Prisoner[x]=1; // mark that this prisoner switched B on.
}
else
{
A = FlipA(A); // only flip A
if (Prisoner[x] > 0)
Prisoner[x]++;  //for fun, see how many room entries
}
}
}
//output
for (x = 0; x < 23; x++)
{
Console.WriteLine("Prisoner {0:G} -- {1:G} ", x+1, Prisoner[x]); //# of Prisoner visits
}
Console.WriteLine("\nGuard Visits {0:G}", c);
}``````
``````   static bool FlipA(bool A)
{
if (A == true)
{
A = false;
return A;
}
if (A == false)
{
A = true;
return A;
}
return A;
}``````
``````   static bool FlipB(bool B)
{
if (B == true)
{
B = false;
return B;
}
if (B == false)
{
B = true;
return B;
}
return B;
}
}
}``````

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.