Alternative solution for 100 prisoners problem I recently heard about the 100 prisoners problem ( https://en.wikipedia.org/wiki/100_prisoners_problem ) and have two questions about it.


*

*Let's assume a cycle with length $l$ > 50, then there are $\binom{100}{l}$ possibilities to choose numbers for such a cycle. After choosing $l$ numbers I would assume that there are $l\ !$ possibilities to arrange them in a cycle. We still have $(100-l)$ remaining numbers, which we can arrange by $(100-l)!$ possibilities. All together I get 
\begin{align}
\binom{100}{l}\cdot l\ !\cdot(100-l)!
\end{align}
possibilities for getting a cycle with $l\ >\ 0$. But I found out that the correct formula is
\begin{align}
\binom{100}{l}\cdot \color{red}{(l-1)\ !}\cdot(100-l)!
\end{align}
$\mathbf{Why}$ $\color{red}{(l-1)\ !}$ $\mathbf{?}$

*It has been shown that the optimal policy "wins" in about 30 %, independently of the number of prisoners. Furthermore it has been shown that this is an optimum, thus there is no better policy. But if we get cycles with $l>50$, this policy $\mathbf{always}$ fails. I wonder if there could be another policy which works as good as the already known policy, but whose success is $\mathbf{independent}$ of the length of the cycles.

 A: Ad 1.
$l$ numbers can be permutated in $l!$ ways, but some of these permutations represents the same cycle, eg. permutations $4,5,6,1,2,3$ and $2,3,4,5,6,1$ represents the same cycle $(1,2,3,4,5,6)$. There are exactly $l$ permutations in this equivalence class, so the number of cycles is equal to $\frac{l!}{l}=(l-1)!$
Ad 2.
This $31\%$ is probability where every prisoner draws his number, ie. in our permutation there is no cycle with length $l>50$. No matter of the length of cycles, if prosoners choose this strategy they have $31\%$ chance to win.
To show what I mean, assume that you have to guess the number drawn on 6 sided dice. Let's say, that your strategy is to say, that the drawn number is $5$. It gives you $16,6\%$ chances to win and $83,4\%$ chances to loose. Saying that your strategy fails when the drawn number is different than $5$ is the same as saying, that your strategy works perfectly when the drawn number is $5$. 
As far as you don't know what the number is, you have $16,6\%$ chances to win. 
As far, as the prosoners don't know if there is a cycle with length $l>50$, they have $31\%$ chance to win. 
A: 1.  You can always choose some person to "start" the cycle, and the remaining can be arranged in $(l-1)!$ ways. For example, there are only 1 way to organize 2 persons into a cycle.
2. There's a nice way to overcome this by randomizing the algorithm. Namely, the prisoners should choose a random permutation $\sigma$ beforehand and apply it. Namely, the prisoner $k$ should start from $\sigma(k)$ and then at each step she should open the box $\sigma(x)$, where $x$ is her number. 
This randomized strategy has the same probability of succeeding, no matter what the initial position is.
