Probabilities and Free Toys, Part 1

Once upon a time, a long time ago, my high-school maths teacher set an extension problem: I never got chance to tackle it, and I've never tried to since.  I've remembered it through the years, as a friend of mine was able to solve it elegantly, and I never saw his answer.  So, it's time for some closure again.


Here's the question:  


A certain breakfast cereal manufacturer is giving away a free toy inside each pack.  There are ten toys in the series, and I'd like to collect them all.  However, I can't tell which toy I'm going to get when I buy the pack.  The original question was:  what's the probability of getting all ten toys after opening ten packs?  And the follow-up question I'd like to look at is:  assuming that each toy is distributed equally, how many packs would I have to buy to be 50%, 70% or 90% sure of having all ten toys?

Now, bearing in mind that this is a high-school maths problem, it shouldn't take any advanced maths to solve the first question.  The follow-up question is one of my own, and could take me anywhere.


So, let's look at the first question, and let's start with two toys and build up to ten.


After buying two packs, the probability of success is 0.5.  The two successful combinations are AB and BA, and the two unsuccessful are AA and BB (i.e. I get the same toy twice).  But let's look at that as a step-by-step process.  When I buy the first pack, I am certain of getting a toy I haven't got before.  There are two alternatives, A and B, and two successes (either of them).  So the probability is 2/2.  The probability of getting a successful toy with my second pack is 1/2.  There's now only one successful toy (the one I haven't got), but there are two toys available.  To calculate the probability of getting the first toy and the second toy in two packs is 1/2 x 2/2 = 1/2.


This can be expanded to three toys, A, B and C:
Probability of success with first pack is 3/3  (any of the toys is a success)
Probability of success with the second pack is 2/3 (I need to avoid getting a duplicate, so there are now only two successes.  If I have A, then I only need B or C).
Probability of success with the third pack is 1/3 (I now need one specific toy as I have the other two).


So, the probability of success after three packs = 3/3 x 2/3 x 1/3 = 6/27 = 2/9 = 22%


I'll do the case for four toys, before moving to a general expression:
p(success with first pack) = 4/4 as any of the four toys is a success
p(success with second pack) = 3/4 as I already have one toy, and need one of the other three
p(success with third pack) = 2/4 as I have two toys and only two are now successes
p(success with fourth pack) = 1/4 as I only need one of the four toys to complete my set.


So, probability of success with four toys and four packs =
4/4 x 3/4 x 2/4 x 1/4 = 24/256 = 3/32 = 9.375%


There's a clear pattern developing.  For five toys, the numerators will be 5, 4, 3, 2, 1 and the denominators will be 5, 5, 5, 5, 5.  The numerators are multiplied together, 5x4x3x2x1 which is called 5 factorial, and written 5! while the denominators are 5x5x5x5x5 which is 5^5.  Looking back, the same rule applies to four toys, three toys and two toys, and will apply going upwards.


So, the probability of getting all n toys with n packs is n! / n^n


n! is an expression that increases very quickly with n (1, 2, 6, 24, 120, 720, 5040 and so on) but the denominator n^n increases even more quickly (1, 4, 27, 256, 3125, 46656 and so on).  The table below shows n, n!, n^n and the ratio n! / n^n which is the probability of getting n toys with n packs.  For the original question - what's the probability of getting 10 toys in 10 packs, the answer is 10! / 10^10 which is 0.036% (less than one in a thousand).


Next time, I'll look at the harder question:  with 10 toys (or a number larger than three or four), how many packs do I have to buy to be 50%, 70% or 90% sure of having the full set?