← All puzzles

The Last Uncounted Visitor

brainteaser
A warden places 100 prisoners in separate cells. Before isolation, they may agree on a strategy and appoint one prisoner to act as the counter. Afterward, the warden repeatedly chooses one prisoner and sends that person alone into a room containing a single light switch. Prisoners may be chosen many times and in any order, but every prisoner will eventually visit the room. No communication is possible except through the switch. The switch begins in the OFF position, and everyone knows this. During each visit, the prisoner may inspect the switch and either leave it unchanged or flip it. At some point, the counter must announce that all 100 prisoners have visited at least once. A wrong announcement is disastrous. Using the standard strategy in which each non-counter prisoner signals exactly once, how high must the counter count before making the announcement?

Hints

Hint 1
Hint 2
Hint 3

Solution

Commit an attempt to unseal the proof. Write your answer — right or wrong, thinking it through is the point.

How high must the appointed counter count?

Rate this puzzle
Report a problem with this puzzle

Comments

No comments yet

Be the first to say something about this puzzle.