12: One light switch [****]

Wes Carroll's Puzzler

For years you were a lonely prisoner here. But earlier today, you were brought to a courtyard to join the others, where you are all addressed by the Warden. There have been budget cuts, he explains, and the one hundred of you need to leave this facility. Whether you will be sent to another high-security facility, or set free, depends on whether you pass the following test of cleverness and teamwork. // There is a secret room not far from here, and like your individual cells, it is soundproof, lightproof, and in all other ways impervious to communication. The only object in this room is a single light switch, not connected to anything. It is currently in the off position. // In an hour, you will each be sent back to your cells. One of you will be selected at random to visit the room. While there, that prisoner may choose to flip the switch or not. No other actions will be permitted. Then another prisoner will be chosen at random. And again and again and again, over and over, always at random. // At any point, any of you may declare that all of you have visited the room. If the declaration is true, you will all go free. If not, then you will never again see the light of day. // You have one hour to formulate your strategy. // How will you arrange for everyone to go free? // Note: you have no idea how often prisoners will be sent to the room. Any solution whereby you try to “run out the clock” will be considered incorrect. A correct solution is one for which a declaration proves that all prisoners have visited the room at least once each. // Oh, one last thing: if it’s still not enough of a challenge for you, try solving the variant in which the switch starts in a random position. // (Spiciness: **** out of ****)