A trading card series has 200 different cards in it, which are sold in 5-card packages.

Each package has a random sampling of the cards (assume that any card of the 200 has an equal chance of being in a package).

On the average, how many packages will need to be bought to collect the complete series if...

A: all the cards in a package will always be different

B: a package can have repeats

(In reply to a method of solving problem A by Steve Hutton)

Steve Hutton’s method is basically valid. A couple of corrections are (1) the denominator is not dependent on the number of unique cards already chosen nor on how many are to be added this packet, as there are always 200 choices for the first card of a packet, 199 for the second, etc., so the x comes out of the denominator formula, and (2) what is given as f(0,x) through f(5,x) are really f(5,x) through f(0,x), as the p(s,n) = sum {i=0 to 5} of f(i,n-i)*p(s-1,n-i) requires for example that f(0,n-0) represent the probability of adding no new unique holdings, that is that all the cards in the coming packet are already held, which is the formula with the x (x-1)… in it rather than the (200-x), etc. Also, (3) as in Steve’s method for problem B, the p(s,200) being cumulative, has to have the preceding p(s-1,200) subtracted before multiplying by s to add into the expected value.

Given this, a Basic program implementing the corrected algorithm provides an answer agreeing with my previously posted analytic solution for problem A using inclusion and exclusion, with 120-digit precision using UBASIC. This algorithm of course eliminates the need for the extra precision (and therefore UBASIC) as the totals never get above 1. The answer, as computed by this and the previous analytic solution, is 233.1581452….

This, together with the previous verification via Steve Hutton's algorithm for B of that part's inclusion/exclusion solution, of 235.5212379..., completes the agreement of two different methods for each part.

Posted by Charlie on 2003-02-06 09:01:32