3
$\begingroup$

There are 9 types of Red Noses, for comic relief this year:

9 red noses

Each one is sold in an opaque packet, so it is lucky dip which one you will get.

Assuming there is the same amount of each type (${1\over9}$th). On average, how many bags would need to be bought for someone to get all 9 of them?

$\endgroup$
9
  • $\begingroup$ Good question! The probability of none of your $n$ bags containing a particular nose (say Nose A) is $(8/9)^n$; the probability of missing any of A, B, $\ldots,$ I is almost $9$ times this (you need to take into account the tiny risk of missing two of them, etc.) Time forbids my taking out a spreadsheet and finding the exact answer, though... $\endgroup$
    – HTFB
    Mar 13, 2015 at 17:12
  • 4
    $\begingroup$ Look up the Coupon Collector's Problem. $\endgroup$
    – David K
    Mar 13, 2015 at 17:14
  • 2
    $\begingroup$ I was intending to mark this as a duplicate as soon as I found a question that asked (essentially) the same problem before; but in the questions I found, nobody actually posts the answer, they just refer you to other sites. So +1 for the question since it actually encouraged someone to post a real answer. $\endgroup$
    – David K
    Mar 13, 2015 at 17:53
  • 1
    $\begingroup$ @David: How about this question? $\endgroup$
    – hmakholm left over Monica
    Mar 13, 2015 at 19:38
  • 1
    $\begingroup$ @HenningMakholm Yes, that qualifies as "a real answer." Nice job finding it. (And the coupon-collector tag is suddenly getting assigned to a lot more questions!) $\endgroup$
    – David K
    Mar 13, 2015 at 19:52

2 Answers 2

Reset to default
7
$\begingroup$

I'm going assume that there are, effectively, infinite bags of noses—if we only had 9 bags... well, you get it. ;)

Say we have $n-1$ of the $9$ unique noses. The probability of getting a new style of nose on the next bag is $p_n = 1 - \frac{n-1}{9}$. Then, on average, it takes $\frac{1}{p_n}$ bags to get the next unique nose. (i.e. - Say we have $0$ unique noses. Then, $n = 1$ and $p_n = 1 - \frac{0}{1} = 1$ and it will take only one bag to get a new nose. Similarly, if we have $4$ nose-styles, $n = 5$ and it will take $1 - \frac{4}{9} = \frac{9}{5}$ bags to get a $5^{\text{th}}$ nose.)

The probabilities here are independant. That is, the chance of getting the $5^{\text{th}}$ new nose on the next bag doesn't depend on the chance of getting the $4^{\text{th}}$ one (once you have the $4^{\text{th}}$ nose, the probability of getting the $5^{\text{th}}$ will always be $\frac{1}{p_5}$). Thus, we can just sum the average of each $p_n$ until $n = 9$.

So, we have: $$\frac{1}{p_1} + \frac{1}{p_2} + \frac{1}{p_3} + \frac{1}{p_4} + \frac{1}{p_5} + \frac{1}{p_6} + \frac{1}{p_7} + \frac{1}{p_8} + \frac{1}{p_9} + = \\ 1 + \frac{9}{8} + \frac{9}{7} + \frac{9}{6} + \frac{9}{5} + \frac{9}{4} + \frac{9}{3} + \frac{9}{2} + \frac{9}{1} = \\ 9 \sum_{n=1}^{9} \frac{1}{n} = \frac{9 \times 7129}{2520} = 25.46$$

That is, on average, it'd take about 25 bags to get all nine noses.

$\endgroup$
0
3
$\begingroup$

The trick to this problem is that the first few bags almost certainly are mostly different noses.

With absolute certainty, you only need to buy one bag to have one type of nose in your collection. To collect two types of noses, you need to buy at least two bags, but there is a probability $\frac89$ that you only need to buy two bags. The expected number of bags you have to buy in order to acquire the second type of nose, after you already have one type of nose, is $\frac98$.

The expected number of bags you have to buy to get the next type of nose only gets to be more than $2$ when you already have most of the noses. When you get to $7$ types of nose, you have a $\frac29$ chance to get a new kind of nose with each bag you buy, so the expected number of bags to get from $7$ types of nose to $8$ types of nose is $4.5$. After that the expected number of bags required to find the last type of nose is $9$ bags.

Add up $1 + \frac98 + \frac97 + \frac96 + \frac95 + \frac94 + \frac93 + \frac92 + 9$ and see what you get.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .