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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.