Bank vaults and probability

Solution 1:

Let $E(n)$ be the expected number of vaults needed to obtain at least $n$ coins. By conditioning on the number $k$ of coins in the next vault, we have $$E(n)= \begin{cases} 0 &\text{if $n\le 0$}\\ 1+\displaystyle{\frac{1}{100}\sum_{k=1}^{100} E(n-k)} &\text{if $n > 0$} \end{cases} $$

To make this derivation explicit for $n>0$, let random variable $V_n$ be the number of vaults needed to obtain at least $n$ coins, and let (discrete uniform) random variable $C$ be the number of coins in a vault. By the law of total expectation, conditioning on $C$ yields \begin{align} \mathbb{E}(V_n)&=\sum_{k=1}^{100}\mathbb{E}(V_n|C=k)\mathbb{P}(C=k)\\ &=\sum_{k=1}^{100}(1+\mathbb{E}(V_{n-k}))\frac{1}{100}\\ &=1+\frac{1}{100}\sum_{k=1}^{100}\mathbb{E}(V_{n-k}) \end{align}

We want to compute $E(100)$, which turns out to be approximately 2.678. You can verify that $E(n)=1.01^{n-1}$ satisfies the recursion if $n>0$, so the exact value is $E(100)=1.01^{99}$.

Solution 2:

It doesn't matter how many vaults there are - you open the first one you come to and it will have an amount of coins in which can be any number between 1 and 100 with equal probability.

You pocket all those coins and move onto the next vault. This vault also has between 1 and 100 coins in, again with equal probability for each number.

You add together these coins and the ones already in your pocket. If this number is greater than or equal to 100 then you stop and leave with your 100 coins. If you have less than 100 coins, then you pocket all the coins and move on to the next vault, repeating the process until you have the desired 100 coins

Solution 3:

Very nice problem! You can safely assume that there are exactly $100$ vaults since this is the maximal number of vaults the burglar may have to open. (See below for an argument.)

My take on the interpretation is as follows: Number the vaults $V_1, V_2, \ldots, V_{100}$ and say that the burglar opens $V_1$ first, then $V_2$ if necessary, and then $V_3$ and so on. Suppose that the number of coins in vault $V_i$ is $C_i$. There are $N = 100^{100}$ different possible configurations of coins in the vaults, all of which are equally likely if we assume that the contents of different vaults are independent. That is, for any $(n_1, \ldots, n_{100}) \in S:= \lbrace 1, \ldots, 100 \rbrace^{100}$, \begin{align*} P\left( C_1 = n_1, \ldots, C_{100} = n_{100} \right) = \frac{1}{N}. \end{align*} For $\textbf{n} = (n_1, \ldots, n_{100}) \in S$, corresponding to specific configuration of coins, let

\begin{align*} b(\textbf{n}) = \min \left\lbrace 1 \leqslant x \leqslant 100 \mid n_1 + \cdots + n_x \geqslant 100 \right\rbrace. \end{align*}

The problem is to compute \begin{align*} P_{100} := \frac{1}{\# S} \sum_{\textbf{n} \in S} b(\textbf{n}) = \frac{1}{N} \sum_{\textbf{n} \in S} b(\textbf{n}). \end{align*}

To see why you can assume that there are only $100$ vaults, consider $100 + k$ vaults for some $k \geqslant 1$. Then (extending our notation in an obvious way) we have

\begin{align*} P\left( C_1 = n_1, \ldots, C_{100 + k} = n_{100 + k} \right) = \frac{1}{100^k N}. \end{align*} But for $\textbf{n} = (n_1, \ldots, n_{100+k})$, it is clear that $b (\textbf{n})$ is independent of $n_{101}, \ldots, n_{100+k}$ since $n_i \geqslant 1$ for all $i$. Letting $S_{100+k} = \lbrace 1, \ldots, 100 \rbrace^{100 + k} = S \times \lbrace 1, \ldots, 100 \rbrace^k$, we now see that the average number of vaults the burglar needs to open in the case of $100 + k$ vaults is \begin{align*} P_{100+k} := \frac{1}{100^k N} \sum_{\textbf{n} \in S_{100 + k}} b(\textbf{n}) = \frac{100^k}{100^k N} \sum_{\textbf{n} \in S} b(\textbf{n}) = P_{100}, \end{align*} since there are precisely $100^k$ ways to choose the last $k$ entries of the $(100+k)$-tuple n, and $b(\textbf{n})$ is independent of these entries.