A bag contains 100 red and 100 blue balls. We draw balls randomly, one by one, without replacement, until we have drawn all 100 red balls. Determine the expected value of the number of balls left in the bag.
I. solution. After each draw, we write down what ball we drew. If it's blue, we denote it with $K$, and if it's red, we denote it with $P$. After the 100th red, we write down as many blues as remain in the bag. This way, we end up with a 200-long $P-K$ sequence, which contains $100 \mathrm{db} P$ and $100 \mathrm{db} K$.

In total, we can write $\binom{200}{100}$ such sequences.

Let's count the possibilities when $k$ balls remain in the bag. That is, the last $k$ letters are $K$ and before them, $P$ is. We can draw the other balls in any order, so on the first $200-k-1$ positions, we can write $99 \mathrm{db} P-\mathrm{t}$ and $100-k \mathrm{db}$ $K-\mathrm{t}$ in all possible arrangements. This can be done in $\binom{199-k}{99}$ ways (we choose which positions will have red $(P)$ balls.) Thus, the probability that $k$ balls remain in the bag is:

$$
\frac{\binom{199-k}{99}}{\binom{200}{100}}
$$

Then the expected value we are looking for can be written in the following form:

![](https://cdn.mathpix.com/cropped/2024_05_02_c063ced0822e4c3430ecg-1.jpg?height=135&width=1118&top_left_y=770&top_left_x=493)

Our goal is to simplify the expression in the square brackets. For this, we will use the following identity:

$$
\binom{n}{k}+\binom{n-1}{k}+\ldots+\binom{k}{k}=\binom{n+1}{k+1}
$$

(The proof of this, known as the hockey-stick identity, is: replace the $\binom{k}{k}$ term in the sum with $\binom{k+1}{k+1}$, then from right to left, always replace the last two terms with the appropriate term using the identity $\binom{l}{m}+\binom{l}{m+1}=\binom{l+1}{m+1}$.)

Based on this, we get the following equations:

$$
\begin{aligned}
\binom{198}{99}+\binom{197}{99}+\binom{196}{99}+\ldots+\binom{99}{99} & =\binom{199}{100} \\
\binom{197}{99}+\binom{196}{99}+\ldots+\binom{99}{99} & =\binom{198}{100} \\
\binom{196}{99}+\ldots+\binom{99}{99} & =\binom{197}{100}, \\
& \vdots \\
\binom{100}{99}+\binom{99}{99} & =\binom{101}{100} \\
\binom{99}{99} & =\binom{100}{100}
\end{aligned}
$$

Adding these equations, we get that the left side is exactly the expression in the square brackets, while the right side can be transformed (again using the hockey-stick identity):

$$
\binom{199}{100}+\binom{198}{100}+\ldots+\binom{101}{100}+\binom{100}{100}=\binom{200}{101}=\binom{200}{99}
$$

Thus, the expected value we are looking for is:

![](https://cdn.mathpix.com/cropped/2024_05_02_c063ced0822e4c3430ecg-1.jpg?height=129&width=494&top_left_y=2223&top_left_x=810)

Remark. The statement of the problem can also be formulated for $n$ blue and $n$ red balls, in which case the expected value is $\frac{n}{n+1}$.

Remark. The fact that the desired sum is $\binom{200}{101}$ was proven by Busa Máté (Nagykanizsa, Batthyány Lajos Gimn., 11th grade) as follows: Consider the first 200 positive integers. We want to choose 101 numbers from these. This can be done in $\binom{200}{101}$ ways. Counting in another way: Let the 100th smallest number among the chosen numbers be an $x$, where $x$ is clearly at least 100 and at most 199. In such a case, where the 100th smallest number is $x$, there are exactly $(200-x) \cdot\binom{x-1}{99}$ possibilities, because the largest chosen number can be $(200-x)$ ways, and the 99 numbers smaller than $x$ can be chosen in $\binom{x-1}{99}$ ways. If we sum the possibilities for the possible $x$ values, we get that

$$
\binom{200}{101}=\sum_{x=100}^{199}(200-x) \cdot\binom{x-1}{99}=100 \cdot\binom{99}{99}+99 \cdot\binom{100}{99}+\ldots+1 \cdot\binom{198}{99}
$$

II. solution. We can assume that after the last red ball is drawn, we also draw the remaining balls one by one. Thus, the 200 balls can have $\binom{200}{100}$ different orders, each case being equally probable. We can assume that the balls were drawn in reverse order, then we are looking for the