100 Prisoners and Attic Switch Puzzles

This was posted on the Summer Accepted 2006 list by Christoph.

Imagine a prison. No way to escape. 100 prisoners are kept in solitary cells,
they cannot communicate at all. The guard proposes a little game to the
prisoners – if they can solve it they will be released. Before the game
starts all prisoners are allowed to communicate for 5 minutes.

Rules of the game:

1. Every day one prisoner will be brought into a small, empty room. The only
interesting thing in the room are two switches on the wall. Each prisoner
has to change the state of one or both switches as he prefers. Nothing
happens when the state of a switch is changed.
2. A single prisoner can be brought into this room multiple times before
another prisoner is brought in once. There is no order after which the
prisoners are chosen. The prisoners have not the slightest idea who will
be next. At one day in the future every prisoner will have been in the
room once – but this can be in 1 or also 10 years.
3. If any of the prisoners is able to tell that _every_ prisoner has been in
the small room at least once, all prisoners are freed. If he is wrong and
there is only a single prisoner that hasn’t been in the room yet, all will
be killed.
4. There is no way to communicate during the process other than using the
two switches. Each single switch is binary (has only the states ON and
OFF). They cannot write something on the walls or leave anything in the
cell. The guard will never tough/change the switches or communicate any
messages.

I ran a few searches (I tried Google first, and then used Yahoo when Google failed), and quickly found the answer (I thought about it too, but couldn’t figure it out). Then I also found this puzzle:

Downstairs there are three light switches on panel. You are told only that one switch will turn on a light in the attic (which cannot be seen from the basement). With just one trip from the ground floor to the attic is it possible to determine which of the three switches operates the attic light?

The only way I found the answer to this one was by using Amazon.com’s Online Reader to “Search Inside the Book.” Thank goodness for that. I think I’ll buy that book now :) Amazon deserves it. The answer’s quite clever in my opinion. Can you figure it out? (Without looking it up!)