Combinatorial Communication in the Locker Room
share
The reader may be familiar with various problems involving prisoners and lockers. A typical set-up is that there are n lockers into which a random permutation of n cards are inserted. Then n prisoners enter the locker room one at a time and are allowed to open half of the lockers in an attempt to find their own card. The team of prisoners wins if every one of them is successful. The surprising result is that there is a strategy which wins with probability about 1-ln 2. A modified problem in which helpful Alice enters before the prisoners, inspects the whole permutation and swaps two cards improves the winning probability to 1. In our problem, there are n lockers and n cards and a helpful Alice just as before, but there is only one prisoner, Bob. If Bob may only open one locker, their chance of success is less than 2.4/n, but our main result is that, if Bob can open two lockers, their chance of success is c_n/n where c_n→∞ as n→∞. For this, Alice and Bob have to achieve effective communication within the locker room. We show asymptotically matching upper and lower bounds for their optimal probability of success. Our analysis relies on a close relationship of this problem to some intrinsic properties of random permutations related to the rencontres number (which is the number of n-permutations with a given number of fixed points).
READ FULL TEXT