15. English Club (from 9th grade. 6 points). Every Friday, ten gentlemen come to the club, and each hands their hat to the doorman. Each hat fits its owner perfectly, but no two hats are the same size. The gentlemen leave one by one in a random order.

When seeing off each gentleman, the doorman tries to put on the first hat he finds. If it fits, the gentleman leaves with that hat. If it is too small, the doorman tries the next random hat from the remaining ones. If all the remaining hats are too small, the doorman says to the poor man: "Sir, a hat does not suit you today," and the gentleman goes home with an uncovered head. Find the probability that next Friday the doorman will not have any hats left.

IX Olympiad in Probability Theory and Statistics for Schoolchildren. Correspondence Round.

(From the Laboratory of Probability Theory and Statistics of the Moscow Center for Continuous Mathematical Education, 2015-2016

![](https://cdn.mathpix.com/cropped/2024_05_06_164205c0ca2288d5a185g-18.jpg?height=391&width=534&top_left_y=216&top_left_x=293)
Solution. Let the number of gentlemen be $n$. We will number them in the order of increasing sizes of their hats from 1 to $n$. No hats will be left only if each took his own hat. Let the probability of this be $p_{n}$. If the $k$-th gentleman leaves first (the probability of this is $\frac{1}{n}$), then the probability of him getting his own hat is $\frac{1}{n-k+1}$ (since his own hat is the only one among $n-k+1$ suitable for this gentleman). If this happens, the probability that all the remaining will take their own hats is $p_{n-1}$. By the formula of total probability, we get:

$$
p_{n}=\frac{1}{n} \cdot \frac{1}{n} p_{n-1}+\frac{1}{n} \cdot \frac{1}{n-1} p_{n-1}+\ldots+\frac{1}{n} \cdot \frac{1}{2} p_{n-1}+\frac{1}{n} \cdot \frac{1}{1} p_{n-1}=\frac{H_{n}}{n} p_{n-1}
$$

where $H_{n}=1+\frac{1}{2}+\ldots+\frac{1}{n}$ is the $n$-th harmonic number. Considering that $p_{1}=1$ (if there is only one gentleman, he will definitely take his own hat), we get:

$$
p_{n}=\frac{H_{n}}{n} p_{n-1}=\frac{H_{n} H_{n-1}}{n(n-1)} p_{n-2}=\ldots=\frac{\left(H_{n}\right)!}{n!}
$$

where the symbol $\left(H_{n}\right)!$ denotes the product of all harmonic numbers from $H_{1}=1$ to $H_{n}$. Substituting $n=10$, we get: $p_{10}=\frac{1 \cdot\left(1+\frac{1}{2}\right)\left(1+\frac{1}{2}+\frac{1}{3}\right) \cdot \ldots \cdot\left(1+\frac{1}{2}+\ldots+\frac{1}{10}\right)}{10!} \approx 0.000516$. The calculation can be easily performed using a calculator or computer.

Answer: approximately 0.000516.