Prisoners Dilemma

OK, one of these days I'm going to run out of puzzles. As it is, I think I am reaching the point where all my puzzles either are really simple or require the axiom of choice to solve. Anyway, this puzzle for this week is still a good one. I have learned this one many times in different incarnations, but this particular version was told to me by Bart:
There is a prison with 100 prisoners and a warden who likes to play bizzare games with them. In this particular game there is a room with two light switches in it. The light switches do not do anything, and can only be in the states up or down. Each day, the warden may select a prisoner and place them in the room. While in the room, the prisoner must flip exactly one of the switches and then is released from the room back to their cell. The prisoners are unable to leave any sort of messages in the room besides the positions of the light switches (the warden will always return the room the its initial state except for the switches).

On any day, any prisoner may declare "we have all been in the room at least once." If this declaration is made and is correct, the prisoners win and will all be released. If the declaration is made and incorrect, the prisoners lose and are killed.

It is promised that given enough time, each prisoner will enter the room arbitrarily many times. The prisoners may plan ahead of time, but then will never get to see eachother again until the game is over. Find a strategy that guarantees the prisoners victory.

Note that the prisoners do not know the initial configuration of the switches, and must always flip exactly one switch when they are in the room (you can make an easier version of this puzzle by modifying these facts). Also note that the warden does not have to place a prisoner in the room each day, so if you are in the room one day and in there again some days later, you do not know how many people have been in the room since. Finally, to make precise the statement that "given enough time, each prisoner will enter the room arbitrarily many times," I mean: For each prisoner P, for each integer N, there exists an integer K such that before day K prisoner P will have visited the room more than N times.

You may assume that the warden is an adversary, capable of meddling with any strategy to maximum effect (up to the rules of the problem). Also, do not worry about the finite lifetimes of the prisoners, that would just make this stupid, I suppose the prisoners are immortal or something.


Anonymous said...

I have a solution, but need to know how much mathematical bubble wrap I must surround it with to make it invulnerable. To that end:
Do the prisoners know on what schedule the warden is putting them into the room, and do they know when the 'game' starts?


kstevens said...

They know when the game starts, they do not know the wardens schedule. The warden has the ability to decide his schedule after the prisoners plan (adversaries tend to do that).

kstevens said...

Upon further consideration, they do not know exactly when the game starts. I'll amend the statement of the problem.