This time, having solved the easier question, let's take a 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?
Once again, let's start with two toys (start small!):
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).
After buying three packs, the probability of success rises to 6/8, which is 0.75 or 75%.
There are eight total combinations (from AAA, AAB through to BBA and BBB), but only two are unsuccessful (AAA and BBB are unsuccessful), leaving six successful combinations.
After buying four packs, the probability of success rises to 7/8. There are 16 total combinations, but the number of unsuccessful combinations remains at two, and the number of successful combinations rises to 14.
Generally, for the two-toy problem, the probability of getting a successful combination after t turns is equal to (2^t - 2) / 2^t or, in words, the total number of combinations minus unsuccessful, divided by the total number of combinations.
This, however, is where it gets tricky. With three toys and three packs, there are just six successful combinations (the exact permutations, in alphabetical order, are ABC, ACB, BAC, BCA, CAB and CBA) and 27 total combinations (which confirms what I proved above for the three toys and three packs case). With three toys and four packs, the number of successes rises to 36, and the total number combinations is 81. The success probability is 36/81 which is 4/9, coincidentally double the probability after three packs. After five packs, the number of combinations rises to 243.
Looking at the number of combinations I've seen so far, for the three-toy problem, it's risen from 9 to 81 to 243, rising by a factor of 3 each time, and n=3, the number of toys squared. In fact the denominator, the total number of permutations, is simply n^t (number of toys raised to the power of the number of turns or packs). This is also known as the formula for 'permutations with repitition'.
Now I need to identify the number of successful permutations - those that contain one of each of the toys.
For n=3 toys and t=3 turns, there are 6 successful permutations (as listed above).
For n=3 toys and t=4 turns, there are 36 successful permutations
Now, the question becomes - how many will there be after five turns?
Let's go back to four turns and look closely at each of the permutations we have. We have the 36 successful ones, ABCA, ABCB, AABC and so on. For these 36 successes, it doesn't matter what we pick next, we'll still have a successful combination; there are three options for each of these, so that's 36x3=108 successes for each of them.
There are also the 3 combinations AAAA, BBBB and CCCC which will not produce a success, irrespective of what we pick next, so that's 3x3=9 fails.
This leaves the rest, which logically must contain two different toys. We've covered the ones which already contain three different toys, and we've looked at the ones which contain only one toy. Since there were 81 combinations in total after four goes, there must be 81-(36+9) = 36 combinations which contain two different toys. There is a probability of 1/3 of the next choice being the correct one, which equals 36 x 1/3 = 12.
So, after five turns, we have 108 + 12 = 120 successful permutations.
Let's review:
After three turns: 6 successful permutations
After four turns: 36 successful permutations
After five turns: 120 successful permutations
Let's take a look at six turns, based on the process we used for five turns.
After five turns, we have 120 successes which will each yield three more successes, so 3x120 = 360
We also still have the combinations which have just one toy in - AAAAA, BBBBB and CCCCC, and these will each produce three more unsuccessful combinations, irrespective of the next choice. 3x3=9 unsuccessful combinations.
There are 3^5 total combinations after five turns, 243 in total, which means that we have 243-(120+9) = 114 other combinations which have two toys. A third of these will become successful with the sixth turn, which is 114/3 = 38.
So, after six turns, we have 360 + 38 = 398 successful permutations. I've deduced the formula for working out successful permutations in an iterative manner, but I don't have the computing power to determine the 10th, 15th or 115th term without knowing each one before. Furthermore, this method won't easily expand to cover five, six, or ten toys. It's all about knowing how many successes you've had previously, and how many certainly won't become successful (because they have n-2 different toys and will require at least two more goes to become successful).
Three toys is an easy case - you either have a successful combination, a combination with only one toy repeated, or a two-toy combination with a 1/3 chance of becoming successful. With four toys, you may already have one, two or three different toys, or be successful, and I don't quite see how to sort all that out.
So, next time, it's on to spreadsheet modelling. I'm going to write a macro that simulates buying the cereal packets and examining the toys, and determining whether or not the combination is a success. If maths fails, use sampling!
No comments:
Post a Comment