This solution is a long one...
The
Almost
Right solution
The prisoners
get
together and nominate one prisoner as the "leader". All the
other prisoners are equivalent. The leader is going to count how
many
different prisoners have visited the switch room. When the count
equals
the number of prisoners, he goes to the warden and says "all the
prisoners
have visited", and everyone goes free. Here's the strategy for
the
followers and the leader:
Visit by a
follower:
Visit by the
leader:
That's
it! Each
prisoner will toggle switch A on exactly once. Only the leader
can toggle
switch A off, and he will count each time he does so. Each time
switch A
is on it means a different prisoner has toggled it. When the
count equals
the number of prisoners, you're done!
This works
because only
the leader turns switch A off. Only the followers turn switch A
on, and
they only do it once each. The key is that each prisoner can
remember
whether they've previously toggled switch A. Each time the
leader
turns switch A off, one more new follower has visited.
Note that the
switch room
basically has one state, held by switch A. The only purpose of
switch B
is to give each prisoner something to toggle if they don't want to
change the
state of switch A.
Make sure you
understand
my convoluted explanation before going on. Hopefully you will
have clear
that the switch room holds one state, and how the leader and the
followers
interact.
The
problem
with the Almost Right solution
A key
complication in the
puzzle is that the initial state is not known. If the initial
state were
known - let's say the switches were both off - then there would not be
a
problem, and we'd be done. But this complication actually means
the strategy
outlined above won't work exactly right. Here's why. The
initial
state of switch A can be either off or on. If switch A is off,
there is
no problem. If a follower visits first, they'll toggle switch A
on, and
when the leader visits, he'll toggle switch A to off and the count will
be
one. If the leader visits first he'll do nothing since switch A
is
already off. All will be cool. But if the initial state of
switch A
is on, then there's a problem. Nothing will happen until the
leader
visits, and he'll toggle switch A off and set the count to one.
But - his
count will be off by one! The leader cannot tell the difference
between
'initial state off, one follower visited' and 'initial state on, zero
followers
visited'. This matters because if the leader is off by one, he'll
either
wait forever for a last follower who doesn't exist (prisoners remain
prisoners), or he'll tell the warden everyone has visited when one
prisoner
still hasn't (prisoners fed to alligators). So - what to do?
The crux of
the complication
is that the leader can't know whether the first "switch A on" was
created by a follower. So the solution has to be - nobody can do
anything
until the leader has visited at least once.
The
Right
solution
The prisoners
get
together and nominate one prisoner as the "leader". All the
other prisoners are equivalent. The leader is going to count how
many
different prisoners have visited the switch room. When the count
equals
the number of prisoners, he goes to the warden and says "all the
prisoners
have visited", and everyone goes free. Here's the strategy for
the
leader and the followers:
Visit by a follower:
If switch A is on, toggle switch B.Visit by the
leader:
The additions
to the
strategy are italicized. Each follower must remember two things,
1)
whether they've seen switch A on during any previous visit, and 2)
whether
they've previously toggled switch A. They must have seen switch A
on
before toggling it on themselves, and they will only toggle it on
once.
The leader must remember two things also, 1) whether he toggled switch
A on
during his previous visit, and 2) the current count of followers who
have toggled
switch A.
To see how
this handles
the initial state complication, let's consider the possibilities.
If the
initial state of switch A is off, then nothing will happen until the
leader
visits, because no follower will have previously seen an on
state. If the
initial state of switch A is on, then again nothing will happen until
the
leader visits, because only he can turn switch A off. Since
nothing
happens until the leader visits, the initial state ambiguity is
settled; the
leader can be sure that the state of switch A has not been disturbed
since the
start.