Hitting a Fixed Target with a Growing Die

Worked Solution

How to Think About It: Picture the situation: you are rolling a die with $n$ sides, and you want the cumulative sum to land exactly on a target $k$. The minimum roll is $1$ and the maximum is $n$. As $n$ grows, the expected value of a single roll is $(n+1)/2$, which diverges. So for large $n$, the very first roll almost certainly overshoots the fixed target $k$. Once you have overshot, the sum only increases, so you can never come back. The only way to ever hit $k$ is to get there through a sequence of small rolls, each at most $k$, and each of those small rolls has probability at most $1/n$ -- vanishingly small.

Quick Estimate: The probability of rolling any value $\leq k$ on a single roll is $k/n$. You need at least one such small roll just to have a chance. For $k = 6$ and large $n$, the probability of the first roll being $\leq 6$ is $6/n$, which is tiny. Even if the first roll is small, subsequent rolls face the same problem. So we expect $f(n, 6) \approx 1/n \to 0$.

More precisely, we can track the leading-order term. The dominant way to hit $k$ is to roll exactly $k$ on the first roll, which happens with probability $1/n$. Any multi-roll path to $k$ requires at least two small rolls, contributing terms of order $1/n^2$ or smaller. So $f(n,k) \sim 1/n$ for every fixed $k$.

Approach: Write a recursion for $f(n,k)$ by conditioning on the first roll, then take the limit.

Formal Solution:

Condition on the outcome of the first roll. If you roll $j$:

• If $j = k$: you have hit the target. This contributes probability $1/n$.
• If $j < k$: you now need the running total to hit $k - j$ starting from $j$. Since future rolls are independent and identically distributed, the probability of this is $f(n, k - j)$. Each such $j$ contributes $(1/n) \cdot f(n, k-j)$.
• If $j > k$: you have overshot $k$, and since rolls are positive, the sum only increases. You can never reach $k$ exactly. Contributes $0$.

This gives the recursion:

$$f(n, k) = \frac{1}{n}\left(1 + \sum_{j=1}^{k-1} f(n, k - j)\right).$$

Now take $n \to \infty$. For $k = 1$:

$$f(n, 1) = \frac{1}{n} \to 0.$$

For $k = 2$:

$$f(n, 2) = \frac{1}{n}\bigl(1 + f(n, 1)\bigr) = \frac{1}{n} + \frac{1}{n^2} \to 0.$$

By induction, suppose $f(n, j) \to 0$ for all $j < k$. Then

$$f(n, k) = \frac{1}{n}\left(1 + \sum_{j=1}^{k-1} f(n, k-j)\right) \to \frac{1}{n}\left(1 + 0\right) = \frac{1}{n} \to 0,$$

since the sum has a fixed number of terms ($k - 1$ terms), each tending to $0$.

Thus $\lim_{n \to \infty} f(n, k) = 0$ for every fixed $k \geq 1$.

The leading-order asymptotics are $f(n,k) = \frac{1}{n}(1 + o(1))$ for every fixed $k$, confirming that the dominant contribution comes from rolling exactly $k$ on the first throw.

Answer: $\displaystyle\lim_{n \to \infty} f(n, 6) = 0.$