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 each chance you can either roll the die (using up one chance) or collect the currently showing number (without using a chance). Now your 100 chances are a budget for rolling only, and you want to maximize your total collected value. How does the optimal strategy change?
Hints
- Think about what you give up when you skip a roll. Does skipping ever give you an advantage if all die values are positive?
- Compute the expected payoff per roll if you only collect values above some threshold $t$. What value of $t$ maximizes the total?
- Write the Bellman equation: $V(k) = E[\max(X + V(k-1), V(k-1))]$. Since $X \geq 1 > 0$ always, the max is always achieved by collecting.
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 (rolling costs chances, collecting is free):
Now the problem becomes a genuine optimal stopping problem. You have a budget of $N = 100$ rolls. After each roll, you collect the value for free and then decide whether to spend another roll. The question is: should you keep rolling to try for another high value, or stop?
Let $W(k)$ be the expected additional value from having $k$ rolls remaining. You roll, see $X$, collect $X$ (it is always worth collecting a positive value), and then decide whether to roll again.
$$W(k) = E[X] + \max(W(k-1), 0) = 10.5 + W(k-1)$$
Since $W(k) > 0$ for all $k \geq 1$, you always want to use all your rolls. Each roll adds $E[X] = 10.5$ in expectation. So $W(N) = 10.5N = 1050$. Since all die values are positive and collecting is free, you should roll all 100 times and collect every result.
The problem becomes non-trivial only when the die includes zero or negative values, or when there is a cost per collection, or when you are choosing a single value to keep (classic optimal stopping). For the single-value variant with $k$ rolls of a d20:
$$V_1 = 10.5, \quad V_k = \frac{1}{20} \sum_{x=1}^{20} \max(x, V_{k-1})$$
With threshold $t_k = \lceil V_{k-1} \rceil$:
$$V_k = \frac{t_k - 1}{20} \cdot V_{k-1} + \frac{1}{20} \sum_{x=t_k}^{20} x$$
For large $k$, $V_k \to 20$ (you just keep rolling until you hit 20). With $k = 100$, $V_{100}$ is extremely close to 20, and the optimal threshold is $t = 20$ (accept only a 20, which you hit with probability $1 - (19/20)^{100} \approx 0.9941$).
Answer: The optimal strategy for the base game is to always collect every roll. The expected total is $\boxed{1050}$. The problem is trivial because all die values are positive, so skipping a positive value with no compensating benefit is never optimal. The problem becomes strategically interesting in variants where you choose a single value to keep (optimal stopping) or where collecting has a cost.
Intuition
This problem is a trap -- it sounds like a hard dynamic programming puzzle, but the answer is embarrassingly simple. The key insight is that skipping a roll costs you a chance without giving you anything in return. Since every outcome on a d20 is strictly positive, there is never a reason to skip. The only situation where a threshold strategy adds value is when some outcomes are undesirable (negative or zero), or when you are competing for a limited resource (like choosing a single value to keep from multiple rolls).
In real quant interviews, this problem tests whether you can recognize when a seemingly complex optimization has a trivial solution, rather than diving into unnecessary backward induction. The deeper lesson: always check whether the "do nothing" or "do the obvious thing" strategy is already optimal before building elaborate machinery. In trading, this maps to the principle that if every trade has positive expected value and no interaction effects, you should take all of them -- being selective only helps when there are costs, capacity constraints, or adverse selection.