Prisoners and a glass that can be flipped
Question
Fifty prisoners are held in isolation. Each minute one of them, chosen in any order by the captor, is brought into a room containing a single glass, which he may leave alone or turn over. They all go free if at some point one prisoner correctly announces that every prisoner has visited the room at least once; a wrong announcement means death for all. They may agree on a plan only once, before being separated. Is there a plan that guarantees success?
Short answer
Yes. Appoint one counter. Every other prisoner turns the glass from up to down the first time he finds it up, and never touches it again; the counter turns it back up whenever he finds it down and adds one to his tally. When his tally reaches , all others have visited and he announces. (This assumes everyone is called infinitely often and the glass starts in a known state.)
Adapted from OpenQuant; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solutionLessons behind this question
- Counting and Combinatorics
- Sample Spaces, Events, and the Probability Axioms
- Conditional Probability, Total Probability, and Bayes' Rule
Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.
Read it free