Suppose you have a game where you roll an $m$-sided dice until the sum of your rolls equals or exceeds a number $n$. If this sum equals $n$, you win, and if the sum exceeds $n$, you lose. What number $n$ should you pick to maximize the chance of winning?
Suppose that the sum of our rolls is $X$. If $X$ is more than $m$ away from $n$, obviously we just roll until that is no longer the case, so assume that $X$ is in the state $n-k$ where $k<m$. There is a $\frac{m-k}{m}$ chance of losing. There is a $\frac{1}{m}$ chance of winning. There is a $\frac{k-1}{m}$ chance of moving to the state $n-k+r$, where $r$ is the number that you rolled.
Put another way, we have this recursive equation
$$P(\text{eventual win}|n-k)=\frac{1}{m}(1+\sum_{r=1}^{k-1}P(\text{eventual win}|n-k+r))$$
and what we need is to calculate $P(\text{eventual win}|0)$, and maximize it in terms of $n$.
I've expressed this in terms of states and probabilities but I'm not sure how to get a solution out of that. It looks like a lot of other similar problems in stochastic dice games where the answer turns out to be in terms of Harmonic numbers.
Best Answer
The answer has to be $m$.
To see this, let $P_k$ be the probability of winning if your current sum is $k$ less than the target sum. Then
$$P_m= \frac 1m (1 + \sum_{k=1}^{m-1} P_k), \text{ whereas } n \lt m \Rightarrow P_n = \frac 1m (1 + \sum_{k=1}^{n-1}P_k).$$
Since each $P_k \gt 0$, it must be the case that $P_m \gt P_n$.
If your target is greater than $m$, then you have some weighted average of the $P_k ~(1 \leq k \leq m)$ where the coefficient assigned to $P_m$ is less than $1$.