A warden meets with 23 prisoners. He tells them the following:

  • Each prisoner will be placed into a room numbered 1-23. Each will be alone in the room, which will be soundproof, lightproof, etc. In other words, they will NOT be able to communicate with each other.
  • They will be allowed one planning session before they are taken to their rooms.
  • There is a special room, room 0. In this room are 2 switches, which can each be either UP or DOWN. They cannot be left in between, they are not linked in any way (so there are 4 possible states), and they are numbered 1 and 2. Their current positions are unknown.
  • One at a time, a prisoner will be brought into room 0. The prisoner MUST change one and only one switch. The prisoner is then returned to his cell.
  • At any time t, given some N>0, there exists a finite t_0 by which time every prisoner will have visited room 0 at least N times. (In other words, there is no fixed pattern to the order or frequency with which
    prisoners visit room 0, but at any given time, every prisoner is guaranteed to visit room 0 again. If you’re still confused by this statement, ignore it, and you should be ok).
  • At any time, any prisoner may declare that all 23 of them have been in room 0. If right, the prisoners go free. If wrong, they are all executed.

What initial strategy is 100% guaranteed to let all go free?

Communicated by Steven Johnson.

WARNING: of all the riddles, this one gave me the hardest time!