12. Stefan Banach ${ }^{1}$ and matches (8th grade, 4 points). An incredible legend says that one day in a small shop in the center of Lviv, Stefan Banach bought two boxes of matches and put them in his jacket pocket. Each box contained 60 matches.

When Banach needed a match, he would randomly pick a box and take a match from it. At some point, Banach took a box and found it to be empty. Find the expected number of matches in the other box.

![](https://cdn.mathpix.com/cropped/2024_05_06_9f21f524e97cb708e16ag-08.jpg?height=417&width=414&top_left_y=248&top_left_x=1529)
Answer: approximately 7.795.

Solution proposed by Olympiad participant Alexandra Nesterenko. Let there be $n$ matches in the box. Banach took a box (let's call it red for definiteness) and found it to be empty. Banach knows that he took the red box $n$ times, and the second (blue) box he could have taken $k$ times, where $0 \leq k \leq n$. If Banach took the second box $k$ times, there are $n-k$ matches left in it. In total, Banach took matches from the boxes $n+k$ times with a probability of taking a match from the blue box of 0.5. The probability that the second box was chosen $k$ times out of $n+k$ trials is

$$
C_{n+k}^{k} \cdot \frac{1}{2^{n+k}}
$$

Therefore, the expected number of matches in the second box is

$$
\mu=\sum_{k=0}^{n} \frac{(n-k) C_{n+k}^{k}}{2^{n+k}}
$$

The sum $\sum_{k=0}^{n} \frac{C_{n+k}^{k}}{2^{n+k}}$ equals 1, since it is the sum of the probabilities of all possible outcomes. This results in the expression

$$
\mu=n-\sum_{k=0}^{n} \frac{k C_{n+k}^{k}}{2^{n+k}}
$$

The calculation can be performed using this formula with the help of spreadsheets. For $n=60$, we get $\mu \approx 7.795$.

Comment. The solution can be continued and the obtained expression can be simplified. Let's transform the sum:

$$
\sum_{k=0}^{n} \frac{k C_{n+k}^{k}}{2^{n+k}}=(n+1) \sum_{k=1}^{n} \frac{C_{n+k}^{k-1}}{2^{n+k}}=(n+1) \sum_{m=0}^{n-1} \frac{C_{n+1+m}^{m}}{2^{n+1+m}}
$$

In the last equality, the substitution $m=k-1$ was made. The resulting sum is similar to the sum $\sum_{k=0}^{n} \frac{C_{n+k}^{k}}{2^{n+k}}=1$, rewritten for $n+1$. The difference is in the upper limit of summation. Let's use this:

$$
\sum_{m=0}^{n-1} \frac{C_{n+1+m}^{m}}{2^{n+1+m}}=\sum_{m=0}^{n+1} \frac{C_{n+1+m}^{m}}{2^{n+1+m}}-\frac{C_{2 n+1}^{n}}{2^{2 n+1}}-\frac{C_{2 n+2}^{n+1}}{2^{2 n+2}}
$$[^0]

The first term, as we know, equals 1, and $C_{2 n+1}^{n+1}=\frac{1}{2} C_{2 n+2}^{n+1}$. We get:

$$
\mu=n-(n+1) \cdot\left(1-\frac{C_{2 n+2}^{n+1}}{2^{2 n+1}}\right)=(n+1) \frac{C_{2 n+2}^{n+1}}{2^{2 n+1}}-1
$$

Figure 6 shows the calculation using this formula with the help of a spreadsheet.

![](https://cdn.mathpix.com/cropped/2024_05_06_9f21f524e97cb708e16ag-09.jpg?height=294&width=1076&top_left_y=527&top_left_x=570)

Fig. 6

One more step can be made using Stirling's formula $m!\approx \sqrt{2 \pi m} \frac{m^{m}}{e^{m}}$. Verify that $\frac{C_{2 n+1}^{n+1}}{2^{2 n+1}} \approx \frac{2}{\sqrt{\pi(n+1)}}$. Then $\mu \approx 2 \sqrt{\frac{n+1}{\pi}}-1$. Calculation using this approximate formula gives $\mu \approx 7.813$, which is very close to the truth.