19. Essay on Suitcases (from 10th grade, 6 points). In the book by Szczepan Jelenski ${ }^{7}$, there is a small essay about suitcases.

A department store received 10 suitcases and 10 keys in a separate envelope, with the warning that each key opens only one suitcase and that a suitable key can be found for each suitcase.

The store employee who received the suitcases sighed:

- What a hassle with key fitting! I know how stubborn inanimate objects can be!! If you start trying to find a key for the first suitcase, it will surely turn out that only the tenth key fits. You'll have to try ten keys for one suitcase, and for ten suitcases - a whole hundred times!

We won't quote Jelenski further, but will briefly summarize the essence. The saleswoman said that the number of attempts would not exceed $10+9+8+\ldots+2+1=55$, another employee suggested reducing the number of attempts even further, since if a key doesn't fit 9 suitcases, it will definitely fit the tenth. Therefore, the number of attempts would not exceed $9+8+\ldots+1=45$. Moreover, he stated that this would only happen in the worst-case scenario - when each time the key fits the last suitcase. In reality, the number of attempts would be approximately

![](https://cdn.mathpix.com/cropped/2024_05_06_42ce3a039dda61c7f471g-11.jpg?height=551&width=446&top_left_y=1666&top_left_x=291)
half of the maximum possible number of attempts, that is, 22.5.

Igor Fedorovich Akulich from Minsk wondered why the average number of attempts equals half of the number 45? After all, the last attempt is not needed only if the key doesn't fit any suitcase except the last one, but in all other cases, the last successful attempt also takes place. Akulich suspected that the claim about 22.5 attempts was baseless, and in reality, things are a bit different.

Problem. Find the mathematical expectation of the number of attempts (all attempts to open the suitcases are counted - unsuccessful and successful, in the case when there is no clarity).
Solution. We will solve the problem in a general form, assuming that there are $n$ suitcases. Let $Y$ be a random variable equal to the number of attempts to open the first of $n$ suitcases. Obviously, $Y=1$ with probability $1 / n$, $Y=2$ with probability $\frac{n-1}{n} \cdot \frac{1}{n-1}=\frac{1}{n}$, and so on, up to $Y=n-2$, but the event $Y=n-1$ has a probability of $2 / n$, since it occurs in two equally likely cases: when the correct key is the $(n-1)$-th or $n$-th in sequence. Then[^4]

$$
\mathrm{E} Y=\frac{1+2+\ldots+(n-2)+(n-1) \cdot 2}{n}=\frac{1+2+\ldots+(n-2)+(n-1)+n}{n}-\frac{1}{n}=\frac{n+1}{2}-\frac{1}{n}
$$

Now, let $X_{n}$ be the number of attempts. After the first suitcase is somehow opened, there will be $n-1$ suitcases left, and it will take $X_{n-1}$ attempts for them. And so on. Therefore, $X_{n}=Y+X_{n-1}$, and by transitioning to expectations and introducing the notation $e_{n}=\mathrm{E} X_{n}$ for brevity, we find:

$$
e_{n}=e_{n-1}+\frac{n+1}{2}-\frac{1}{n}=e_{n-2}+\frac{n}{2}-\frac{1}{n-1}+\frac{n+1}{2}-\frac{1}{n} \text { and so on. }
$$

Considering that $e_{1}=0$, we eventually obtain an explicit formula:

$$
\begin{aligned}
& e_{n}=\frac{3+4+\ldots+(n+1)}{2}-\left(\frac{1}{n}+\frac{1}{n-1}+\ldots+\frac{1}{2}\right)= \\
& =\frac{(n-1)(n+4)}{4}+1-\left(\frac{1}{n}+\frac{1}{n-1}+\ldots+\frac{1}{2}+1\right)=\frac{n(n+3)}{4}-H_{n}
\end{aligned}
$$

where $H_{n}$ is the $n$-th harmonic number, equal to

$$
1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots+\frac{1}{n}
$$

It is known that $H_{n} \approx \ln n+\gamma+\frac{1}{2 n}$, where $\gamma=0,5772 \ldots$ is the Euler-Mascheroni constant. With a reasonably small error, we can assume that

$$
e_{n} \approx \frac{n(n+3)}{4}-(\ln n+0,577)
$$

For $n=10$, we get $e_{10} \approx 32,5-(\ln 10+0,577) \approx 29,62$.

Answer: approximately 29.62.

[^0]:    ${ }^{1}$ Karpach Kirpich (Konstantin Saprykin) - a character from the novel "Era of Mercy" by the Vayner brothers. This novel was the basis for the famous film "The Meeting Place Cannot Be Changed".

[^1]:    ${ }^{2}$ The problem is based on a plot devised by Andrei Dmitrievich Sakharov about himself. The difference is that Academician Sakharov had not two umbrellas but three pairs of galoshes. Try to solve the original problem with three pairs of galoshes (or umbrellas). The problem was reconstructed by I.F. Ginzburg. Academician A.D. Sakharov. Scientific Works. Collection. - M.: AOZT "Izdatel'stvo TsentrKom", 1995).

    ${ }^{3}$ The tree will be a bit simpler if you notice that the edges $B_{0} R$ and $B_{0} D$ can be identified, since the Scholar will definitely take an umbrella if there is no umbrella in V. The same trick is possible with the chains $B_{1} R R$ and $B_{1} R D$.

[^2]:    But explaining how the "simplified" tree is constructed is a bit more complicated than the one we built. Therefore, we decided to build the unsimplified one.

    ${ }^{4}$ If you believe O. Henry, Anchuria has five cities: San Mateo, Coralio, Solitas, Alforan, and Alasan.

[^3]:    ${ }^{5}$ The apparent paradox lies in the fact that when comparing the probabilities of events related only to Dima and Mitya, one has to take into account the event related to Mitya and Vanya. What does Vanya have to do with it? ${ }^{6}$ The probability that there are an equal number of heads in two random stacks of the same number of coins is easy to find if you flip the second stack and place it on top of the first. This means that it is sufficient to find the probability that in a stack of double the number of coins, the number of heads is exactly half.

[^4]:    ${ }^{7}$ "In the Footsteps of Pythagoras" (M., Detgiz, 1961).