Last Wednesday night I attended a "Math Encounters" program co-sponsored by the soon-to-open Museum of Math in New York City. In 2008, Glen Whitney, a mathematician and former hedge fund manager, was dismayed to learn that a small museum dedicated to math in Long Island was closing. He decided to start a math museum himself. In just a few years, he raised the required funds, and the museum, the only such institution dedicated to math in North America, will open in December 2012.
Each Math Encounter (Wednesday's was the "umpteenth," according to Whitney) features of a public program led by a mathematician. Last night, Peter Winkler, a Dartmouth mathematician and author of two math puzzle books, gave a talk, "Intuition Gone Awry: Puzzles to S-T-R-E-T-C-H Your Mind," at Baruch College. I thought I'd dive into one of the puzzles he presented. I have seen it floating around before, but it never fails to astonish me.
The situation, like so many math puzzle hypotheticals, is a bit far-fetched: A prison has 100 prisoners, and the sadistic warden has decided that tonight, all the prisoners will be set free or die. In order to toy with them, the warden decides that they will determine their own fate. In a separate room, he will write down each prisoner's name and put it in a box at random. One by one, the prisoners will enter the room and open 50 boxes each. If every prisoner opens the box with his own name, the prisoners all live. If any prisoner fails to find his name, all the prisoners will die. The prisoners can decide on a strategy beforehand, but they cannot confer once the first prisoner has begun opening boxes. What should the prisoners' strategy be to maximize their chance of seeing another dawn?
It is clear that random choices on the part of each prisoner will not lead to a very high success rate. Each prisoner has a 50 percent chance of finding his name, but the chance of two prisoners succeeding is only 1⁄21⁄2=1⁄4, or 25 percent. The chance of three is only 1⁄21⁄21⁄2=1⁄8, or 12.5 percent. By the time we get all the way to 100, the probability is only ()100=7.910-31=0.000000000000000000000000000079%. (Yes, I counted all the zeroes.) To understand how unlikely this is, consider that if this scenario had transpired every nanosecond since the Big Bang, there would still be less than a 1 in 100,000 chance that the prisoners would ever have survived. Can we improve the odds to one in a million? One in a thousand? Believe it or not, we can do a lot better: there is a strategy that saves the prisoners more than 30 percent of the time.
When I first encountered this puzzle, the prisoners were each assigned a number at the outsetand they found numbers, not names, inside the boxes, which I think led me to find the idea of the solution more quickly. So from now on we'll assume that the prisoners alphabetized themselves and assigned numbers based on that order, although any numbering would work. (This is ever so slightly different from the original problem because it gives the warden extra knowledge, and he could choose a strategy to ensure the prisoners' doom. Assuming that he assigns the numbers to boxes at random takes care of this difficulty.)
It's not easy to come up with a box opening strategy that isn't random. But as I often tell my students when I am tutoring math, if you don't know what to do, do something. Do the only thing you can think ofit beats doing nothing. So that's what I did. One way a prisoner could decide which box to open is to start at random and then use the contents of the box to decide which one to open next. For example, if prisoner 1 opens box 5, and box 5 contains the number 7, the prisoner will open box 7 next, and then open the box whose number is in box 7.
It turns out that this has the seed of the right strategy in it. The only thing missing is how to choose the first box to open, and it turns out that each prisoner should start with his own number. Full disclosure: I did not figure out the answer on my own, but I had a lot of fun talking about it with my fellow math graduate students, and eventually one of them let us in on how to solve it.
To take a look at how this strategy works, I'll follow Winkler's lead and use a "baby" example with just 10 numbers, as he did in last Wednesday's presentation. We need to think of the assignment of numbers to boxes as a permutation, a way to order the set of numbers from 1 to 10. Let's say the permutation corresponding to the boxes is:*
The number on the top row represents the box number, and the number on the bottom row is the number in the box. We can also write the permutation in what is called cycle notation: (1 7 3 4)(2 5)(6 10 8 9). The first cycle (1 7 3 4) means that the number in box 1 is 7, the number in box 7 is 3, the number in box 3 is 4, and the number in box 4 is 1. The second cycle (2 5) means that box 2 contains the number 5 and box 5 contains the number 2, and the third cycle (6 10 8 9) means that box 6 contains the number 10, box 10 contains the number 8, box 8 contains the number 9, and box 9 contains the number 6. The two-line notation and the cycle notation are equivalent ways of writing the same permutation.
If the 10 prisoners get to choose 5 boxes each, and each prisoner starts with his own number, we see that prisoner 1 will open boxes 1, 7, 3, and 4 in that order. In box 4, he finds his own number, 1. Prisoner 2 only has to open boxes 2 and 5 before finding his number. Every prisoner in turn finds his own number, so they all go free. You can check this yourself by starting at any number on the top row of the permutation and checking to see how many steps it takes to get back to that number.
What if I had picked a different permutation for the boxes? Let's try this one:*
Written in cycle notation, this permutation is (1 3 5 6 2 9)(4 8 10)(7). Prisoner 1 opens boxes 1, 3, 5, 6, and 2, in that order. In box 2, he finds the number 9 instead of 1. Too latethat's his fifth choice. He's out of boxes. There's no mercy for the fact that his sixth choice contained his number in this game. In fact, no one whose number is in the first cycle finds his number. They are all one step away when they open the fifth box. The prisoners whose numbers are on the other cycles do find their numbers: prisoner 7 finds it immediately in his own box, and prisoners 4, 8, and 10 find them on their third tries. Alas, the group is doomed because prisoners 1, 2, 3, 5, 6, 2 and 9 all failed to find their numbers.
The key to the first permutation I picked was that there were no cycles in it of length greater than 5. The length of the cycle containing your number is exactly the same as the number of boxes you must open to find your own number using this strategy. If there is a cycle with, say, 6 numbers in it, anyone whose number is in that cycle will fail to find his own number, and the prisoners are guaranteed to lose. But if all the cycles of the permutation are shorter than 6 elements long, everyone will find his number.
The same principle scales up to our puzzle with 100 prisoners who get to open 50 boxes each. If the permutation defined by the random placing of names into boxes has a cycle longer than 50 numbers, the prisoners die because everyone whose number is on that cycle will fail to find his number in time.
To calculate the probability of success, we need to figure out what proportion of permutations of 100 elements have cycles of length greater than 50. The nice thing is that if a permutation has a cycle of length 51 or more, it can't have another; there are at most 49 elements left. Miraculously, it turns out that the probability of a random permutation having a cycle of length 51 is 1⁄51, a length of 52 is 1⁄52 and so on. If you'd like to see why, read on. If not, skip the next paragraph.
To find a cycle of length 51, we have 100 choices of first element, 99 choices for the second, 98 choices for third, and so on, until there are 50 choices for the 51st element. So there are 1009950 different ways we could write a 51-cycle. But some of these cycles are equivalent. To use a small, manageable example, the cycle (1 2 3 4) is equivalent to the cycle (2 3 4 1). They've just been written down in a different order, but both correspond to the permutation:
The cycles (3 4 1 2) and (4 1 2 3) are also equivalent. We can correct for this error by dividing by the length of the cycle; we could have written down the same cycle starting at any number, so that is how much we have over-counted. In our case, this means dividing by 51. So 51 elements of our permutation have been assigned. We have 49 elements remaining, and any permutation of them is acceptable. The number of permutations of 49 elements is 49484721, also known as 49! (factorial). Putting it all together, we have
permutations that have a cycle of length 51. Since there are 100! total permutations of 100 elements (this is the top number in the fraction), the fraction of permutations that have a cycle of length 51 is exactly 1⁄51. The same reasoning works for any cycle length over 50.
We now need to add up all the permutations that kill the prisoners, meaning all the permutations that have cycles of length over 50. In terms of probability, this is 1⁄51+1⁄52+1⁄99+1⁄100≈0.688. So the remaining proportion, 1-0.688, or 0.312, is the probability of finding a permutation that doesn't have a deadly cycle. This strategy leads to a whopping 31.2 percent success rate, gazillions (the technical term) of times better than the random strategy. Hurrah! Just don't think about the fact that they'll still probably all die.
This solution is interesting in its robustness. If you increase the number of prisoners (and keep the ratio of prisoners to guesses at 2:1), you might think that your chance of success would go down. It does, but barely. For any such situation, the success rate is about 1-ln2. (Remember, ln is the base e logarithm; ln(x)=y means that e^y=x.) This is the success rate if you increase the number of prisoners to 1,000 and the number of guesses to 500, or increase the number of prisoners to a billion and the guesses to 500 million. The reason is that the chance of failure is very close to the integral of the function 1⁄x from n to 2n, for large n. Because of the properties of logarithms, this is equal to ln2≈0.693, so the chance of success is about 1-ln2≈0.307, or 30.7 percent.
I find the winning strategy a little poetic. It's impossible for the prisoners to get close to winning, with only one or two people failing to find their numbers. If they don't all succeed, then everyone whose number is on the long chain fails to find his own number. That's more than half of them! The nature of the strategy means that you start opening boxes at the point of the chain that is furthest from your number. But there is no better strategy; starting with your own box is the only way to ensure that you are even looking on the right chain. It feels like a "united we stand" attitude.
Peter Winkler's talk described this and several other mind-bending puzzles, although there was not time for him to go into quite as much detail as I have here. The audience enjoyed trying to figure out the puzzles as they came up. The Museum of Math is co-sponsoring several more Math Encounters before their opening in December on a variety of different mathematical topics. Their next guest speaker is the mathematician and computer scientist Carlo Squin, who designs mathematically inspired works of art.
*Correction (7/19/12): These examples were improperly placed in the original posting. They are now in the correct position.