19
$\begingroup$

Let $a,b,n$ be positive integers in which $a,b\le n$. You are locked in a room, with $n$ distinguishable keys and $n$ distinguishable locks in it. You know that each lock can be unlocked by a unique key, but you don't know which key unlocks which lock. You also know each key initially has a durablility of $a$ and each lock initially has a durability of $b$. The only way out of the room is unlock at least one of the locks, but each time you try to unlock a lock using a key, the durablility of both that lock and key will decrease by $1$. A key or lock cannot be used for any further unlocking attempts if its durability is $0$. For each $n$, what pairs of $a,b$ guarentees a strategy which you can certainly leave the room?


I haven't posted in a while, let's see how this goes. This problem is made by me a few years ago.


Nice that someone has the correct condition and proving that it is sufficient. To prove that it is necessary, you can

Notice that you can fix what lock-key pairs that you will try before the start (Why?) and then you should prove for all valid lists of lock-key pairs, there exists a lock-key pairing such that none of the attempts are correct.

$\endgroup$

3 Answers 3

7
$\begingroup$

The exact condition is

$a+b>n$.

Actually, something slightly stronger is true: A strategy is winning if and only if

there is some collection of $k$ keys and $\ell$ locks, satisfying $k+\ell>n$, that are tested in all combinations. (As then $k\geq b$ and $\ell\geq a$, it is clear that such a collection can exist if and only if $a+b>n$.) In particular, this will show that the strategy suggested by Florian F (with $k=b$, $\ell=a$) is not only optimal but actually a necessary part of any winning strategy!

We can prove this equivalence by an application of

Hall's Marriage Theorem.

Suppose we are handed any strategy.

As there is no nontrivial information gain throughout the game, the strategy can reasonably be considered as a list $S$ of pairs of keys and locks to be tested that is fixed from the outset. To this strategy, we associate the graph $G_S$ that has all keys and locks as its $2n$ vertices and contains an edge between a key and a lock if these are not tested by the strategy.

Now, observe that

a perfect matching in $G_S$ is exactly the same thing as an association of keys to locks that evades the strategy $S$. Hence, the strategy $S$ is winning if and only if $G_S$ does not have a perfect matching. By HMT, this is the case if and only if there is some subset $A$ of $k$ keys (wlog) that has altogether fewer than $k$ neighbouring locks. Now, a lock is neighbouring $A$ if and only if it is not tested against every key in $A$. Hence, the complement of the neighbourhood in the locks is exactly the set of locks that are tested by all the keys in $A$. But this now is exactly our condition above $-$ since the neighbourhood has size less than $k$, the complement will have size $\ell$ greater than $n-k$. Thus, a violating set for HMT is exactly the same thing as such a collection, which shows the claim.

$\endgroup$
1
  • 1
    $\begingroup$ Nice work applying HMT! Necessity is the hardest part of this puzzle, and I like your proof of necessity better, so I will give the checkmark to you. $\endgroup$ Commented May 27 at 12:11
11
$\begingroup$

I believe the condition is:

$a+b > n$

This condition is sufficient.

Choose $a$ locks and $b$ keys and try all combinations. If no lock opens, that means the $b$ keys belong to the $n-a$ remaining locks. But that is impossible because $b > n-a$.

Is this condition necessary?

I think it is also necessary, i.e. if $a+b \le n$ then there is always a possibility of "using up" all locks and keys without finding a match. But I have trouble finding a convincing argument. The only justification is that the strategy above (choose a key and b locks) seems to be the best but has the possibility to fail when $a+b = n$ or less.

$\endgroup$
2
  • $\begingroup$ Oops... You are obviously right. Thanks for the correction. I fixed the answer. $\endgroup$
    – Florian F
    Commented May 26 at 19:18
  • $\begingroup$ Hi you may want to look at the hint I posted $\endgroup$ Commented May 27 at 0:01
4
$\begingroup$

I thought of it in terms of a

directed graph. Suppose the locks and keys are both numbered $1, \ldots, n$, but that key 3 doesn't necessarily open lock 3. Every time you try a key in a lock and it doesn't work, you can draw a red directed edge (or arrow) on the graph. For example, if you try key 3 in lock 6, you draw a directed edge from node 3 to node 6. Because of the durability requirement, we know the out-degree (number of edges coming out of a node) of the red edges is at most $a$, and the in-degree is at most $b$.

Suppose

$a + b \leq n$. We'd like to show that, no matter what keys and locks we've tried so far (red edges), that there is some assignment of keys to locks (green edges) that misses all the red edges. The green edges form a permutation, and thus we can think of the green edges a forming a bunch of directed cycles that cover all the nodes in the graph.

Can this always be done?

We will build up the cycles one node at a time. Consider a node $v$. If $x \to y \to z \to x$ is an already established green cycle, then we could potentially add $v$ anywhere in that cycle. For example, if $y \to v \to z$ are two edges that are not red, then we could create the cycle $x \to y \to v \to z \to x$, and we would have incorporated $v$ into the green cycles. However, if we can't add $v$ here, that means either $y \to v$ or $v \to z$ is red. If we can't add $v$ to this cycle at all, we see ($x \to v$ or $v \to y$) and ($y \to v$ or $v \to z$) and ($z \to v$ or $v \to x$) are red. These are six seperate edges, so that means at least three edges incident to v are red. This is the same for every cycle in our list so far. If $w$ is just another node not in a cycle, then we can see that either ($v \to w$ or $w \to v$) is red, so we get another red edge from $w$. We also must have $v \to v$ is red, and this actually counts twice. So that means $v$ must be involved in $n+1$ red edges, but this is impossible if $a + b \leq n$. Therefore, there is a way to incorporate $v$ into the decomposition of cycles, and thus one by one we can incorporate all the nodes. That means there is some way the locks and keys could be paired up so that they avoid everything that we guessed so far, proving that Florian F's condition is necessary.

$\endgroup$
1
  • $\begingroup$ Your solution kinda seems correct but I am not sure (lazy to verify details), and I like the other proof of necessity better (it is cleaner, and is my solution also). $\endgroup$ Commented May 27 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.