The locker puzzle (Q816387)

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).