The case of the missing ingredients

Suppose you are in the kitchen and are looking for two misplaced ingredients. You know that they are somewhere inside a bank of 10 10 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 10 10 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 a b \dfrac{a}{b} , where a a and b b are positive coprime integers, then enter a + b a + b as your answer.

Clarifications:

  • It is possible that both ingredients are in the same drawer.
  • You remember which drawers you've opened, so won't open the same one twice.
  • Once you open a drawer with the ingredient(s) inside you will subsequently have found the ingredient(s).


The answer is 163.

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.

3 solutions

Abhishek Sinha
Nov 23, 2014

Let X 1 X_1 be the number of drawers needed to be opened for locating the ingredient 1. Define X 2 X_2 similarly for ingredient 2. Note that X 1 X_1 and X 2 X_2 are independent. Define Z = max { X 1 , X 2 } Z=\max\{X_1,X_2\} . We require E Z \mathbb{E}Z .

Now, note that for any 1 n 10 1\leq n \leq 10 P ( Z n ) = P ( X 1 n and X 2 n ) = P ( X 1 n ) P ( X 2 n ) = ( n 10 ) 2 \mathbb{P}(Z\leq n)=\mathbb{P}(X_1\leq n \hspace{2pt}\text{and} \hspace{2pt}X_2\leq n )=\mathbb{P}(X_1\leq n)\mathbb{P}(X_2\leq n) = \big(\frac{n}{10}\big)^2 Where we have used the independence property of X 1 X_1 and X 2 X_2 . Hence, P ( Z = n ) = P ( Z n ) P ( Z n 1 ) = 2 n 1 100 \mathbb{P}(Z=n)= \mathbb{P}(Z\leq n)- \mathbb{P}(Z\leq n-1)=\frac{2n-1}{100} Thus, E Z = n = 1 10 n P ( Z = n ) = 1 100 n = 1 10 ( 2 n 1 ) n = 143 20 \mathbb{E}Z=\sum_{n=1}^{10}n\mathbb{P}(Z=n)=\frac{1}{100}\sum_{n=1}^{10}(2n-1)n=\frac{143}{20}\hspace{1pt}\blacksquare

Adit Mohan
Nov 13, 2014

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 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 n^{2} /100 - ( n 1 ) 2 {(n-1)}^{2} /100. = (2n-1)/100.
multiplying probabilties with number of drawers opened and summing we have.
1/100 i = 1 10 \sum_{i=1}^{10} (k(2k-1))=143/20.


There is a probability of 1 10 \frac{1}{10} 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 10 k = 1 10 k = 1 10 10 11 2 = 11 2 \dfrac{1}{10} \displaystyle\sum_{k=1}^{10} k = \dfrac{1}{10} * \dfrac{10*11}{2} = \dfrac{11}{2} .

There is a probability of 9 10 \frac{9}{10} that the two ingredients are in separate drawers. There are ( 10 2 ) = 45 \binom{10}{2} = 45 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

1 45 k = 1 9 k ( k + 1 ) = 330 45 = 22 3 \dfrac{1}{45} \displaystyle\sum_{k=1}^{9} k(k + 1) = \dfrac{330}{45} = \dfrac{22}{3} .

(Explanation: there are 9 9 pairs where the second ingredient is in the tenth drawer opened, 8 8 pairs where the second ingredient is in the ninth drawer opened, and in general k k pairs where the second ingredient is in the ( k + 1 ) (k + 1) st drawer opened for 1 k 9 1 \le k \le 9 .)

Thus the expected number of drawers that you will have to open in general is

( 1 10 ) ( 11 2 ) + ( 9 10 ) ( 22 3 ) = 11 + 132 20 = 143 20 (\dfrac{1}{10})(\dfrac{11}{2}) + (\dfrac{9}{10})(\dfrac{22}{3}) = \dfrac{11 + 132}{20} = \dfrac{143}{20} .

Thus a + b = 143 + 20 = 163 a + b = 143 + 20 = \boxed{163} .

EDIT: A simpler approach would be to note that for 1 k 10 1 \le k \le 10 there are 2 k 1 2k - 1 pairings of drawers where drawer k k is the last one opened, where the pairings are considered distinct if, for example, ingredients A , B A,B are in drawers 2 , 5 2,5 , respectively, as opposed to ingredients A , B A,B being in drawers 5 , 2 5,2 , respectively. Since there are k = 1 10 ( 2 k 1 ) = 100 \sum_{k=1}^{10} (2k - 1) = 100 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 100 k = 1 10 k ( 2 k 1 ) = \dfrac{1}{100} \displaystyle\sum_{k=1}^{10} k*(2k - 1) =

1 100 ( 2 k = 1 10 k 2 k = 1 10 k ) = 1 100 ( 2 10 11 21 6 10 11 2 ) = 715 100 = 143 20 \dfrac{1}{100} * \displaystyle (2*\sum_{k=1}^{10} k^{2} - \sum_{k=1}^{10} k) = \dfrac{1}{100} \displaystyle (2*\dfrac{10*11*21}{6} - \dfrac{10*11}{2}) = \dfrac{715}{100} = \dfrac{143}{20}

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.

Hungry Cap - 6 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...