The Locker Problem with Empty Lockers

Authors: David Avis, Luc Devroye, Kazuo Iwama

Abstract:

We consider a cooperative game played by n players against a referee. The players names are randomly distributed among n lockers, with one name per locker. Each player can open up to half the lockers and each player must find his name. Once the game starts the players may not communicate. It has been previously shown that, quite surprisingly, an optimal strategy exists for which the success probability is never worse than 1 − ln 2 ≈ 0.306. In this paper we consider an extension where the number of lockers is greater than the number of players, so that some lockers are empty. We show that the players may still win with positive probability even if there are a constant k number of empty lockers. We show that for each fixed probability p, there is a constant c so that the players can win with probability at least p if they are allowed to open cn lockers.

Keywords: Locker problem, pointer-following algorithms.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077499

References:

[1] D. Avis and A. Broadbent. The quantum locker puzzle. ICQNM09, Cancun, February 2009.
[2] E. Curtin and M. Warshauer. The locker puzzle. The Mathematical Intelligencer, 28(1):28-31, 2006.
[3] A. G'al and P. B. Miltersen. The cell probe complexity of succinct data structures. In Proceedings of the 30th International Colloquium on Automate, Languages and Programming (ICALP), pages 332-344, 2003.
[4] A. G'al and P. B. Miltersen. The cell probe complexity of succinct data structures. Theoretical Computer Science, 379(3):405-417, 2007.
[5] N. Goyal and M. Saks. A parallel search game. Random Structures and Algorithms, 27(2):227-234, 2005.