Given $n$ locked chests and $n$ keys such that each chest is opened by exactly one key and each key opens exactly one chest. Our goal is to determine which key opens each chest. A trial consists of trying to open a chest with a key. Determine the smallest number $p(n)$ such that there exists a procedure that, when followed, ensures we will know the $n$ corresponding chest-key pairs after at most $p(n)$ trials.
Solution. We will show that for $n \geq 1$, $p(n)=\binom{n}{2}$. The following procedure solves the problem in at most $\binom{n}{2}$ attempts, i.e., $p(n) \leq \binom{n}{2}$. Let the keys be $k_{1}, k_{2}, \ldots, k_{n}$, and let $b_{i}$ denote the lock that $k_{i}$ opens. Our goal is to find $b_{i}$ for every $i$. We try the $k_{1}$ key in the first few locks until we determine which one is $b_{1}$. This requires at most $n-1$ attempts, because as soon as we have tried and failed $(n-1)$ times, we immediately know that $k_{1}$ must open the last untried lock. We do the same with the $k_{2}$ key, with the restriction that we do not try the $b_{1}$ lock. For similar reasons, we make at most $n-2$ attempts until we find $b_{2}$. Generally, after finding $b_{1}, b_{2}, \ldots, b_{i-1}$, we find $b_{i}$ by trying the $k_{i}$ key in the remaining $n-(i-1)=n-i+1$ locks. Clearly, we will find $b_{i}$ in at most $n-i$ attempts. In total, we perform no more than $\sum_{i=1}^{n}(n-i)=\binom{n}{2}$ attempts.

On the other hand, we will show that $p(n) \geq \binom{n}{2}$, i.e., with fewer than $\binom{n}{2}$ attempts, we cannot be certain that we will always find the matching lock-key pairs. Suppose we try the keys in the locks according to a method that identifies the matching lock-key pairs and also minimizes the maximum number of attempts required. It is clear that using this strategy, we will never try a key in a lock if we are already certain that the key opens that lock. This means we must be prepared to confirm all matching $\left(b_{i}, k_{i}\right)$ lock-key pairs based on a series of failed attempts.

If this happens and for some $1 \leq i < j \leq n$ we have not tried either the $k_{i}$ key in the $b_{j}$ lock or the $k_{j}$ key in the $b_{i}$ lock, then based on the attempts we have made, we cannot rule out the possibility that the $k_{i}$ key opens the $b_{j}$ lock and the $k_{j}$ key opens the $b_{i}$ lock, while the other keys open the locks we thought they did. This would mean that we cannot be certain about the correct pairing of keys and locks. Therefore, for any $1 \leq i < j \leq n$, we must perform at least one of the $k_{i}-b_{j}$ or $k_{j}-b_{i}$ attempts. Since these attempts are different for different $(i, j)$ pairs, we need at least as many attempts as there are ways to choose different $i$ and $j$, i.e., at least $\binom{n}{2}$. This shows that $p(n) \geq \binom{n}{2}$, and combining this with the previously proven $p(n) \leq \binom{n}{2}$, we get the desired result $p(n)=\binom{n}{2}$.

Remarks. 1. The key step in the above proof is the proof of the lower bound, particularly the use of the "adversary method," where we show that even with all negative attempts, we must still be able to pair the keys and locks correctly.

2. The lower bound can also be stated in graph-theoretic terms. Consider the graph $G$ whose vertices are the locks and keys, and edges represent the matching pairs. Clearly, each attempt corresponds to querying whether a potential lock-key edge is in $G$, and our goal is to determine $G$. The argument using the adversary method (adversary method) justifies that we must be able to determine $G$ even if every meaningful query reveals that the edge is not in $G$. The proof given above can also be stated as follows: if $G$ can be determined from the negative results of the queries, then for any $i \neq j$, at least one of the $k_{i} b_{j}$ or $k_{j} b_{i}$ edges must have been queried.

There is another way to prove the lower bound. If the negative results of the queries uniquely determine $G$, then the unqueried $k-b$ edges cannot form an alternating cycle with the edges of $G$. Otherwise, it would not be possible to rule out that the keys and locks are paired along the edges of this cycle that are not in $G$. (In the above proof, we worked with a 4-length alternating cycle.) From this, it can be easily shown that some lock or key must have been involved in at least $n-1$ attempts. Suppose this is $k_{n}$ or $b_{n}$. Similarly, it can be shown that among the $b_{1}, b_{2}, \ldots, b_{n-1}$ locks or the $k_{1}, k_{2}, \ldots, k_{n-1}$ keys, some (say the $(n-1)$-th) must have been involved in at least $n-2$ attempts where neither $b_{n}$ nor $k_{n}$ was used. Continuing this line of reasoning, it can be shown that the matching $b_{i} k_{i}$ lock-key pairs can be indexed such that for every $1 \leq i \leq n$, $b_{i}$ or $k_{i}$ was involved in at least $i-1$ attempts where $b_{i+1}, \ldots, b_{n}$ and $k_{i+1}, \ldots, k_{n}$ were not used.

3. Several people attempted a similar line of reasoning. Some made the mistake of trying to prove that the graph of unqueried edges is acyclic. Unfortunately, this is generally not true. In fact, this graph cannot contain an alternating cycle with the edges of $G$. Fortunately, as the outline of the proof in the previous remark shows, this is sufficient for the lower bound.