A warden meets up 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 is a switch room, which contains two light switches labeled
1 and 2, each of which can be in either up or the down position. I am
not telling you their present positions. 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 flip one switch
when he visits the switch room, and may only flip one of the switches.
Then he'll be led back to his cell.
"No
one else will be allowed to alter the switches until I lead the next
prisoner into the switch room. 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. I will not touch the switches, if I wanted you dead you
would already be dead.
"Given
enough time, everyone will eventually visit the switch room the same
number of times as everyone else. At any time, anyone 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 all die horribly. You
will be carefully monitored, and any attempt to break any of these
rules will result in instant death to all of you"
What is the strategy they come up with so that they can be free?
