I got this problem from Rustan Leino, who got it from Clark Barrett, who got it from Robert Nieuwenhuis. I also heard it from Sean McCarthy.
I solved it and wrote up my solution.
100 prisoners agree on a strategy before playing the following game where they either all win or all lose. Find a strategy that lets them win with probability at least 1%. Don't bother trying to prove that your strategy is optimal.
A courtyard has a line of 100 boxes numbered 1–100. Each box contains a different prisoner's name, and the distribution of the 100 prisoners' names among the boxes has been chosen uniformly randomly among such distributions. One at a time (in some unspecified order), each of the prisoners is taken to the courtyard. The prisoner gets to look in up to 50 of the boxes and see the names in them. If, after looking in 50 boxes, the prisoner has not found their own name, the game is over and all the prisoners lose. But, if the prisoner does find the box containing their name among the 50 boxes they look into, then the prisoner is taken to the other side of the courtyard where they cannot communicate with the others. The boxes and courtyard are restored to their original state (in case the prisoner tried to manipulate them to communicate information), and the next prisoner is brought out into the courtyard. If all prisoners make it to the other side of the courtyard, they win.
The prisoners should assign themselves the numbers 1–100 and remember the assignment of numbers to names. Prisoner $i$ should start by opening box $i.$ Whenever a prisoner sees the name of another prisoner $j$, they should next look in box $j.$
The probability of this working is about 31.2%, for the following reason. One can uniquely partition the prisoner numbers into cycles, where each cycle $(p_0, p_1, p_2, \ldots, p_{n-1})$ has the property that each box $p_i$ has the name of prisoner $p_{(i+1) \bmod n}.$ The strategy will win if no cycle has length $> 50.$
Define $a_c$ to be the probability that there's at least one cycle of length $c$. No two cycles of length $> 50$ can co-exist since there are only 100 prisoners total. So, the probability that there's a cycle of length $> 50$ is $\sum_{c=51}^{100} a_c.$
Now let's calculate $a_c$ for $51 \leq c \leq 100.$ There are 100 ways to choose the first element of the cycle, then 99 ways to choose the second, etc., and then we have to divide by $c$ because cycles that are equivalent except for shifting are the same. So, there are $\frac{100!}{c(100-c)!}$ ways to choose the cycle. There are then $(100-c)!$ ways to permute the remaining elements that aren't in the cycle. So, there are a total of $\frac{100!}{c}$ ways to permute the prisoners so that there's a cycle of length $c.$ There are $100!$ total ways to permute the prisoners, so $a_c = 1/c.$
This means the probability of there being a cycle of length $> 50$ is $\sum_{c=51}^{100} 1/c,$ which equals about 68.8%. Thus, the probability of winning is 100% minus this, which is about 31.2%.