Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the coupon collectors problem, there are $n$ unique coupons and each cereal box has 1 coupon only. I would like to modify the problem such that there are $m$ boxes of cereal in total and each box has $c_i (1 \le c_i \le n)$ number of coupons.

Then how many boxes of cereal do I need to buy to have $n$ unique coupons?

share|improve this question
    
Are all the coupons in a given box guaranteed to be different? If not, you need enough boxes to have the number of coupons in the standard problem. If yes, I don't think there will be a nice solution for unspecified $c_i$ –  Ross Millikan Aug 6 '12 at 23:25
    
As per Ross Millikan, there are not enough details in the question. Furthermore, I don't understand how the parameter $m$ affects the problem, since it will not factor in the solution to your problem. –  Jérémie Aug 7 '12 at 0:31
    
@RossMillikan No, it is not guaranteed to be different. I don't understand what "enough boxes" means. Could you explain more? –  Myungcheol Doo Aug 7 '12 at 15:41
    
In the standard problem, you expect to need about $n \log n$ coupons to have a complete set. If each box just contains random coupons (drawn with replacement), you still need that many, so keep buying boxes until you have that many. –  Ross Millikan Aug 7 '12 at 16:11
    
@RossMillikan Thanks a lot for explanation! –  Myungcheol Doo Aug 7 '12 at 18:14

1 Answer 1

Since the coupons within a box are not guaranteed to be different, basically we are just buying boxes in batches of $c_i$.

As in the original coupon problem, we expect to have to buy $n \log n$ original boxes to make for a complete set of $n$ unique coupons. So if each new box contains $c$ coupons, we expect to need to buy $\dfrac{n \log n}c$.

However, without any specification on how the $c_i$ are distributed for the new boxes we cannot make an estimate of the number of boxes we need to buy in the new situation.

Let us tackle the general situation where each box has the same probability distribution, say chance $p_i$ to contain $i$ boxes, $1 \le i \le n$. Then each box is expected to contain $$E = \sum_{i=1}^n ip_i$$ coupons. It follows that we expect to have to buy $$\frac{n \log n}E$$ boxes to complete a set.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.