Suppose you are in the kitchen and are looking for two misplaced ingredients. You know that they are somewhere inside a bank of 1 0 drawers but have no idea which drawer{s} they are in.
Assuming that each ingredient has an equal chance of being in any of the 1 0 drawers, what is the expected number of drawers you will have to open before finding both of the missing ingredients?
If the expected number of drawers is b a , where a and b are positive coprime integers, then enter a + b as your answer.
Clarifications:
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
the probability of finding the ingredients UNTIL (i.e. cumulative, even if you have found both of them you keep opening drawers) the n drawer is
n
2
/100 (n/10 for each ingredient.)
therefore the probability of finding both the ingredients exactly WHEN you open the nth darawer =
n
2
/100 -
(
n
−
1
)
2
/100. = (2n-1)/100.
multiplying probabilties with number of drawers opened and summing we have.
1/100
∑
i
=
1
1
0
(k(2k-1))=143/20.
There is a probability of 1 0 1 that both ingredients end up being in the same drawer. Since you have no idea which drawer this is, it is equally likely that it will be the first, second, third, ..... or tenth drawer you open. The expected number of drawers you will have to open in this case is
1 0 1 k = 1 ∑ 1 0 k = 1 0 1 ∗ 2 1 0 ∗ 1 1 = 2 1 1 .
There is a probability of 1 0 9 that the two ingredients are in separate drawers. There are ( 2 1 0 ) = 4 5 possible pairs of drawers that contain the ingredients, each pair being equally likely to contain the ingredients. (By "pairs of drawers" I mean, for example, the first and third drawers you open, or the fifth and ninth, etc..) Since it is the last of the pair that is opened that will determine the total number of drawers you will have to open, the expected number of drawers you will have to open in this case is
4 5 1 k = 1 ∑ 9 k ( k + 1 ) = 4 5 3 3 0 = 3 2 2 .
(Explanation: there are 9 pairs where the second ingredient is in the tenth drawer opened, 8 pairs where the second ingredient is in the ninth drawer opened, and in general k pairs where the second ingredient is in the ( k + 1 ) st drawer opened for 1 ≤ k ≤ 9 .)
Thus the expected number of drawers that you will have to open in general is
( 1 0 1 ) ( 2 1 1 ) + ( 1 0 9 ) ( 3 2 2 ) = 2 0 1 1 + 1 3 2 = 2 0 1 4 3 .
Thus a + b = 1 4 3 + 2 0 = 1 6 3 .
EDIT: A simpler approach would be to note that for 1 ≤ k ≤ 1 0 there are 2 k − 1 pairings of drawers where drawer k is the last one opened, where the pairings are considered distinct if, for example, ingredients A , B are in drawers 2 , 5 , respectively, as opposed to ingredients A , B being in drawers 5 , 2 , respectively. Since there are ∑ k = 1 1 0 ( 2 k − 1 ) = 1 0 0 such pairings, each of which is equally likely, the expected number of drawers that you will need to open to find both of the missing ingredients is
1 0 0 1 k = 1 ∑ 1 0 k ∗ ( 2 k − 1 ) =
1 0 0 1 ∗ ( 2 ∗ k = 1 ∑ 1 0 k 2 − k = 1 ∑ 1 0 k ) = 1 0 0 1 ( 2 ∗ 6 1 0 ∗ 1 1 ∗ 2 1 − 2 1 0 ∗ 1 1 ) = 1 0 0 7 1 5 = 2 0 1 4 3
as found before.
It is necessary to specify that the two ingredients are distinguishable because if not, the above method yields an answer of 7 instead of the desired 143/20.
Problem Loading...
Note Loading...
Set Loading...
Let X 1 be the number of drawers needed to be opened for locating the ingredient 1. Define X 2 similarly for ingredient 2. Note that X 1 and X 2 are independent. Define Z = max { X 1 , X 2 } . We require E Z .
Now, note that for any 1 ≤ n ≤ 1 0 P ( Z ≤ n ) = P ( X 1 ≤ n and X 2 ≤ n ) = P ( X 1 ≤ n ) P ( X 2 ≤ n ) = ( 1 0 n ) 2 Where we have used the independence property of X 1 and X 2 . Hence, P ( Z = n ) = P ( Z ≤ n ) − P ( Z ≤ n − 1 ) = 1 0 0 2 n − 1 Thus, E Z = n = 1 ∑ 1 0 n P ( Z = n ) = 1 0 0 1 n = 1 ∑ 1 0 ( 2 n − 1 ) n = 2 0 1 4 3 ■