The classical problem goes as follows:
There are 100 numbered prisoners and 100 ordered boxes containing their numbers (1 per box). Each prisoner goes into the room with boxes alone and must open and look into 50 of them one by one. After leaving, all boxes are closed. A prisoner cannot reorder or otherwise modify the boxes. Each prisoner does this separately from the others and they can't leave any clues behind. The prisoners are allowed to sync on strategies beforehand.
The original question asks about the best strategy if the goal is for ALL of them to find their own number. The answer is to follow the permutation chains, i.e. look into the box that's labeled with their own number and then look into the box with the number they saw inside it and repeat. This gives >30% success rate for arbitrary $$$N$$$ boxes ($$$N=100$$$ in the example) because if there is no permutation cycle of length larger than $$$N/2$$$, all prisoners will find their number, and the odds of that happening can be computed and are actually bounded by a constant regardless of the number of prisoners.
You can read more about the classical problem here
Recently I came up with the following variation: What if we have the exact same setup but we want NO prisoner to find their own number. They're still forced to open 50 different boxes by the same rules, but if any of them sees their own number they are all executed.
Using the exact same strategy of following permutation cycles, the prisoners will only succeed if the permutation consists of a single cycle of size $$$N$$$. This happens in $$$1/N$$$ of the cases.
I and indjev99 spent quite a long time trying, but we could neither find a better success rate than $$$1/N$$$, nor prove that this is optimal. I couldn't find this variant of the problem in literature either. The proof that the solution is optimal in the classical case is not really applicable for the variation. Any ideas?
The generalization of opening $$$K \geq N / 2$$$ boxes might be interesting to look at when trying to prove optimality for $$$K = N / 2$$$. For example, we tried thinking about the $$$K = N - 2$$$ case (as $$$K = N - 1$$$ is trivial).
Hmmm, I do seem to remember this variant from somewhere and the bound $$$\frac{1}{N}$$$ been frown around... I'll try and find it
lol, it was your post on r/math https://www.reddit.com/r/math/comments/zegqnq/strategy_for_100_prisoner_problem_if_you_want_no
Yes, I came up with it a while ago and tried in r/math first, but didn't get any useful ideas there. These kinds of problems seem to be more comfortable for computer scientists, so I have some hope in the CF community.
Does the question really make sense? Like even using the cycles, a person might find his own number even if the cycle has length N, by pure luck. So now we’re maybe talking about the strategy for which the most number of cases MIGHT work. Even then, the random strategy is a trivial 100% MIGHT work one.
In a cycle-following strategy if the permutation consists of a single cycle of length N, you are guaranteed that every player will examine their own box last.
In case you've misunderstood the strategy — in summary, prisoner X examines the boxes in order X, P[X], P[P[X]] ... Since the first box he examines is X, then the last box (before the cycle loops) must be the one containing the number X, i.e. the one he tries to avoid. Thus for single-cycle permutations they're all simultaneously guaranteed to succeed even if they had to open 99 (i.e. N-1) boxes.
We're thus talking of a strategy that has the highest chance of success if the permutation is random. The cycle-following achieves a success rate of $$$1/N$$$ because that's how many single-cycle permutations exist.