There are 23 prisoners who will each be put into solitary confinement tomorrow. After they are in solitary confinement, a prison guard will take them each into a room, one at a time. He will choose them randomly and repeatedly, so that over a long period of time, each prisoner will probably be brought into the room multiple times. The room has two light switches in it, which are either in the on or off position and are not connected to anything. (The switches do not turn anything on or off.) The starting position of the switches is not known. Whenever a prisoner is brought into this room, she must change the position of exactly one switch. (A prisoner cannot change the position of both switches, nor can she choose to leave them both in the positions that they are in.) All of the prisoners will be released if any prisoner says, “All 23 prisoners have been inside this room,” and it is true when the prisoner says it. If it is false when a prisoner says it, then they will all be executed immediately. What strategy can the prisoners use that will ensure their release?
If the prisoners designate one switch (the one on the right, say) to be the “counting switch” and they designate one prisoner to be the counter, and they designate one switch position of that switch (up/on, say) to be the “I’ve been in this room” position, then this strategy would almost work: If you go into the room and the counting switch is in the down/off position and you’ve never changed the position of the counting switch before, then you change it, to indicate your presence. If you go into the room and the counting switch is already in the up/on position, then you don’t change it, you change the position of the other switch. You leave the counting switch alone because it indicates someone else’s presence and also indicates that the counter has not counted that person’s presence yet. Whenever the counter comes in and sees that the counting switch is in the up/on position, she adds another number to her tally and resets the counting switch to the down/off position so that it is ready for the next not-yet-counted prisoner who enters the room. After she observes the switch in the up/on position 22 times (she doesn’t need to count her own presence via a switch position), then she can be sure that all 23 prisoners have been inside the room.
That strategy only almost works, because they don’t know the starting position of the switches, and if you don’t know the starting position of the switches, then you can’t be sure that 22 up/on positions indicate 22 flips by prisoners—22 up/on positions might be 21 flips by prisoners plus the one from the starting position. If the 22 up/on positions have been caused by the starting position and 21 flips, then there is still one flip that the counter should be waiting for. But if the counting switch started in the down/off position, then the 22 up/on positions were caused by 22 prisoner flips, and there is nothing more to wait for. At this point, the counter would be stuck, unless the switch happened to flip up a 23rd time—then the counter would know that the 23 flips were due to the starting position of the switch (up/on) and 22 prisoner flips.
To get around this, the strategy needs to be for each prisoner to flip the counting switch up/on not just once but twice. If they do this, then the counter waits to see 44 up/on positions instead of 22 on/up positions. 44 up/on positions might be caused by the starting position and 43 prisoner flips, but with 43 prisoner flips the counter will know that 21 prisoners have flipped the switch twice, and what the counter won’t be sure of is whether the 22nd prisoner flipped the switch once or twice. But the counter will know the 22nd prisoner flipped it at least once, and so the counter will know without a doubt that all 22 of the other prisoners have been inside the room.