Saturday, November 8, 2008

Puzzle time!

One hundred prisoners and a warden agree to play the following game. Each day, starting tomorrow, the warden will select a prisoner at random and lead her to a room that contains nothing but a lamp standing in the center of the room. The prisoner may do one of three things:

1. Switch the lamp on if it is off, or switch it off if it is on, and then head back to her cell.

2. Do nothing and head back to her cell.

3. Announce: "All 100 prisoners have visited this room."

If a prisoner makes such an announcement, and she is correct, then all 100 prisoners will be set free. If not, all will be executed. The game will continue until someone makes an announcement.
Knowing that they are about to play, what strategy can the 100 prisoners agree upon to ensure their freedom? Assume that the lamp is initially on and that all prisoners know this. (Is there is a winning strategy even if the initial state of the lamp is not known?)


PS: This puzzle is from a book by Peter Winkler, and the solution will be posted once i can solve it or my copy of the book reaches me, whichever comes first (hopefully i'll be able to solve it myself).

>>Addendum:
So i wasnt able to solve it, and i could finally rest easy when i got a copy of the book. Select below text for solution.

The assumption is that no one fools with the room's light between visits by the prisoners. The prisoners don't need to know the initial state of the light. One prisoner (call her X) will always turn the light on whenever she goes in to the room, and each of the other prisoners, will turn it off the first two times that they find it on, otherwise leave it as is. After 2n-3 dark re-visits, the prisoner X can conclude that everyone has visited the room (n is ofcourse the number of prisoners).

Well that's the solution, you can still work on why is this the one that works.

2 comments:

Mayur said...

uh-oh, weird or i havent got what it is.

ferret said...

@Mayur
Think some more..

and let me know if you still need an explanation after that.