17. Successful Pairs. Vasya bought $n$ pairs of identical socks. For $n$ days, Vasya had no problems: every morning he took a new pair from the closet and wore it all day. After $n$ days, Vasya's mother washed all the socks in the washing machine and paired them up as they came out, since, to reiterate, the socks are identical. We will call a pair of socks successful if both socks in this pair were worn by Vasya on the same day.

a) (7 - $\mathbf{1 1}$ classes, 2 points) Find the probability that all the resulting pairs are successful.

b) (8 - $\mathbf{1 1}$ classes, 3 points) Prove that the expected number of successful pairs is greater than 0.5.
Solution. a) The probability that the first pair turned out to be a successful one is $\frac{1}{2 n-1}$, since when the mother took the first sock in her hand, there were $2 n-1$ socks left, and only one of them forms a successful pair with the first. Further - the same: the probability that the second pair is successful (given that the first pair is successful) is $\frac{1}{2 n-3}$, and so on. The probability that all pairs are successful is obtained as the product

$$
\frac{1}{2 n-1} \cdot \frac{1}{2 n-3} \cdot \ldots \cdot \frac{1}{3}=\frac{1}{(2 n-1)!!}=\frac{(2 n)!!}{(2 n)!}=\frac{2^{n} n!}{(2 n)!}
$$

(The double factorial $m!!$ of a natural number $m$ is the product of all natural numbers not exceeding $m$ and having the same parity as $m$. If $m$ is odd, then $m!!=1 \cdot 3 \cdot \ldots \cdot m$, and if $m$ is even, then $m!!=2 \cdot 4 \cdot \ldots \cdot m$.)

To find an approximate expression, we apply Stirling's formula for factorials: $m!\approx \sqrt{2 \pi m} \cdot m^{m} e^{-m}:$

$$
\frac{2^{n} n!}{(2 n)!} \approx \frac{2^{n} \sqrt{2 \pi n} \cdot n^{n} e^{-n}}{\sqrt{4 \pi n} \cdot(2 n)^{2 n} e^{-2 n}}=\frac{1}{\sqrt{2}}\left(\frac{e}{2 n}\right)^{n} .
$$

b) The probability that each one pair is successful, found in part a) - it is equal to $\frac{1}{2 n-1}$. Let's number the pairs from 1 to $n$ and use the method of indicators. Let

$$
\xi_{k}=\left\{\begin{array}{l}
1, \text { if } k-\text { - pair is successful, } \\
0, \text { if } k-\text { pair is unsuccessful. }
\end{array}\right.
$$

Then

$$
\mathrm{E} \xi_{k}=1 \cdot \frac{1}{2 n-1}+0 \cdot \frac{2 n-2}{2 n-1}=\frac{1}{2 n-1} .
$$

The random variable $X$ "number of successful pairs" is equal to the sum of the indicators:

$$
X=\xi_{1}+\xi_{2}+\ldots+\xi_{n}
$$

Then

$$
\mathrm{E} X=n \mathrm{E} \xi_{1}=\frac{n}{2 n-1}>\frac{1}{2}
$$

End of proof.

Answer: a) $\frac{2^{n} n!}{(2 n)!} \approx \frac{1}{\sqrt{2}}\left(\frac{e}{2 n}\right)^{n}$.