I've been thinking about this in my spare moments for the past few
days and I think I have a solution. Hopefully there are no bugs in my
strategy (please let me know if there are). Here it is:
Choose one prisoner, call X
Rest of prisoners called R
-------------------
Strategy for X:
Initialize (in X's memory) a signal counter S = 0
IF NOT X's first time in room THEN {
IF state of switch B has changed where X left it last THEN {
IF switch B changed from on to off THEN yell "Shit!" break;
ELSE IF switch B changed from off to on THEN increment S
}
}
IF S >= 22 THEN declare "Everyone has visited" [much celebration];
TOGGLE switch B and remember its state
----------------------
----------------------
Strategy for all R's:
Note the position of switch B
IF you have seen switch B in an up state on a previous visit
AND you have NOT ever toggled switch B
AND switch B is currently in a down state
THEN TOGGLE switch B
ELSE TOGGLE switch A
------------------------
On Fri, Feb 07, 2003 at 05:42:31PM -0500, Kevin Tarr wrote:
>
> 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 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. 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 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 anyone 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."
>
> Here's the question:
>
> What is the strategy the prisoners devise?
--
"Erik Reuter" <[EMAIL PROTECTED]> http://www.erikreuter.net/
_______________________________________________
http://www.mccmedia.com/mailman/listinfo/brin-l
