I got this problem from Rustan Leino, whom Tom Ball told (a close variation of) this problem.

The problem has been featured as a Car Talk Puzzler under the name "Prison Switcharoo". But, if you can find that page, beware: the Car Talk problem page also contains an answer.

I solved it and wrote up my solution.

$N$ prisoners get together to decide on a strategy. Then, each prisoner is taken to their own isolated cell. A prison guard goes to a cell and takes its prisoner to a room where there's a switch. The switch can either be up or down. The prisoner is allowed to inspect the state of the switch and then has the option of flicking the switch. The prisoner is then taken back to their cell. The prison guard repeats this process infinitely often, each time choosing fairly among the prisoners. That is, the prison guard will choose each prisoner infinitely often.

At any time, any prisoner can exclaim "Now, every prisoner has been in the room with the switch." If, at that time, the statement is correct, all prisoners are set free; if the statement is not correct, all prisoners are immediately executed. What strategy should the prisoners use to ensure their eventual freedom?

Clarifications:

• The initial state of the switch is unknown to the prisoners.
• The state of the switch is changed only by the prisoners.
• The prisoners' only means of communication with each other, once they've finished strategizing, is via the switch's position.
• The switch cannot be in any state other than up or down.

If $N = 1$, the prisoner can just make the exclamation upon entering the room with the switch. So, we'll assume from now on that $N > 1$.

The Strategy

The prisoners should choose one of themselves to act as the downer. The rest will act as uppers.

Each upper does the following. If the switch is down when they enter the room, they flip the switch up, unless they've already flipped the switch up twice.

The downer does the following. If the switch is up when they enter the room, they flip the switch down. Then, if they've flipped the switch down $2N-2$ times, they make the exclamation.

Why it Works

First, we need to show that this strategy is safe, i.e., that the exclamation will never be made when it will cause the prisoners to die. Second, we need to show that it's live, i.e., that eventually the exclamation will be made.

Here's why the strategy is safe. Suppose that the downer is in the room, but fewer than $N$ prisoners have ever been to the room. The downer has been in the room, so this means that fewer than $N-1$ uppers have been to the room, i.e., at most $N-2$ uppers have been to the room. Each of these uppers can have flipped the switch up at most twice, so the number of up-flips so far is at most $2(N-2)$. Each down-flip can only occur after an up-flip, except for the very first down-flip which might occur just because the switch started out up. Thus, the number of down-flips so far is at most $2(N-2)+1 = 2N-3$. The downer only makes the exclamation if their down-flip count is at least $2N-2$, so they can't make an exclamation in this situation. Thus, the exclamation is never made when fewer than $N$ prisoners have been to the room.

Here's why the strategy is live. First, we'll show that whenever the down-flip count is less than $2N-2$, at some future point it must increase by one. There are two cases to consider when the down-flip count is less than $2N-2$.

• If the switch is up, the prison guard's fairness requirement will cause them to eventually choose the downer, who will flip the switch down and thereby increase the down-flip count.
• If the switch is down, then the up-flip count can't be greater than the down-flip count, because otherwise the switch would have to be up. Thus, the up-flip count must also be less than $2N-2 = 2(N-1)$. This means that, of the $N-1$ uppers, at least one must not have flipped the switch up twice. The prison guard's fairness requirement will cause them to eventually choose one of the uppers who hasn't flipped the switch up twice. The first time this happens, that upper will flip the switch up. Then, the prison guard's fairness requirement will cause them to eventually choose the downer, who will flip the switch down and thereby increase the down-flip count.

This covers all the cases, so we know that whenever the down-flip count is less than $2N-2$, it will eventually increase by one. Thus, eventually the down-flip count reaches $2N-2$, which causes the downer to make the exclamation.