Squirrels digging holes

Question

A large colony of squirrels dug holes during the summer and in each hole, they put between 1 and 100 nuts (each quantity has the same probability).

If each squirrel has to eat 100 nuts during the winter, how many holes must he find (in average)?

Each hole contains 50.5 nuts in average, so 2 should be enough, right?

Hint:

Ybbx sbe n pbairetrag frevrf. (Decode with http://www.rot13.com/)

(I appreciate it because it looks so simple but it is damned hard. If you like it, do not forget the up arrow. I often find help in Python and I wish to have enough points so my thanks are not only recorded but displayed, too. I will not get points by helping others, FORTRAN and dBaseIII are not very fashionable anymore and my C strongly stinks FORTRAN.)

Answer 1

And the answer is:

$(\frac{101}{100})^{99} \approx 2.67803349448$

Why is that?

We procede by induction,
If we want 1 nut, we can dig only 1 hole. Let's say we need to dig $u_n$ hole on average to get $n$ nuts.
When we want $n+1$ nuts, we can decompose the probability as follow, depending on how many nuts we get in the first hole we dig: $u_{n+1}=1*\frac{101-(n+1)}{100}+\sum_{i=1}^n (1+u_i)*\frac{1}{100}$. The first term is if we dig more than enough, and the sum is for each case where we dug up $i$ nuts, which happens with probability $\frac{1}{100}$.
We can simplify this relation as $u_{n+1} = 1 + \sum_{i=1}^n u_i*\frac{1}{100}=u_n+u_n*\frac{1}{100}$ by splitting the last element of the sum and using the induction. Then we have a simple geometric sequence with ratio $\frac{101}{100}$ and starting term $1$, which gives $u_n=(\frac{101}{100})^{n-1}$.

Answer 2

Imagine that whenever you amass exactly $k$ nuts, you receive a stamp labeled $k$, for each $1\le k\le 99$. The time it takes to amass at least 100 nuts is equal to the number of stamps you collect, plus one. By linearity of expectation, the expected time to get 100 nuts is equal to $1+p_1+\dots+p_{99}$, where $p_n$ is the probability of collecting stamp number $n$.

To compute $p_n$, let's count the number of ways to "walk" from 0 to $n$ in $k$ steps. We can choose the $k-1$ intermediate numbers to walk across in $\binom{n-1}{k-1}$ ways. As long as we restrict our attention to $n\le 99$, each of these choices results in a valid walk (all steps are at most $100$). The probability of any walk with $k$ steps is $\frac{1}{100^k}$, so $$ p_n=\sum_{k=1}^n \binom{n-1}{k-1}\frac{1}{100^k} = \frac{1}{100}\left(1+\frac{1}{100}\right)^{n-1}, $$ using the binomial theorem. This means $p_1,\dots,p_n$ is a geometric progression, so its total can be easily computed easily. The final result is

$$1+p_1+\dots+p_{99} = 1 + \frac{1}{100}\left(\frac{(1+\frac1{100})^{99}-1}{(1+\frac1{100})-1}\right) = \left(\frac{101}{100}\right)^{99}$$