Suppose there is a prisoner who is being held by a gambling-addicted warden. The warden offers a compromise to the prisoner - if the prisoner can win a certain game of chance, the warden will let them go free, however if the prisoner loses the game, the prisoner will be required to serve the rest of their term without parole.
$n$ is fixed.
The prisoner will choose how many $n$-sided dice to roll. The prisoner can roll as many as they wish. The warden will roll a single $n$-sided die.
The prisoner's goal is to get at least one die with a value greater than or equal to the warden's in order to win. However, if the prisoner gets a number of dice with a value greater than or equal to the warden's, the prisoner loses. i.e. The warden's roll is $w$, and the prisoner's rolls are $p_1,p_2,...,p_n$ the prisoner wins if $1\le|S|<w$ where $S=\{p_i|p_i\ge{w}\}$
For example, suppose the warden doesn't play role-playing games, and just has 6-sided dice laying about. The prisoner, not necessarily being the logical sort, decides to roll 5 dice. The warden rolls a 3. The prisoner rolls $\{5,1,2,6,6\}$. The prisoner loses, because three of the dice were greater than the warden's. If instead he had rolled $\{3,1,2,1,3\}$ he could have won.
The problem is, given $n$, what is the optimal number of dice for the prisoner to roll, and what is the probability that he walks?
Hint: Let's say, we have an $n$-sided dice and the prisoner choose to roll $l$ times. Now , if the warden rolls a $m$, the probability of $|S|$ being $k$ is $$b(n,l,m,k):=\binom{l}{k}\left(\frac{n-m+1}{n}\right)^k\left(\frac{m-1}{n}\right)^{l-k}$$ The probabilitiy of $|S|$ being inbetween $1$ and $m-1$ is $$w(n,l,m):=\sum\limits_{k=1}^{m-1}b(n,l,m,k)$$ Hence, the probability of winning in general is: $$W(n,l):=\frac{1}{n}\sum\limits_{m=1}^{n}w(n,l,m)$$ So, for given $n$, you need to choose $l$, such that $$\frac{1}{n}\sum\limits_{m=1}^{n}\sum\limits_{k=1}^{m-1}\binom{l}{k}\left(\frac{n-m+1}{n}\right)^k\left(\frac{m-1}{n}\right)^{l-k}$$ is maximized. I'm not doing this.