Not Really A Dilemma

So, I always hate it when people misuse the word dilemma, I mean seriously now, its supposed to be a problem involving two choices. If you don't have exactly two choices its not a dilemma. Naturally, that didn't stop me from breaking this rule when I posted the problem last week and titled it prisoners dilemma. Whatever, anyway, lets have a look at the solution now.

First of all, its important to realize the two switches and the manditory flipping thing is a big ol' red herring. You can just use the switch on the right as a "dummy switch" and the switch on the left as your real switch. You flip the right switch if you are in the room and do not feel like flipping the left switch. So now there is just one switch in the room and flipping it is optional.

Next, the problem is alot easier if we assume that the prisoners know the initial position of the switch. So, let us assume that the switch starts in the up position. The solution is begins by having one person designated to be the "master" who will count off the prisoners by being the only person to flip the switch to up. The strategy for every prisoner who is not the master is:

If the switch is down, do nothing.
If the switch is up, then flip it down if you have never flipped it down before. If you have flipped it down before, do nothing.

The strategy for the master is:

If the switch is up, do nothing.
If the switch is down, flip it up.
If you have flipped it up 99 times, declare that all 100 prisoners have been in the room.

So flipping the switch up declares a prisoner to be 'counted', and each prisoner will be counted exactly once. Its interesting to ask how long it takes for this strategy to work assuming the warden picks prisoners at random, I'll get to that next week.

This strategy might even work if you don't know the initial position of the switch (because it might start as up anyway), but if it started as down then the master will count a prisoner that wasn't actually there and the warden (being an adversary) will arrange things so that you lose.

You could try to solve that by having the master count to 100, but then if it had started as up you will never manage to end the strategy, as nobody will ever make the last flip (and you will never be sure it isn't just the warden holding out on you).

So, with an unknown initial switch position it is a bit harder. You can deal with this by counting everybody off twice. Agian, designate a master, the strategy for any prisoner who is not the master is:

If the switch is down, do nothing.
If the switch is up, then flip it down if the number of times you have flipped it down before is one or zero. If you have flipped it down twice before, do nothing.

So now each prisoner will ask to be counted exactly twice. The strategy for the master is:

If the switch is up, do nothing.
If the switch is down, flip it up.
If you have flipped it up 198 times, declare that all 100 prisoners have been in the room.

Counting to 198 is counting every one of the "non-master" prisoners twice. Now, if the switch started as down, then you counted that once, but that does not matter. All that would mean is that there is a prisoner out there that you only counted once, which is good enough anyway.

Calculating how long this strategy takes is much harder, and I am still working on the solution to that.