110
$\begingroup$

Names in Boxes

  • The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room.
  • One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
  • The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.

Find a strategy for them which has probability of success (all prisoners' survival) exceeding 30%.

Comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable $1 /2^{100} \approx 0.0000000000000000000000000000008 $. They could do worse—if they all look in the same 50 boxes, their chances drop to zero. 30% seems ridiculously out of reach—but yes, you heard the problem correctly.

This problem was sourced from the excellent, "Seven Puzzles You Think You Must Not Have Heard Correctly," (Note - link includes solutions!) Compiled by Peter Winkler

This is the hardest brainteaser that I've ever actually been able to solve. (Eventually, anyway - I spent my spare time for a couple of weeks on it, and at the time, even though I found the solution, I lacked the math skills to calculate the precise odds of the optimal solution working.) Can you explain the solution without too much mathematical background (less than what the linked solution assumes)?

$\endgroup$
  • 2
    $\begingroup$ There's a typo in the problem description: 1/2100 -> should be $(1/2)^{100}$ ($(1/2)^{100}$ for MathJax syntax) $\endgroup$ – Andrew T. Oct 1 '14 at 4:22
  • 5
    $\begingroup$ Wait, what happens after each prisoner had seen at most 50 boxes and has left the room? $\endgroup$ – user170141 Oct 5 '14 at 9:38
  • 4
    $\begingroup$ youtube.com/watch?v=eivGlBKlK6M :) $\endgroup$ – Sawarnik Dec 16 '14 at 6:50
  • 13
    $\begingroup$ Isn't something missing in this question? People come, look into boxes, go out again... And what? What is their goal? Otherwise strategy seems a bit unreasonable... I think that's what user170151 meant also. $\endgroup$ – BmyGuest Jan 11 '15 at 7:22
  • 5
    $\begingroup$ err...did you forget to accept any one of the answers? :p $\endgroup$ – manshu May 24 '16 at 9:44
71
$\begingroup$

I've tried to explain the solution using as little math as possible, and to give some intuition as to what makes it tick. Nonetheless there will be a little mathematical notation at the end.

First steps: going beyond the obvious solution in the simplest case (N=2)

The statement of the puzzle as presented here doesn't make this very clear, but the puzzle relies on the prisoners not knowing anything about which name is located in which box (until they get into the room, after which they cannot communicate anymore). If every prisoner checks 50 boxes at random, then each prisoner has a ½ chance of finding his own name. If all the prisoners choose a set of boxes at random, independently, then the probability that they all find their own name is ½ × … × ½ = 1/2100 — infinitesimal.

Making independent choices is a waste, though. If anyone gets it wrong, the situation isn't worse than if everybody gets it wrong. Rather than make independent choices, they can make correlated choices; the idea is to try to arrange that either everybody gets it right, or many get it wrong.

Let's consider the simpler case when there are two prisoners. If they both choose at random, then they have ½ × ½ = ¼ chance of surviving. But there's an obvious waste: suppose prisoner #1 opens the left-hand box and finds his name: then prisoner #2 will not find his name in the left-hand box. So the prisoners can decide that #1 will look at the box on the left and #2 looks at the box on the right: that way, either they both get it right or both get it wrong, and they have a ½ chance of survival.

Incidentally, note that another assumption that wasn't clearly stated here is that the prisoners get to formulate their strategy in secret. If the warden knows which prisoner chose which box, he can arrange for the prisoners to fail by putting prisoner #1's name in the right-hand box.

The next step: N=4

The obvious way to generalize this to more prisoners is to assign each prisoner a fixed set of boxes that he'll open. However, I won't pursue this further, because it doesn't take advantage of an important ability: after a prisoner has opened a first box, he can base his decision on which box to open next on the content of the first box, and so on.

Consider the case with 4 prisoners and 4 boxes. I'll use numbers for the prisoners' names, and assume that the boxes are numbered as well. Intuitively, it is preferable for each prisoner to pick a different box to open first, since otherwise some common choices are wasted. So prisoner #1 opens box #1 and finds a name (number). Now what? If he finds his own name (#1) (¼ chance), of course, he can stop. If he finds some different name (say 2) (¾ chance), what information does this provide? Well, since each box contains a different name, prisoner #1 now knows that box #2 does not contain 2, so prisoner #2 will not be lucky the first time either. Furthermore, the strategy should favor arranging for prisoner #2 to pick box #1 next.

