# An asymmetric die game

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?

-
It looks like it should be $S=\{p_i|p_i \ge w\}$ based on your example. Also, there is a section missing from the first sentence in that paragraph. – Ross Millikan Jun 27 '13 at 13:10
I'm assuming the prisoner wins if he gets a value greater than or equal to the wardens? This seems suggested by your 2nd example. – Calvin Lin Jun 27 '13 at 15:27
@CalvinLin Yes, that's where the correction Ross mentioned came in. – Foo Barrigno Jun 27 '13 at 15:29
Ah, the first line of the 4th paragraph still says "greeter than", hence I was confused. – Calvin Lin Jun 27 '13 at 15:31

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.