Bright Idea - Futility Closet

A jailer will send each of a group of n prisoners alone into a certain room. Each prisoner will visit the room infinitely often, but the order of the visits will be determined arbitrarily by the jailer. The prisoners can confer in advance, but once the visits have commenced they can communicate with one another only by means of a light in the room, which they can turn on or off. How can they ensure that some prisoner will eventually be able to determine that everyone has visited the room?

	Select Click for Answer
The prisoners agree that one of them (say, Alice) will try repeatedly to turn the light on, and each of the others will turn it off twice. That is, if Alice finds the light off she’ll turn it on, and if she finds it on she’ll leave it on. Each of the others will turn it off the first two times he finds it on and otherwise leave its state unchanged. Alice counts the number of times she finds the room dark after her first visit. When she’s returned to find the room dark 2n – 3 times, she can announce that everyone has visited the room. Each time Alice returns to the room and finds it dark, that’s a sign that one of the other n – 1 prisoners has visited it. If a prisoner exists who still hasn’t visited the room, then the light can’t have been turned off more than 2(n – 2) = 2n – 4 times. So once Alice’s total exceeds that, reaching 2n – 3, she knows that everyone’s visited the room. (Note that the light’s initial state doesn’t matter: If the first visitor isn’t Alice and he finds the light on, he’ll turn it off, and that sign of his presence won’t be evident to her. But she’ll have to turn the light on again before he can perform his second off-turning, and that ensures that she’ll register his second visit.) (From Peter Winkler’s excellent Mathematical Puzzles: A Connoisseur’s Collection, 2003.)

Click for Answer