This problem was initially created as an analogy for a strategy of searching for a substring in a given data structure. Gal and Miltersen were aiming to prove a lower limit for query time for substring search, but the problem would go on to gain popularity as an independent exercise. In the original paper, the authors mention that Sven Skyum found that in the case where n=m (there are an equal number of slips of paper as boxes for them to go into), "the team can win the game with probability bounded from below by a constant (roughly 0.3)" for arbitrarily large values of m. Gal and Miltersen's paper does not include Skyum's solution. The problem's popularity as a thought exercise seems to come from a collection of mathematical puzzles presented by Peter Winkler at the 7th Gathering for Gardner (Winkler 2006). Winkler presents a slightly modified version of Gal and Miltersen's game. Winkler's version is the currently used version of the puzzle and appears to be the first to introduce the prisoners context that gives the puzzle its current name (Winkler simply calls this puzzle "Names in Boxes").
Back to top