The King of Freedonia has caught 10 spies from the Kingdom of Sylvania who attempted to poison his wine. The King of Freedonia keeps 1000 bottles of wine in his cellar. The spies managed to poison one of the 1000 bottles but were caught before they could poison any more. The poison is a very special one that is deadly even at one-millionth the dilution of the poisoned wine bottle and takes exactly 24 hours to kill the victim, producing no symptoms before death.
The trouble is that the King doesn’t know which bottle has been poisoned and the wine is needed for the Royal Ball in exactly 24 hour’s time! Since the punishment for attempted regicide is death, the King decides to feed some of the wine to the spies. The King informs his executioner that he will be able to identify the poisoned bottle by the time the ball starts and kill at most 8 of the spies, leaving 2 alive to be interrogated. Further, each spy drinks only once.
How does he do it?
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?