Optimal Strategy for Rolling a 20-Sided Die with 100 Chances
You are playing a game with a fair 20-sided die (faces labeled $1$ through $20$) and you have $100$ chances. Each chance, you roll the die and see the result. You can either collect the number (adding it to your running total) or skip it. Either way, one chance is used. Your goal is to maximize the expected total collected value over all $100$ chances.
What is the optimal strategy, and what is the expected total under that strategy?
As a follow-up: suppose instead that you may roll up to $100$ times but you keep only one number -- the value showing when you choose to stop (and if you never stop, you are left with whatever the $100$th roll shows). What is the optimal stopping rule, and what is the expected value you collect?
Hints
- Think about what you give up when you skip a roll in the base game. Does skipping ever gain you anything if every die value is positive?
- Compute the expected payoff per chance if you only collect values above a threshold $t$. Which $t$ maximizes the total?
- Write the Bellman equation for the base game: $V(k) = E[\max(X + V(k-1),\ V(k-1))]$. Since $X \geq 1 > 0$ always, the max is always achieved by collecting.
- For the follow-up, note that accepting now forfeits every remaining roll. Set $V_k = \frac{1}{20}\sum_{x=1}^{20}\max(x, V_{k-1})$ with $V_1 = 10.5$ and read the threshold off as "accept $x \ge V_{k-1}$".
Worked Solution
How to Think About It: Before doing any math, think about what skipping a roll actually costs you. If you skip a roll showing value $v$, you give up $v$ points and you still burn one of your 100 chances. You get nothing in return; the next roll is a fresh independent draw regardless. So skipping a positive value is literally lighting money on fire. Your gut should say: always collect. And your gut is right.
The follow-up version is where it gets interesting. If rolling costs a chance but collecting is free, then you have a budget of 100 rolls to generate values, and you collect as many as you want. Now there is a real trade-off: should you spend rolls being picky?
Quick Estimate: In the base game, always collecting gives:
$$E[\text{total}] = 100 \times E[X] = 100 \times \frac{1 + 20}{2} = 100 \times 10.5 = 1050$$
Can you beat this? Suppose you skip values below some threshold $t$ and only collect values $\geq t$. When you collect, the expected value is $(t + 20)/2$, but you only collect with probability $(21 - t)/20$ per chance. Your expected total is:
$$100 \times \frac{21 - t}{20} \times \frac{t + 20}{2} = 100 \times \frac{(21 - t)(t + 20)}{40}$$
Maximize $(21 - t)(t + 20) = -t^2 + t + 420$. Taking the derivative: $-2t + 1 = 0$, so $t^{*} = 0.5$, meaning the nearest integer is $t = 1$, meaning collect everything. Plugging in: $(20)(21)/40 = 10.5$, confirming expected total $= 1050$. Any threshold $t \geq 2$ gives a strictly lower expected total.
Approach: We verify by backward induction that the greedy (always-collect) policy is optimal, then solve the more interesting follow-up.
Formal Solution:
Let $V(k)$ be the expected total under optimal play with $k$ chances remaining. We have $V(0) = 0$. At each chance, you roll and see value $X \sim \text{Uniform}\{1, \ldots, 20\}$. If you collect, you get $X + V(k-1)$. If you skip, you get $0 + V(k-1)$. You collect whenever $X > 0$, which is always. So:
$$V(k) = E[X] + V(k-1) = 10.5 + V(k-1)$$
$$V(k) = 10.5k$$
$$V(100) = 1050$$
The optimal strategy is trivially to always collect.
Follow-up -- keeping a single value:
This version *is* a genuine optimal stopping problem, and the reason is worth naming: collecting now ends the game. In the base game collecting was free, so selectivity bought you nothing; here every acceptance forfeits all remaining rolls, which is exactly the cost that makes a threshold worth computing.
Let $V_k$ be the expected value collected with $k$ rolls remaining under optimal play. With one roll left you must take what appears, so $V_1 = E[X] = 10.5$. With $k$ rolls left you roll, see $x$, and keep it precisely when it beats the value of continuing:
$$V_k = \frac{1}{20}\sum_{x=1}^{20} \max\!\left(x,\ V_{k-1}\right).$$
So the optimal policy is a threshold rule: with $k$ rolls remaining, accept $x$ if and only if $x \ge V_{k-1}$. Iterating the recursion in exact arithmetic gives thresholds that climb and then saturate:
| Rolls remaining $k$ | $2$ | $3$ | $4$ | $5$-$6$ | $7$-$8$ | $9$-$12$ | $13$-$22$ | $23$-$100$ | |---|---|---|---|---|---|---|---|---| | Accept $x \ge$ | $11$ | $13$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ |
with values $V_2 = 13$, $V_3 = 14.4$, $V_5 \approx 16.00$, $V_{10} \approx 17.71$, $V_{20} \approx 18.88$, $V_{50} \approx 19.76$, and
$$V_{100} \approx 19.9817.$$
With a budget this large the rule is simply *hold out for a $20$* until fewer than $23$ rolls remain, then start settling. You see at least one $20$ with probability $1 - (19/20)^{100} \approx 0.9941$, and the small gap between $V_{100}$ and $20$ is the price of the rare runs where you never do.
The contrast between the two versions is the real content of the problem. Identical die, identical budget: when collecting is free, being picky is pure loss and the answer is "take everything"; when collecting ends the game, being picky is worth almost $9.5$ points per play. What changed was not the randomness but the *opportunity cost of accepting*.
Answer: In the base game the optimal strategy is to always collect every roll, giving expected total $\boxed{1050}$ -- skipping a positive value burns a chance and returns nothing in exchange. In the follow-up, where you keep only the single value you stop on, the optimal policy is the threshold rule "with $k$ rolls left, accept $x$ iff $x \ge V_{k-1}$"; with $100$ rolls that means holding out for a $20$ until the final $22$ rolls, and the expected value collected is $V_{100} \approx 19.98$.
Intuition
This problem is a trap -- it sounds like a hard dynamic programming puzzle, but the base game's answer is embarrassingly simple. Skipping a roll costs you a chance and gives you nothing back, and since every outcome on a d20 is strictly positive, there is never a reason to skip. In real quant interviews this tests whether you can recognize when a seemingly complex optimization has a trivial solution, rather than diving into unnecessary backward induction.
The follow-up earns its keep by isolating exactly what was missing. A threshold strategy pays only when accepting has an opportunity cost -- when taking this value forecloses something else. Free collection has no such cost, so the threshold collapses to "accept everything"; single-value collection makes acceptance terminal, and the optimal threshold jumps to $20$ whenever more than $22$ rolls remain. Same die, same budget, answers of $10.5$ and $19.98$ per play.
In trading this maps directly to capacity. If every positive-edge trade can be taken independently, take them all -- selectivity destroys value. The moment a trade consumes something scarce (risk limit, capital, the one slot in a portfolio, a counterparty's patience), a hurdle rate appears, and the right hurdle is precisely the expected value of what you could otherwise do with that slot. Most bad selectivity in practice comes from applying a hurdle where there is no scarcity; most bad greed comes from ignoring one where there is.