19. Monochromatic pairs. In a box, there are $n$ white and $n$ black balls. Balls are drawn from the box in pairs - random pairs.

a) (from 9th grade. 2 points). Find the expected number of mixed-color pairs drawn from the box by the time it is empty.

b) (from 9th grade. 5 points). Suppose that if a pair is mixed-color, it is set aside, and if it is monochromatic, it is returned to the box. Such an operation is called an attempt. Find the expected number of attempts needed to set all the balls aside, leaving nothing in the box.
Solution. a) Let us mentally number all the black balls. Introduce a random variable $I_{k}$ - the indicator of the event $A_{k}$ "the $k$-th black ball has a white one in its pair", that is,

$$
I_{k}=\left\{\begin{array}{l}
0, \text { if event } A_{k} \text { does not occur, } \\
1, \text { if event } A_{k} \text { occurs. }
\end{array}\right.
$$

The expected value of this random variable is

$$
\mathrm{E} I_{k}=\mathrm{P}\left(A_{k}\right)=\frac{n}{2 n-1}
$$

The random variable $X_{n}$ "the number of mixed pairs" is equal to the sum of all $n$ indicators:

$$
X_{n}=I_{1}+I_{2}+\ldots+I_{n}
$$

We transition to the expected values in this equality:

$$
\mathrm{E} X_{n}=\mathrm{E} I_{1}+\mathrm{E} I_{2}+\ldots+\mathrm{E} I_{n}=n \cdot \frac{n}{2 n-1}=\frac{n^{2}}{2 n-1}
$$

b) Let the required number of attempts be $X_{n}$. Let $I$ be the indicator of the event "a mixed pair appeared on the first attempt", that is,

$$
I=\left\{\begin{array}{l}
0, \text { if the first pair is of the same color, } \\
1, \text { if the first pair is mixed. }
\end{array}\right.
$$

The expected value of the random variable $I$ is

$$
\mathrm{E} I=\mathrm{P}(I=1)=\frac{n}{2 n-1}
$$

After the first attempt, there remain $k$ pairs in the box: $k=n$ if the pair was returned to the box, or $k=n-1$ if the pair was removed. Therefore, a new random variable $Y_{k}$ "the number of attempts needed to set aside $k$ pairs of balls remaining after the first attempt" arises. Then

$$
X_{n}=I Y_{n-1}+(1-I) Y_{n}+1
$$

Due to the independence of $I$ and $Y_{k}$

$$
\mathrm{E} X_{n}=1+\mathrm{E} I \cdot \mathrm{E} Y_{n-1}+(1-\mathrm{E} I) \cdot \mathrm{E} Y_{n}
$$

Introduce the notation $m_{k}=\mathrm{E} Y_{k}$. In this case, $\mathrm{E} X_{n}=\mathrm{E} Y_{n}=m_{n}$. We get:

$$
m_{n}=\frac{n}{2 n-1} m_{n-1}+\left(1-\frac{n}{2 n-1}\right) m_{n}+1
$$

from which $m_{n}=m_{n-1}+2-\frac{1}{n}$.

Setting the initial value of the recursion $m_{1}=1$ (if there is 1 white and 1 black ball in the box, exactly one attempt is needed) we find:

$$
m_{2}=1+2-\frac{1}{2}=2 \cdot 2-\left(1+\frac{1}{2}\right), \quad m_{3}=\left(2 \cdot 2-\left(1+\frac{1}{2}\right)\right)+2-\frac{1}{3}=2 \cdot 3-\left(1+\frac{1}{2}+\frac{1}{3}\right)
$$

and so on:

$$
m_{n}=2 n-\left(1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}\right)=2 n-H_{n}
$$

where $H_{n}=1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}$ is the $n$-th harmonic number.

Comment. It is known that $H_{n} \approx \ln n+\gamma$, where $\gamma=0,5772156 \ldots$ is the Euler-Mascheroni constant. Therefore, we can approximate

$$
m_{n} \approx 2 n-\ln n-\gamma
$$

with the error being smaller the larger $n$ is. For example, if there are 20 balls in the box ($n=10$), the exact formula gives $m_{10}=17,071$ (rounded to the thousandths), while the approximate formula gives $m_{10} \approx 17,120$, so the error does not exceed 0.05.

Answer: a) $\frac{n^{2}}{2 n-1}$; b) $2 n-H_{n}$, where $H_{n}=1+\frac{1}{2}+\frac{1}{3} \ldots+\frac{1}{n}$ or, approximately, $2 n-\ln n-0,577$

![](https://cdn.mathpix.com/cropped/2024_05_06_a6149daf2f3a04ecb66bg-18.jpg?height=134&width=1348&top_left_y=133&top_left_x=385)

## XII INTERNET OLYMPIAD IN PROBABILITY THEORY AND STATISTICS. MAIN (CORRESPONDENCE) ROUND

## Analysis of Submitted Essays