1

Suppose we have $n$ keys. We try each key at random to open a door. If we $\bf discard$ the ones that don't work, what is the probability that we open the door in the kth try? What if we dont discard the previously tried keys?

$$\bf \underline{Attempt \; to \; the \; solution}$$

We can call $E_i$ to be event that the ith key opens the door. Clearly, since we have $n$ keys $P(E_i) = \frac{1}{n}$. Here is where I am having trouble trying to express our outcome in terms of events $E_i$. I feel like the answer is just $P(E_k) = \frac{1}{n}$ but perhaps the phrasing of the problem is confusing.

Now, if we dont discard. Suppose we put first key into door. there are $n-1$ possible ways that it wont work cause $1$ of them is the one that works.same holds for the second and third and so forth until we get to the $k-1$th case. The next case the one that opens the door can be done in 1 way of course. Thus,

$$ P = \frac{(n-1)^{k-1} }{n} $$

Is this a correct approach?

James
  • 3,997

3 Answers3

2

Almost, but you are on the right track.

Let's define the event $E= \{ \text{the $k$-th key opens the door }\}.$

  • If we discard the keys that don't work: then we have that $$P(E_k) = \frac{n-1}{n}\cdot \frac{n-2}{n-1} \cdots \frac{n-k}{n-k+1}\cdot \frac{1}{n-k}=\frac{1}{n}.$$ Look at it this way: we require that all attempts to open the door will fail until we reach the $k$-th key. Since we are assuming only one key opens the door, the probability of failure in the first trial is $\frac{n-1}{n}.$ Then we discard that key since it doesn't work, leaving us with $n-1$ keys. Now for the second attempt to fail we have $\frac{n-2}{n-1}$ probability. And so on, until the $k$-th attempt, where we now want to succeed with probability $\frac{1}{n-k}$. Notice that almost all terms cancel each other out and end up with $\frac{1}{n}$.

  • If we don't discard the keys that don't work: then we have that $$P(E_k)=\underbrace{\frac{n-1}{n}\cdot \frac{n-1}{n} \cdots \frac{n-1}{n}}_{k-1 \text{ times}}\cdot \frac{1}{n}= \left( \frac{n-1}{n}\right)^{k-1} \cdot \frac{1}{n}= \left(1-\frac{1}{n}\right)^{k-1} \cdot \frac{1}{n}$$ since we want to fail on the first $k-1$ attempts and succeed on the $k-$th attempt. Since we are not discarding the keys this time, every time we have that same probability $\frac{n-1}{n}$ to fail and always have the probability $\frac{1}{n}$ to succeed.

Bergson
  • 1,647
0

First of all, I gather you are assuming that exactly one of the keys opens the door. You should always state all your assumptions.

When you discard the keys, the probability that the first key opens it it $\frac{1}{n}.$ The probability that the second key opens it is $$\frac{n-1}{n}\cdot\frac{1}{n-1}=\frac{1}{n}$$

The probability that the second key opens it is $$\frac{n-1}{n}\cdot\frac{n-2}{n-1}\cdot\frac{1}{n-2}=\frac{1}{n}$$ and so on.

When the keys aren't discarded, your mistake is not using probabilities. The probability that the door doesn't open is $\frac{n-1}{n}$, so the answer is $$\frac{(n-1)^{k-1}}{n^k}$$ Alternatively, you could just divide by the number of ways to choose $k$ keys.

saulspatz
  • 53,131
0

I'd suggest looking here.

Your solution to the first part $\left(\frac{1}{n}\right)$ is correct. The second part is slightly off.

Joseph Eck
  • 649