You have a bunch of n keys of which only one one opens the door of a storeroom, You wish to get into the storeroom. You choose one key at random and try it. If it does not work, you discard and try another key at random from the remaining keys. You proceed in this way until you open the door. Find the probability that you will open the door in the (i) 1st attempt, (ii) 2nd attempt, (iii) 3rd attempt. What do you think the probability will be for the kth attempt, where 4 ≤ k ≤ n? Can you justify it?

My answers were: (i) $\frac{1}{n}$

(ii) $\frac{1}{n-1}$


and for the kth attempt: $\frac{1}{n-k-1}$

However, it is given that the probability for the kth attempt is just $\frac{1}{n}$. why is that so?

Appreciate any help!

  • $\begingroup$ Please explain how you arrive at 1/(n-1) as the answer to (ii). $\endgroup$ – Did Nov 15 '14 at 11:34
  • $\begingroup$ Your pattern would have suggested $\dfrac{1}{n-(k-1)}=\dfrac{1}{n-k+1}$ for the $k$th attempt, though this is in fact a conditional probability $\endgroup$ – Henry Nov 15 '14 at 11:36
  • $\begingroup$ How would you then relate this to the Monty Hall problem? $\endgroup$ – hypergeometric Nov 15 '14 at 12:03

Before trying them out give each key a different number in $\{1,\dots,n\}$. The key with e.g. number $2$ will be tried out at the second attempt. The probability that the right key gets number $k$ (corresponding with $k$-th attempt) is: $$\frac{1}{n}$$ So this is the probability that door will be opened at the $k$-th attempt.


The probability you open on the second attempt is the probability you fail to open on the first attempt multiplied by the conditional probability you succeed on the second, i.e. $$\frac{n-1}{n} \times \frac{1}{n-1}=\frac{1}{n}$$ and this pattern continues, so by induction the probability you open on the $k$th attempt is the probability you fail to open on the first $k-1$ attempts multiplied by the conditional probability you succeed on the $k$th, i.e. $$\frac{n-k+1}{n} \times \frac{1}{n-k+1}=\frac{1}{n}.$$

A simpler approach is to order the keys at random at the beginning. The key which opens the lock has a probability of $\frac1n$ of being in each position.

  • $\begingroup$ Problem for us humans is that we find it hard to see things from the perspective of a key. I think that plays a part when it comes to the simpler approach. We jump immediately in the shoes of the person that tries to open the door. But it is more effective to personalize with the key. $\endgroup$ – drhab Nov 15 '14 at 11:32
  • 1
    $\begingroup$ @drhab: Or with the lock. ‘Hm. Today I think that I’ll open for the — rolls n-sided die — third key.’ $\endgroup$ – Brian M. Scott Nov 15 '14 at 16:32

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.