Suppose that you have a key ring with N keys, exactly one of which is your house

Question

Suppose that you have a key ring with N keys, exactly one of which is your house key. Further suppose that you get home after dark and can't see the keys on the key ring. You randomly try one key at a time until you get the correct key, being careful not to mix the keys you have already tried with the ones you haven't. a) Use counting techniques to determine the probability that you get the correct key on the n^th try, where n is an integer between 1 and N inclusive. b) Solve part a) without doing any computations. c) Determine the probability that you get the correct key on or before the n^th try by using (i) direct counting and (ii) your result from part a) and the additivity measure.

Explanation / Answer

This is a case of drawing sample without replacement. Each time a wrong key is drawn out, the remaining sample space size decreases by 1.

If the correct key is drawn on the nth attempt, this means that n-1 wrong keys had been drawn out before that. So the remaining sample space size when drawing the nth key is equal to N-(n-1) = N-n+1.

The probability of drawing a wrong key on 1st try is (N-1)/N, on 2nd try is (N-2)/(N-1), and on (n-1)th try is (N-n+1)/(N-n+2). So,
P(drawing the correct key on nth try) = (N-1)/N * (N-2)/(N-1) * (N-3)/(N-2) ... * (N-n+1)/(N-n+2) * 1/(N-n+1) = 1/N

This could also have been without any computation, by using the information that since there is only 1 correct key and total keys are N, so the probability of drawing that key is simply 1/N, because n can take any value between 0 and N, which means that the correct key could be present at any poisition and all the possible ordering of keys are equally likely.

So probability of drawing the correct key on nth try is the same and equal to 1/N, whether n takes any of the values between 1 and N.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.