# Squirrels digging holes

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.)

• Welcome to Puzzling.SE! For hinting on your puzzle, use "spoilers." This is done by adding >! to the beginning of the line you wish to hide. See here for more markdown help – Chowzen Mar 28 '18 at 13:00
• In the future, wait a bit to post a hint because a lot of times people like to try and think it through first :) – Sensoray Mar 28 '18 at 13:02
• @Chowsen - did not read markdown help carefully enough, looked for color. Anyway, I do not mind, rot13 is not wide used anymore and I believe someone might be glad to discover it this way. – kaksi Mar 28 '18 at 13:12
• @Oray I agree it requires statistics. Before posting, I browsed the forum, there are puzzles of this kind. – kaksi Mar 28 '18 at 13:14
• @puzzledPig If you get to a certain value on one site, you gain the association bonus of 100 extra rep because you're trusted not to be a spammer / bad user. – wizzwizz4 Mar 28 '18 at 16:44

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}$.

• I did not expect the solution so quickly. Note that if the number of nuts -> inf, the number of holes -> e. – kaksi Mar 28 '18 at 13:21

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}$$