16. Mailboxes. In a newly inhabited apartment building, workers installed a block of 80 mailboxes. Inside each mailbox, they placed a ring with a key and a tag with the apartment number, but they did not bother to ensure that each mailbox contained the key to that mailbox. They simply threw the keys into the mailboxes in a random order. The mailboxes, of course, are locked.

The Absent-Minded Scientist, who recently moved into apartment 37, was delighted to see the mailboxes, but the concierge said she could not get the keys out. One had to go to the management company, which accepts citizens every third Monday of the month from 12:00 to 12:30.

Finding a stick in the trash can (someone had ordered sushi), the Scientist managed to extract a key from mailbox № 37 on the fourth try. He reasoned as follows: if this is the key to my mailbox, then everything is fine. If not, I will open the mailbox to which this key belongs, leave the key in the lock, take out the next key, open the next mailbox, and so on, until I get my key.

a) (for 8th grade, 3 points). Prove that the described algorithm is effective, that is, that the Absent-Minded Scientist will find his key.

b) (for 9th grade, 6 points). Find the expected number of residents who will have to poke in the mailboxes with a stick if they all follow the Absent-Minded Scientist's algorithm.
Solution. We will number the mailboxes and keys in the same way as the apartments. We need to show that sooner or later the Scholar will take out key 37 from mailbox 37.

The sequence of the numbers of the extracted keys cannot be infinite, since there are only 80 apartments. The sequence must end with the number 37. If this is not the case, and the last number is not 37, then the next mailbox will be opened, and the Scholar will take out the next key. But then the previous number will not be the last. Contradiction. Therefore, the last key is 37, which means the algorithm is effective.

To solve problem b), imagine a directed graph where the vertices represent mailboxes. If a key to mailbox $b$ lies in mailbox $a$, then there is an edge $(a ; b)$ in the graph. There are no other edges in the graph. One edge enters each vertex, and one edge leaves each vertex (it may be the same if the key to the same mailbox lies in the mailbox). Thus, the degree of each vertex is 2. Consequently, this graph is a union of non-intersecting cycles. Each tenant, by means of a stick, "lands" in some vertex of this cycle and completes it by retrieving the key to their mailbox. We need to find the average number of cycles $X$.

Let $I_{1,2, \ldots, k}$ be the indicator of the event "vertices $1,2, \ldots, k$ form a cycle, and precisely in this order of vertices," that is, $I_{1,2, \ldots, k}=1$ if this is the case, and $I_{1,2, \ldots, k}=0$ if this is not the case.

If the total number of vertices-mailboxes in the graph is $n$, then the expected value $\mathrm{E} I_{1,2, \ldots k}$ is equal to the probability of this event and is equal to

$$
\frac{1}{n} \cdot \frac{1}{n-1} \cdot \frac{1}{n-2} \cdot \cdots \cdot \frac{1}{n-(k-1)}=\frac{(n-k)!}{n!}
$$

Briefly, let's explain why this is so. The first factor is the probability that key 2 lies in mailbox 1. The second factor is the probability that, given this, key 3 will be in mailbox 2, and so on.

The probability that any ordered set of $k$ vertices forms a cycle is exactly the same. The total number $X_{k}$ of ordered cycles of length $k$ is the sum of the indicators of all possible ordered cycles with exactly $k$ vertices, and there are

$$
C_{n}^{k} \cdot(k-1)!=\frac{n!}{k(n-k)!}
$$

Therefore, $\mathrm{E} X_{k}=\frac{n!}{k(n-k)!} \cdot \frac{(n-k)!}{n!}=\frac{1}{k}$. In other words, on average, there is 1 cycle of length 1, half a cycle of length 2, a third of a cycle of length 3, and so on, the average number of cycles of length $n$ is $\frac{1}{n}$, and the expected value of the number of all cycles is

$$
\mathrm{E} X=1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}
$$

The obtained sum is called the $n$-th harmonic number and is denoted by $H_{n}$. For $n=80$, using a computer or calculator, we find that $H_{n} \approx 4.965$. It is known that there is an approximate equality

$$
H_{n} \approx \ln n+\gamma+\frac{1}{2 n}
$$

where $\gamma$ is the Euler-Mascheroni constant, equal to the limit of the difference between the harmonic number and the natural logarithm: $\gamma=\lim _{n \rightarrow \infty}\left(H_{n}-\ln n\right)$. In practical calculations, $\gamma$ can be taken as 0.58. If we use this approximate formula, we get that the average number of tenants poking with a stick is approximately $\ln 80+0.58+\frac{1}{160} \approx 4.968$.