We have 30 padlocks and for each one, we have a key that does not open any of the other padlocks. Someone randomly drops the keys into the closed padlocks, one into each. We break open two padlocks. What is the probability that we can open the rest without breaking any more padlocks?
I. Solution. Before we start the opening, let's line up the boxes starting with the two we will break open and write their numbers on them.

After the keys were randomly thrown into the boxes, and the two boxes to be broken open are also chosen randomly, every arrangement of the keys in the boxes is equally likely to occur.

Now we break open the first two boxes. If the key in the first box is not its own, we use the key found in it to open the box it unlocks, take out the key inside, and set the box aside. We use the new key to open the appropriate box, take out the key inside, and place the box next to the previous one, and so on, until we can.

If the key to the second box also comes up during this process, we proceed as if we hadn't broken it open, take out the key from it as well, and place the box in the row of opened boxes.

We get stuck when the key to the first box comes up, which can happen as soon as we take out the key from the first box. It is clear that the key to any other opened box cannot come up, as it has already come up before, and each box has only one key.

When the key to the first box comes up, we also move the first box into the row of opened boxes. Then we take out the key from the second box if it hasn't come up yet, and continue the process. This ends when the key to the second box also comes up.

If we haven't opened all the boxes by then, which is an unfavorable case in terms of the probability we are looking for, we continue the process by always breaking open the first unopened box whenever we get stuck.

In this way, we have assigned a sequence of (opened) boxes to each key distribution in the boxes. Conversely, knowing the box sequence, we can put back each key into the box it was thrown into. The key from the first box in the sequence must go into the box numbered 1, and then the key from each box up to the first numbered one must go into the box in front of it. The key from the box after the first numbered one goes into the box with the smallest number that is still empty, and the keys from the boxes that are in front go into the box in front of them, and so on.

The arrangement of the boxes belongs to a favorable sequence of keys if the last place is occupied by the box numbered 1 or 2, otherwise it belongs to an unfavorable sequence of keys. No matter which box is in the last place, the ones in front of it can always be arranged in the same number of ways, so the event that a given box is in the last place is equally probable, totaling 30. Of these, 2 are favorable, so the probability we are looking for is 1/15.

It is clear that in general, if there are $n$ boxes and $k$ of them are broken open $(k \leq n)$, then the probability that we can open every box is $k / n$.

Remark. Most contestants counted all and the favorable key distributions, partly by also counting the selection of the boxes to be broken open as part of the events. Some simplified the counting of favorable events by pairing each arrangement where it was essential to break open the second box with a unique arrangement where the second box did not need to be broken open. We get such an arrangement by placing the key from the first box into the box where the second key was and vice versa.

II. Solution. We will prove that if we randomly throw the keys of $n$ boxes into the boxes and break open two of them, then the probability that we can open every box is $2 / n$.

Let $p_{n}$ denote the probability we are looking for. Clearly, $p_{2}=1$. We will show that if $n \geq 2$, then

$$
p_{n+1}=\frac{n}{n+1} p_{n}
$$

From this, it follows that

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

and for the problem at hand, $p_{30}=1 / 15$.

Consider an arrangement $E$ of the $n+1$ keys in the boxes. Let $r$ be the number of the box in which the key to the $(n+1)$-th box is and $s$ be the number of the box whose key is in the $(n+1)$-th box. It is clear that either $r$ and $s$ are both equal to $(n+1)$ (the last box contains its own key), or both are less than $n+1$.

In the former case, ignoring the $(n+1)$-th box, we get an arrangement $E_{1}$ of the first $n$ keys in the first $n$ boxes. In the latter case, we also assign an $E_{1}$ arrangement to $E$, which differs from $E$ only in that the $s$-th key is thrown into the $r$-th box.

In this way, we have assigned an $E_{1}$ to every $E$. Conversely, if we know $E_{1}$, it could have come from $E$ by taking the key from the first, or the second, or ..., or the $n$-th box and replacing the key in the $(n+1)$-th box, or by ignoring the $(n+1)$-th box, which contained its own key. Thus, the $n$ keys in an $E_{1}$ arrangement correspond to $(n+1)$ different arrangements of the $n+1$ keys.

If we now break open the first 2 boxes, then in both $E$ and $E_{1}$, we can open the same boxes until we reach the $r$-th box. If this happens, in $E$ the $(n+1)$-th box becomes openable, and then opening it, the $s$-th box, while in $E_{1}$ the $s$-th box is directly openable. Further, in both key arrangements, the same boxes can be opened.

Thus, all $n+1$ boxes can be opened in the $E$ key arrangement if and only if all $n$ boxes can be opened with the corresponding $E_{1}$ key arrangement and the $(n+1)$-th box does not contain its own key.

Accordingly, to every possible arrangement of the $n$ keys, $(n+1)$ arrangements of the $n+1$ keys correspond, and to every arrangement where all boxes can be opened, $n$ such arrangements of the $n+1$ keys correspond. This precisely provides the (1) relationship.

Remark. It can be similarly shown that (1) also holds if $p_{n}$ is the probability that all boxes can be opened when $k$ boxes are broken open. Since in this case $p_{k}=1$, it follows again that in this more general case $p_{n}=k / n$.