Associated Topics || Dr. Math Home || Search Dr. Math

### Elect a Spokesman

```Date: 07/02/2002 at 06:42:52
From: Vaibhav Kamthan
Subject: Puzzle

Ponder This Challenge from IBM (select July 2002):

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/

This puzzle has been making the rounds of Hungarian mathematicians'
parties.

The warden meets with the 23 prisoners when they arrive. He tells
them:

You may meet together today and plan a strategy, but after today you
will be in isolated cells and have no communication with one another.

There is in this prison a "switch room" which contains two light
switches, labelled "A" and "B", each of which can be in the "on" or
"off" position. I am not telling you their present positions. The
switches are not connected to any appliance. 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", and this prisoner will
select one of the two switches and reverse its position (e.g. if it
was "on", he will turn it "off"); the prisoner will then be led back
to his cell. Nobody else will ever enter the "switch room".

Each prisoner will visit the switch room arbitrarily often. That is,
for any N it is true that eventually each of you will visit the
switch room at least N times.)

At any time, any of you may declare to me: "We have all visited the
switch room." If it is true (each of the 23 prisoners has visited the
switch room at least once), then you will all be set free. If it is
false (someone has not yet visited the switch room), you will all
remain here forever, with no chance of parole.

Devise for the prisoners a strategy which will guarantee their
release.
```

```
Date: 07/21/2002 at 22:46:09
From: Doctor Shawn
Subject: Solution to this puzzle

One prisoner is designated as the "caller."  He and only he will make
the determination of when everyone's been in the room. Whenever he
sees that the left-hand switch is "down," he will move it "up" and add
1 to his count; otherwise, he will flip the right-hand switch and not
think anything of it. When the other prisoners enter the room, they
have a different strategy. If the left-hand switch is "up," they will
switch it "down," but they will only do this the first two times they
encounter the left-hand switch "up."  If they've moved the left switch
twice already, or if the left-hand switch is "down," they will flip
the right-hand switch.

When the caller's count is 44, each prisoner must have been in the
room at least once, regardless of the initial configuration of the
switches.

Neat problem.

For IBM's explanation, see (select July2002.html):

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/

-Doctor Shawn
http://mathforum.org/dr.math/
```
Associated Topics:
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search