1
$\begingroup$

Let's say we have $n$ keys and $k$ locks on a door, with $n \ge k$. The $n$ keys are different, i.e. only $1$ key goes into a specific lock. Also every lock has a key that goes to it (but some of the keys may be "duds"). What is the probability of unlockin gthe door on the $M$th attempt?

If we had $n$ keys and $1$ lock then obviously the probability to unlock on $M$-th attempt would be $\frac1n$, but now we have more locks.

So let's say we have $11$ keys and $2$ locks, what the probability that while we unlock we use up $3$ keys that are bad?

Is it $\frac1{11}\cdot\frac1{11}$ because we try the key on both doors before discarding it? If it doesn't unlock any door we don't use it again.

What if we have more locks?

$\endgroup$
  • $\begingroup$ Clarification: "only $1$ key goes into $k$ locks": Does this mean that there are $n-k$ keys that don't go into any locks, and each of the remaining $k$ keys goes into one of the $k$ locks? $\endgroup$ – Brian Tung Feb 22 '17 at 23:43
  • $\begingroup$ Do you mean "there is one particular key which opens one specific lock" or instead "each key opens its particular partner lock"? $\endgroup$ – David G. Stork Feb 22 '17 at 23:46
  • $\begingroup$ Edited. 1 key to 1 lock, my bad $\endgroup$ – CyprusN Feb 22 '17 at 23:48
  • $\begingroup$ Define an "attempt", and define "unlock". Do you meant to define the first key in the first lock is the first attempt? Also, are we to assume that all locks are locked to start with? The algorithm needs to be defined. Do you try all keys in one lock and then proceed to the next lock, or one key in all locks? The 2nd algorithm would on average solve the problem faster. $\endgroup$ – user334732 Feb 23 '17 at 19:53
1
$\begingroup$

Throughout I'm assuming that you meant one key goes into at most 1 lock, not $k$ as otherwise your answer is still $\frac{1}{n}$.

Lay out the order that you use your keys in. There are $n!$ ways of doing this. You want the probability that we open the door of the $a$-th try for some $k\leq a\leq n$. How many permutations of yours would achieve this? You need to count all permutations with $k-1$ good keys in the first $a-1$ slots and a good key in the $a$-th slot. You can do this in $k\left(\begin{array}{c} n-k \\ a-k\end{array}\right)(k-1)!(a-k)!\left(\begin{array}{c} a-1 \\ k-1 \end{array}\right)(n-a)!=k\frac{(n-k)!(a-1)!}{(a-k)!}$ ways, where the first two terms coming from deciding which $k-1$ and $a-k$ keys from the good and bad pile should be in the first $a-1$ slots, the third and fourth gives the total number of ways to arrange them individually, the fifth is the number of ways to position each group, and the final term the number of ways to arrange the leftover bad keys afterwards, making the probability of this happening $k\frac{(n-k)!(a-1)!}{(a-k)!n!}$, again only for $k\leq a\leq n$.

$\endgroup$
0
$\begingroup$

Note: I think the question may be defining "attempt" as trying the key on a single lock. In this answer, I took "attempt" to be trying one key (on every lock).

The question is: if there are $n$ keys and $k$ locks, and a random ordering of the $n$ keys, what is the probability that the locks are all unlocked in $m$ steps, where $k \le m \le n$?

Overall, we randomly choose $k$ of the $n$ keys to be the correct ones, and this can be done in $\binom{n}{k}$ ways. The question is then the probability that the last correct key is the $m$th one. The number of ways to do that is $\binom{m-1}{k-1}$, since we have to choose which of the $m-1$ first keys are the $k-1$ remaining correct ones.

Therefore the answer is $$ \frac{\binom{m-1}{k-1}}{\binom{n}{k}} = \frac{(m-1)! \cdot (n-k)! \cdot k}{(m-k)! \cdot n!}. $$ Note the special cases:

  • When $k = 1$, this gives ${(n-1)!}/{n!} = 1/n$, which is what you computed.

  • When $m = k$, this gives $1 / \binom{n}{k}$, because the correct keys must all come at the front.

  • When $n = k$, this gives $1$ if $m = n$, $0$ otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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