The answer of @Acccumulation already mentions it, but I think it needs more emphasis: dependence is the key. Assuming the permutation of numbers is completely random, it does not matter which half of the drawers the first prisoner opens – as long as these are 50 different drawers (opening the same drawer twice is obviously suboptimal), the probability of finding his number is exactly $1/2$ whatever he does.
The key is in dependence of choices of the prisoners.
Suppose that $P(A_i)$ is the probability that the $i$'th prisoner found his number. As we have observed, $P(A_1) = 1/2$, but in fact $P(A_i) = 1/2$ for any $i$. However, because prisoners can make their choices based on the permutation hidden in the drawers, they are able to force $A_i$ and $A_j$ to be dependent and concentrate the failures on one particular set of permutations.
More precisely,
- consider the set of all possible permutations in drawers $\Omega = \{\pi_1, \pi_2, \ldots\}$,
- let's call a permutation $\pi$ successful for the $i$'th prisoner if his searching strategy succeeds in finding his number,
- define $\Omega_k$ as the set of permutations that are successful for all prisoners in range $\{1,\ldots, k\}$.
Basic probability gives us $P(A_1) = \frac{|\Omega_1|}{|\Omega|} = \frac{1}{2}$. Now, if the second prisoner were to make his choices randomly, then he would split $\Omega_1$ further in half, that is the size of $\Omega_2$ would be half of the size of $\Omega_1$ and a quarter of $\Omega$. On the other hand, by adjusting his strategy, i.e., taking into account the permutation he is observing, the second prisoner can try to concentrate his successes on the permutations in $\Omega_1$ and his failures on the permutations in $\Omega \setminus \Omega_1$. In this way $|\Omega_2|$ is strictly bigger than $|\Omega| / 4$, although smaller than $|\Omega_1|$. If all prisoners follow the suit, when one fails, a lot of other will fail too, but also when one succeeds, many other will succeed as well.
Finally to give you some intuition about why the particular drawers opened do not matter much (i.e., why it matters less than the dependence): suppose that we make the prisoners agree on an arbitrary permutation $\sigma$ and follow a strategy where the $i$'th prisoner starts with $\sigma(i)$ and when he finds $x$ in the drawer, follows up with $\sigma(x)$. This strategy does not change anything in the probabilities – because the permutation $\pi$ in the drawers is random, the probability of $\pi \circ \sigma$ having a cycle of length $\geq 51$ is also less than $70\%$. While no prisoner can beforehand commit to a set of drawers to open, the opened drawers are, due to $\sigma$, in a way, arbitrary.
Bonus puzzle:
There is yet another puzzle that uses a similar technique. There are 100 prisoners that wear hats, black or white (arbitrary assignment, there are no count constrains). They all see each other, but not the color of their hats. Each of them writes on a piece of paper (so that the others do not see) what color of hat they think they have. If all have guessed correctly, they are free. What is the best strategy for the prisoners to guess their hat colors?
I hope this helps $\ddot\smile$