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.
$(1/2)^{100}$for MathJax syntax) $\endgroup$