To simplify the analysis, I'll only look at cases where all prisoners follow the same strategy. (I don't have an intuitive argument as to why breaking the symmetry wouldn't be advantageous.) Either they all open the box whose number they found in the first box, or they all open a different box.

  • If #1 opens box #2 and finds his name there, then either boxes #3 and #4 contain 3 and 4 respectively, or they contain 4 and 3. Either way, with the strategy of using the name in the first box, if one prisoner is lucky the second time then every prisoner is lucky!
  • If #1 opens box #3 instead and finds his name there, then there is a ½ chance that prisoner #2 will find his name in box #2, and a ½ chance that he'll find his name in box #4. But what about prisoner #3? He finds the name of prisoner #1 in box #3, which doesn't give any clue as to where 3 might be instead.

So let's concentrate on the strategy where each prisoner opens the second box whose number is what he found in the first box. What arrangement of numbers in boxes make it work?

There are 4 ways to choose which box contains the number 1. The number 2 can go into any of the 3 remaining boxes. The number 3 can go in either of the 2 remaining boxes, and the number 4 must go into the one remaining box. So there are 4×3×2 = 24 different arrangements. The following arrangements lead to success because each number is either in its own box or swapped with another number:
1234 1243 1324 1432 2134 2143 3214 3412 4231 4321

That's 10 successful arrangements out of 24. The chance of success isn't very far from the theoretical maximum of ½, which is encouraging.

Note that in order for the chance of success to be 10/24, we need to know that the arrangements have an equal chance of being chosen. If the warden is nasty and arranges the numbers as 2341, the prisoners are sure to lose. This is where the fact that the prisoners choose a strategy in secret comes in. In my analysis, I used numbers for prisoners — but fact the prisoners are names, not numbers, and they can pick a random assignment of names to numbers as part of their secret strategy (in fact, this assignment is the only secret part, since the warden may have looked up the solution of the puzzle).

General analysis

Let's explore a strategy that generalizes what we explored for 4 boxes: each prisoner opens the box with his own number, then the box whose number is contained in the first box, and so on. Consider the sequence of numbers that a certain prisoner encounters: $x_0$ (the inital box numbered with the prisoner's own number), $x_1$ (number contained in box $x_0$), $x_2$ (number contained in box $x_1$), … Since each number is contained in only one box, this sequence cannot contain any repeated element as long as it doesn't loop back to $x_0$. Eventually the sequence has to loop back to $x_0$ since it will run out of numbers. At that point, the prisoner has found his own name. The critical problem for the prisoner is whether the loop completes before or after the prisoner has opened the maximum of 50 boxes.

From now on, let me use the proper mathematical vocabulary. A way to arrange distinct numbers into as many boxes is called a permutation. Opening box number $k$ and looking at the number that it contains is called applying that permutation. Repeated applications of a permutation eventually runs into a loop; such a loop is called a cycle. The prisoners succeed if all of the cycles for the permutation have a length of at most 50.

Let's call a cycle long if it contains 51 or more elements. Observe that there cannot be more than one long cycle (if one cycle has at least 51 elements, then there are only 49 or fewer elements to share between the other cycles). So we can count the losing configurations by adding up the permutations of 100 elements that have a cycle of length 51, 52, …, 100.

Lemma: there are $n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (n-1) \cdot n$ distinct permutations of $n$ elements. Proof: there are $n$ ways to pick the image of the first element, $n-1$ remaining ways to pick the image of the second elements, etc., down to a single way to pick the image of the last element.

Now let's count the number of permutations that have a cycle of length $c$ (for $c \ge 51$, so that there's a single such cycle). We're actually going to count each permutation $c$ times, once for each element of the cycle. Pick the first element in the cycle: there are 100 possibilities. There are 99 possibilities for the second element, and so on, until we've picked $c$ elements. So far, that's $100 \times 99 \times \ldots \times (100-c+1)$ possibilities. There are $100-c$ remaining elements, and they can be permuted in any way, so there are $(100-c)!$ possibilities as per the lemma above. That's a total of $(100 \times 99 \times \ldots \times (100-c+1)) \times ((100-c) \times \ldots \times 2 \times 1)$ possibilities, which nicely collapses to $100!$. Recall that we counted each permutation $c$ times, since we counted it once per element in the cycle. So the number of permutations with a cycle of length $c$ is $100! / c$.

The number of permutations with a long cycle is thus $$ \frac{100!}{100} + \frac{100!}{99} + \ldots + \frac{100!}{51} $$ That's out of a total of $100!$ permutation. The proportion of failing permutations is thus $$ \frac{1}{100} + \frac{1}{99} + \ldots + \frac{1}{51} $$ Numerically, this is about 0.6882, i.e. the chance of success is about 31.18%, a little over the requisite 30%.

