I have few questions:a. does your P(C,n) include case of P(C,n-1), if it does, as n tends to infinity, P(C,n) is approaching 1, obviously, with infinite purchases, you can be quite sure you can collect all C cards. Thus summing P(C,n) for all n from 0 to infinity is infinity!
b. to find the average of n, the formula should be Sum[n * P(C,n)]. On Wed, Sep 16, 2009 at 11:10 PM, George Prekas <[email protected]> wrote: > > I took another approach into solving this problem. > 1. Let function P(x,n) that gives the probability of having exactly x > unique cards after exactly n purchases. > 2. We know that P(0,0) = 1 and P(x != 0,0) = 0. > 3. We know that P(x,n) = Sum[P(i,n-1)*T(i,x),{i,0,x}], where T(x,y) is > as described in the contest's analysis: "Let's call T(x,y) the > probability of ending up with y different cards after opening a new > pack [and having initially x unique cards]." In other words the > probability of having x cards after n purchases depends on the sum of > probabilities of having i cards after n-1 purchases times the > probability of going from i unique cards to x unique cards with 1 > purchase. > 4. With the above recursive equation we can compute P(C,n) for every > n. > 5. Now the answer to our problem is the expected value of P(C,n), that > is Sum[P(C,n),{n,0,Infinity}]. > 6. We can compute this series until it stops changing. > > This may be not as clean and slick as the solution in the analysis, > but it still works. > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
