The Lumber Room

"Consign them to dust and damp by way of preserving them"

Eugene Curtain and Max Washauer

with 7 comments

If you came here because you were reading Peter Winkler’s “7 Puzzles You Think You Must Not Have Heard Correctly”, the names are supposed to be Eugene Curtin and Max Warshauer, and the paper is called “The locker puzzle”, published in The Mathematical Intelligencer, Volume 28, Number 1 (March 2006), pages 28–31.
[If not, you should read the amazing "7 Puzzles You Think You Must Not Have Heard Correctly", spend several days trying the first problem, read the brilliant solution, and then come back here if you're interested in learning why no other solution can do better.]

The paper is available here if your institution has access. If not, here’s a sketch of the proof that the strategy cannot be improved upon. [Update 2010-01-06: Oliver Nash has a post about the puzzle, explaining both the original solution and the proof of optimality, here. Just the original solution is also worked out by David MacKay here.]

First, let us modify the rules slightly so that each prisoner must continue looking in boxes until he finds the box containing his name. The prisoners win if no prisoner opens more than 50 (i.e., n/2) boxes. This change obviously makes no difference to the outcome. Let’s call this (modified) game Game 1.

A different game involves all the prisoners being in the room at the same time, and is played as follows. The first prisoner opens boxes until he finds his name (i.e., the number “1”). Then, the lowest-numbered prisoner whose name hasn’t been revealed starts opening boxes until he finds his name. Then the next lowest-numbered whose name hasn’t been revealed opens boxes, and so on. The prisoners win if no one opens more than 50 boxes. Call this Game 2.

Let’s say we observe the prisoners as they play Game 2, and record the order in which boxes were revealed. This completely specifies what happened. For example, (with 10 prisoners instead of 100) if we record the list 2,6,1,4,9,7,10,8,3,5, we know that the first prisoner revealed boxes containing 2, 6, 1, then the third (lowest unrevealed) prisoner opened boxes with 4,9,7,10,8,3, then prisoner 5 opened 5, and they lost because the third prisoner opened 6 > 5 boxes.

  • Prove: No matter what strategy the prisoners follow, each permutation has the same probability (1/n!) of being the list recorded.
  • Prove: “The classical records-to-cycles bijection”. It sends 2,6,1,4,9,7,10,8,3,5 to (2 6 1)(4 9 7 10 8 3)(5), for example.
  • So the probability of the prisoners winning Game 2 (no matter what strategy they follow) is exactly the probability that a random permutation has no cycle of length greater than n/2.
  • Prove: Any strategy for Game 1 corresponds to a strategy for Game 2 with the same probability. (Trivial: the only change is that you don’t have to open boxes you’ve already seen opened.)

This proves that the pointer-chasing strategy is optimal for Game 1.

Here’s the puzzle as it was originally considered, still open: suppose there are n prisoners and 2n boxes, half of them empty. The prisoners can each examine n lockers. The pointer-chasing strategy doesn’t work as empty boxes point nowhere. Does the probability of winning go to 0 as n→∞?

About these ads

Written by S

Mon, 2009-08-10 at 23:45:25 +05:30

7 Responses

Subscribe to comments with RSS.

  1. “Does the probability of winning go to as n→∞?”

    go to 0?

    Preyas

    Tue, 2009-08-11 at 03:16:13 +05:30

  2. Here’s a perl program that implements the algorithm described in Dr. Winkler’s document.

    It does worse than randomly selecting half the boxes to open would, due to cycles. When the prisoner first selects a box that happens to be in a cycle with length 50 or less, he just spins there and has less chance of finding his own box.

    My conclusion after examining this problem was that it was not a serious lecture note but rather a “find the fallacy” kind of assignment, but in e-mail with Dr. Winkler he seems to believe that it is supposed to work.

    Having been fooled by the monty hall problem for some time until I wrote a simulation that verifies the correct answer, I now doubt my intuition in these matters, thus the time spent pondering this.

    After reading the “explanation” above, I’m now thinking that the general error that is being made is making a false leap from a valid proof of “Any strategy for Game 1 corresponds to a strategy for Game 2 with the same probability.” to an entirely specious “Any strategy for Game 2 corresponds to a strategy for Game 1 with the same probability.”

    I do not expect to see a practical demonstration of how to choose one box from one hundred in fifty tries with a 99% success rate, which is what is required to get a 30% success rate for 100 consecutive trials, ever.

    See perl code at http://davidnicol.diaryland.com/100priz.html

    David Nicol

    Tue, 2009-09-22 at 13:29:51 +05:30

    • Thanks for the comment. I took the liberty of commenting out the code since you said the formatting was better on your website.

      One clarification: the explanation in my post is not for showing that the pointer-chasing strategy works more than 30.68% of the time — that is already proved by Dr. Winkler in his http://www.math.dartmouth.edu/~pw/solutions.pdf — but for showing that no other strategy can do better, which he just mentions (with references).

      That said, there is no fallacy in the solution; the strategy does work more than 1-ln(2) of the time. :-) It is not at all necessary that the first prisoner have a 99% success rate (in fact, his success rate turns out to be exactly 50%), because their outcomes are not independent. The intuition is that when there is a cycle of length more than 50 (which happens less than 69.32% of the time), lots of them will fail together, but when there are only short cycles, all of them will succeed. (There’s another explanation of the solution here by David MacKay with the maths worked out.)

      So there’s at least one bug in your code. :-) I haven’t read through it carefully, but I ran it and it seems to print lots of “FAILED at p=” with no number after the “p=”.
      Also, there seem to be bugs in your understanding of the problem and solution:
      * The prisoners all have distinct names, and they choose to work out a labelling of their names that gives each of them a distinct number from 1 to 100 (i.e. a permutation of 1 to 100) — your “hash” of simply taking a number mod 100 is almost certainly going to have at least one collision. The easiest way to avoid this in your code is to simply make their “names” 1 to 100; you’re shuffling the boxes anyway.
      * When a prisoner starts examining a cycle of length less than 50, he will find the box with his name in it, because prisoner k starts with box_k and following the permutation along the cycle will eventually find the box with name_k in it. (This is either the definition of a cycle in a permutation or an easy and fundamental property of permutations, depending on how you define cycles.)

      Shreevatsa

      Tue, 2009-09-22 at 18:33:05 +05:30

  3. Yes. After reviewing the “Locker Puzzle” article and pondering further, I better understood the strategy.

    My problem was interpreting “a random labeling of the boxes by their own names” to mean any name->box function, instead of a full name <–> box correspondence.

    Thanks for your patience, my faith in the wisdom of academia has been restored.

    David Nicol

    Wed, 2009-09-23 at 13:35:06 +05:30

    • It’s a very very surprising puzzle, isn’t it? I had become very convinced that it was impossible to solve it, before I looked at the solution. :-)

      I wrote some code for implementing it anyway. Here it is below, in Python. (Without loss of generality we can assume that the prisoners’ “names” are 0 to 99.) It is nice to confirm (by looking at 100000 trials or so) that the success probability for 100 prisoners is exactly the 31.18% predicted by the theory.

      import random
      N = 100               # The number of prisoners
      failures = trials = 0
      while True:
          trials += 1
          b = range(N); random.shuffle(b) #The boxes
          for p in range(N):              #The prisoners
              # Prisoner p looks in at most N/2 boxes
              found=False
              w = p      #Which box to look at next
              looked = 0 #Number of boxes looked in so far
              while looked<N/2:
                  looked += 1
                  #print "Prisoner %d looked in box %d, saw %d" % (p, w, b[w])
                  if b[w]==p:
                      #print "Prisoner %d found his name after looking in %d boxes" % (p, looked)
                      found = True
                      break
                  w = b[w]
              if not found:
                  failures += 1
                  break
          print "After %d trials, %d failures and %d successes, so %f percent success" % (trials, failures, trials-failures, (trials-failures)*100.0/trials)
      

      Shreevatsa

      Wed, 2009-09-23 at 14:47:38 +05:30

      • Jinx! While you were writing your python demonstration, I fixed the code on my blog so it converges to the expected success rate.

        David Nicol

        Wed, 2009-09-23 at 15:12:07 +05:30


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 67 other followers