In general, the proportion of failing permutations for $N$ prisoners is $H_N - H_{N/2}$ where $$ H_n = 1 + \frac{1}{2} + \ldots + \frac{1}{n} $$ is called the $n$th harmonic number. For large values of $n$, $H_n \approx \ln n + C$ for some number C, and the series $H_N - H_{N/2}$ converges to $\ln 2 \approx 0.6931$ from below. (I will not provide an elementary proof of that). This gives a lower limit to the chance of success for large numbers of prisoners: 30.68% is achievable.

$\endgroup$
  • 1
    $\begingroup$ I'll just take a stab at the elementary proof (I need the practice): $$\begin{align}H_n - H_{n/2} &= \big(\!\ln(n) + C\big) - \big(\!\ln(n/2) + C\big) \\ &= \ln(n) + C - \big(\!\ln(n) - \ln(2) + C\big) \\ &= \ln(n) - \ln(n) + \ln(2) + C - C \\ &= \ln(2)\end{align}$$ $\endgroup$ – michaelb958 Jun 13 '14 at 0:17
  • 2
    $\begingroup$ @michaelb958 The first equality is wrong. $H_n \approx \ln n + C$, or more precisely, $H_n \sim \ln n + C$, meaning that $\lim H_n/(\ln n + C) = 1$. It's not too hard to make that proof work (ask for help on Mathematics if you need to). But I was mostly refering to providing an elementary proof of $H_n \sim \ln n + C$. $\endgroup$ – Gilles Jun 13 '14 at 0:25
  • 7
    $\begingroup$ I knew I'd do something silly like that... $\endgroup$ – michaelb958 Jun 13 '14 at 0:28
66
+50
$\begingroup$

The solution I read when I heard about this problem (which is most likely the same one in your solution booklet) goes like this:


Before they begin, give each prisoner a fixed number from 1 to 100, and correlate this with their name.

Then, when it is a prisoner's turn to open the boxes, he will start with the box of his own number. If the box does not contain his name in it, he will recall the number of the prisoner whose name is in the box, and open that number's box. He then continues this cycle of recalling a number and opening that box until either he finds the box with his own name in it, or 50 boxes are opened.

This strategy essentially maps one prisoner to another unique prisoner, or a number from 1 to 100 to another unique number from 1 to 100.

This is known as a permutation, and one of the things that can be shown about permutations is that they all consist of cycles. This is because no two prisoners can have the same prisoner's name in "their" boxes, so eventually each prisoner would come across their name by following the procedure above.

Now, obviously, if there are no cycles of length 51 or longer, then the prisoners will go free. And if there is a cycle of length 51 or longer, then the prisoners will all die.

Then, we just need to find the probability that there is a cycle of 51 or longer.

To do this, note first that there can only be one cycle of length 51 or more in a permutation of 100 elements - if there were more than one, there'd have to be at least 102 elements, which is impossible!

Now, for a cycle of length exactly $n$, we select the elements that are going to be in the cycle, and the rest can be permuted whatever way they want. This results in $\binom {100} {n}$ possible sets of $n$ to be chosen, times $\frac {n!}{n}$ ways to permute the cycle in that set (because the cycle has $n$ states itself), times $(100-n)!$ ways to permute the rest of the elements. Conveniently, this equals exactly $\frac{100!}{n}$, so the probability that there is a cycle of length exactly $n$ is just $\frac 1n$.

Then, the probability that there is a cycle of length 51 or longer is just $$1/51 + 1/52 + 1/53 + ... + 1/100 \approx 0.688172$$, so the probability of the opposite is $0.311828$ which is above 30%.

$\endgroup$
  • 4
    $\begingroup$ Great explanation $\endgroup$ – Mikey Mouse Aug 15 '14 at 10:36
  • 2
    $\begingroup$ This is correct! Monte Carlo estimation of the probability: repl.it/CVBV/1 $\endgroup$ – Brian Risk May 25 '16 at 15:11
9
$\begingroup$

Chance for all prisoners surviving: 50%

Just use time as an indication.

Before the exercise, all prisoners agree that they will each learn the name of the person going in after them. The first prisoner will search the first 50 boxes for his name and for the name of the second person. He has a 50% chance of finding his own name. If he doesn't find it in the first 50 boxes, everyone dies.

If the first person also finds the name of the person coming after him in the first 50 boxes, he leaves immediately within a pre-agreed time (say, 5 minutes). If he doesn't, then the next person is in the last 50 boxes, and he waits at least 5 minutes before leaving.

The second person knows whether his name is in the first 50 boxes or the last 50 boxes, based off of whether he had to wait 5 minutes or not. He finds his name, and finds whether the third person is in the first 50 boxes or the last 50 boxes, and waits the 5 minutes if the third person is in the last 50 boxes.

And just repeat...

50% chance the first person finds his own name, and then 100% chance that each subsequent person finds his own name.

