Problem of the Week 1047

Locker Room Dilemma

Alice, Bob, Charlie, and Diane are prisoners under the supervision of warden Stan. One day the warden takes the ID cards from each prisoner and places them randomly in different lockers in a locker room. The locker room consists of four numbered lockers each with a curtain instead of a door. The curtains are marked 1, 2, 3, and 4. On the next day the prisoners will be taken, one at a time, into the locker room, where they can choose a curtain and look behind it. If they see their own ID card, they are said to be successful. Otherwise, they get to open a second curtain and again, if they see their own ID card, they are successful; otherwise they are failures. As they leave the locker room they cannot communicate with the others. And as they enter the locker room they have no way of telling if a previous prisoner was successful or has looked into any specific locker.

If all four prisoners are successful, then they will all be released; otherwise, back to the cells for everyone.

The prisoners know the protocol and can get together in advance to decide on a strategy. For example, they might decide that each should open two lockers at random. Such a strategy would mean that each prisoner succeeds with probability 1/2, and so the group of four is successful with probability 1/16, or 6.25%. Find a strategy whose probability of success is over 40%.

Extra Credit: Suppose there are 2m prisoners and each can look into m lockers. Find a strategy that is asymptotically positive as m goes to infinity.

Source: Thanks to Joe Buhler for the suggestion. The puzzle itself originates from the paper "The Cell Problem Complexity of Succinct Data Structures," by Peter Bro Milterson and Anna Gál. The language in the paper, however, is quite different than that used here. The problem is discussed in detail in "The Locker Puzzle," by E. Curtin and M. Warshauer, The Mathematical Intelligencer (2006:1)28-31.

© Copyright 2006 Stan Wagon. Reproduced with permission.