The locker puzzle
In the Locker Puzzle game, Player \(A\) is pitted against Team \(B\) consisting of \(2n\) members numbered from 1 to \(2n\). Player \(A\) distributes \(2n\) slips of paper numbered from 1 to \(2n\) randomly among \(2n\) lockers numbered from 1 to \(2n\), placing 1 slip into each locker. The members of Team \(B\) are then admitted into the locker room one at a time and each is allowed to open and examine the contents of \(n\) lockers. Team \(B\) wins if every team member discovers the locker containing his or her own number. Members of Team \(B\) may confer in advance on a strategy, but no communication is allowed after the first team member is admitted to the locker room. While at first sight it appears that Team \(B\) has probability only \((.5)^n\) of winning, there is in fact a strategy giving them a probability of over \(0.3\) of winning. This strategy is shown to be optimal, given that Player \(A\) must distribute the slips in a random manner. The problem originally appeared in the paper of \textit{Ana Gál} and \textit{Peter Bro Miltersen}, ``The Cell Probe Complexity of Succinct Data Structures, Proceedings of 30th International Colloquium on Automata, Languages and Programming (ICALP), 332--344 (2003).
- Inglenook shunting puzzles
- Prisoners, rooms, and light switches
- The Mensa Correctional Institute
- Iterating the locker problem
- On partial information retrieval: the unconstrained 100 prisoner problem
- Haystack hunting hints and locker room communication
- Haystack hunting hints and locker room communication
- The Prisoners and the Swap: Less than Half is Enough
This page was built for publication: The locker puzzle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q816387)
