Connecting n keys to n safes in minimal number of attempts

Question

Suppose I have $n$ safes and $n$ keys "arranged in random succession", each safe unlockable by exactly one of those keys. To find out which key belongs to which safe I am allowed to try unlock a safe with one of the keys: such an attempt is counted as one "turn".

I know that if I try to match the first key with the first safe, try to match it with the 2nd safe if that first attempt failed, try to match it with the 3rd safe if that 2nd attempt failed,..., try to match it to safe no. $n-1$ if the $n-2$'nd attempt failed, then after at most $n-1$ turns I can locate the safe belonging to the first key. Hence, I can situate the 2nd key in $n-2$ turns, the 3rd key in $n-3$ turns,..., key no. $n-1$ in $1$ turn and the final key is associated to the final remaining safe and requires no turn. To conclude: there's clearly a strategy which permits a solution to this problem requiring $(n-1)+(n-2)+...+1+0=\frac{n(n-1)}{2}$ turns in the worst-case scenario.

Is it possible to arrive with a better strategy, as measured in the no. of turns in the worst-case scenario? If not, how to prove that $n(n-1)/2$ is the optimal number of turns required in the worst case?

Addendum: one comment hinted the possibility that there's just "the number of turns in the worst-case scenario" in stead of the "optimal number of turns in the worst-case scenario". To partially address this comment, let me give an example of a strategy (which is "bona-fide" in the sense that every turn consists of trying a key-vs-safe pair that wasn't attempted before and we still allow to match safes with keys "by elimination") whose worst-case performance is worse than $n(n-1)/2$. Here it goes:

*First we try to match key $1$ to safe $1$, then key $2$ to safe $2$,..., key $n$ to safe $n$

*Next, we try to match key $1$ to safe $2$, then key $2$ to safe $3$,..., then key $n-1$ to safe $n$ and then key $n$ to safe $1$.

*...

*Next we try to match key $1$ to safe $n-1$, then key $2$ to safe $n$, key $3$ to safe $1$,...,key $n$ to safe $n-2$.

Now, if the keys and safes were arranged so that key $1$ were matched to safe $n$, key $2$ to safe $1$, key 3 to safe $2$,..., key $n$ to safe $n-1$, we would have spent $n(n-1)$ turns before determining which key is matched to which safe.

Answer 1

I think that you can prove $\binom{n}2$ tests is optimal using Hall's marriage theorem, specifically the following generalization, due to Marshall Hall Jr:

Suppose you have a collection of sets $A_1,A_2,\dots,A_n$, which satisfies:

• Hall condition: For any $I\subseteq \{1,2,\dots,n\}$, $\left|\bigcup_{i\in I} A_i\right|\ge |I|$.

• Each $|A_i|\ge r$, for some number $r\le n$.

Then there exists a way to select from each set $A_i$ an element $a_i$ such that the elements $a_i$ are pairwise distinct. Furthermore, this can be done in at least $r!$ ways.

Suppose that you have performed fewer than $\binom{n}2$ tests. Further suppose that none of those tests were successful. This is a valid assumption; once you have deduced a key goes in a lock, there is no reason to test it. Therefore, for every test you make in an optimal strategy, there must be a possibility that the key you test did not unlock that safe, so in the worst case all tests are unsuccessful.

Assume that no key was tested $n-1$ times. I claim this implies you cannot deduce the true assignment. If you let $K_i$ be the set of safes you have not tested the $i^{th}$ key on, then a valid assignment exists, implying Hall's condition is fulfilled, and by assumption each $|K_i|\ge 2$. We have verified both conditions of the above proposition, so at least $2!$ assignments exist. Therefore, if you can deduce the assignment, some key must have been tested $n-1$ times, meaning you know what safe it goes in. What remains are $n-1$ keys to be matched with $n-1$ safes, which have been tested fewer than $\binom{n}2-(n-1)=\binom{n-1}2$ times. By induction, we can conclude there is more than one valid assignment.