$\endgroup$
  • 4
    $\begingroup$ This doesn't work: the prisoners don't know how much time the warden waits before calling the next prisoner. He might be calling one per day, for instance. $\endgroup$ – Gilles Jan 11 '15 at 13:17
  • 1
    $\begingroup$ @Gilles That's not stated/clear from the puzzle wording given. $\endgroup$ – pkr298 Jan 11 '15 at 13:44
  • 8
    $\begingroup$ Exactly: it's not stated, so you aren't allowed to implicitly assume an ad hoc hypothesis tuned for your solution. $\endgroup$ – Gilles Jan 11 '15 at 13:45
  • 5
    $\begingroup$ +1 I love the lateral-thinking approach to conveying information. This is not the "correct" solution (for reasons given in the comments), but I like the spirit of this one. $\endgroup$ – Brian Risk Aug 5 '16 at 15:49
  • 2
    $\begingroup$ I disagree with Gilles; I believe this answer is perfectly acceptable. The question stated that the prisoners are to go into the room "one by one", which to me means that after one finishes, the next one goes. With similar logic, another method would be to "pace quickly" as you leave the room if you find the next prisoner's name, or slowly if you don't. This method is more plausible as well, as I can't imagine a group of 100 prisoner's that are able to memorize numbers corresponding to each of the other 99 people plus themselves without making a mistake, which factors into the success rate. $\endgroup$ – Joe Majewski Dec 15 '17 at 18:57
5
$\begingroup$

This is just of an observation about the solution and the formulation of the problem, but was too long to be put as a comment:

It's a remarkable riddle, but the one thing I don't like about the problem is the >30% target, it's slightly more cumbersome but with an additional rule, you can ask for a 100% success rate:

The first prisoner is allowed to restart the experiment (as many times as he wants) at the end of his turn, the boxes will be reshuffled before he reenters the room (he will not be able to communicate with other prisoners while the room is reset)

To win, just use this variation of the same strategy:

  • if the first prisoner don't find his name, he asks a reset obviously
  • if he finds his name by opening less than 50 boxes, he asks a reset (because that gives a chance of a >50 length cycle)
  • if he finds his name by opening exactly 50 boxes, he know for sure everyone will find his own name in max 50 tries (if one cycle is of length 50, no other cycle can be > 50)
$\endgroup$
0
$\begingroup$

I argue that 50% of the prisoners can be saved: regardless of any ordering of the prisoners names in boxes, in any given string of 50 boxes (a string need not be consecutive) there are exactly 50 names which correspond to exactly 50 of the 100 prisoners. So, as long as all 100 prisoners choose to select the same 50 boxes to examine, at least 50 of them will find there name. This corresponds to a 50% success rate.

$\endgroup$
  • 7
    $\begingroup$ Every single prisoner has to find their name otherwise the entire group of prisoners will be executed. $\endgroup$ – Ben Aaronson Oct 5 '14 at 12:35
  • $\begingroup$ That is not the way OP worded the riddle. $\endgroup$ – user170141 Oct 5 '14 at 18:30
  • 2
    $\begingroup$ "because unless every single prisoner finds his own name all will subsequently be executed" $\endgroup$ – Ben Aaronson Oct 5 '14 at 18:30
  • 1
    $\begingroup$ I agree it could have been better worded though, it's weird to hide the objective half way though a completely different sentence like that after all the other information has been given $\endgroup$ – Ben Aaronson Oct 5 '14 at 18:31
  • 6
    $\begingroup$ Because every prisoner has to find their own name. If they all pick the same 50 boxes, that's impossible. So the probability of them all finding their name in your strategy is 0%. It needs to be better than 30% $\endgroup$ – Ben Aaronson Oct 5 '14 at 22:01
0
$\begingroup$

I personally think that there is atmost 50% chance of the prisoners being saved When the first prisoner goes to find his name he has 1/2 probability of finding his name. Now if he has found his name ,he will know the other 49 names and their respective positions. He will tell these to those 49 prisoners. And they now would have full chance of finding their name.In the process they would decipher other names of prisoners and their positions which they could tell to their fellows. Note that there is no chance of a prisoner opening the same 50 boxes which the first prisoner opened as thay have agreed upon a strategy to remember names and positions . Therfore after the first prisoner everyone would have a full chance of finding their name as they would bring extra information along with them. By multiplication theorem: 1/2×1×1×1...100 times which corresponds to a probability of 50% chance of the prisoners being saved

$\endgroup$
  • 3
    $\begingroup$ The first prisoner is not allowed to "tell these to those 49 prisoners"; no communication between the prisoners is allowed after the first one enters the room. $\endgroup$ – Gareth McCaughan Feb 14 '18 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.