Suppose there are N types of surprise mystery toys uniformly distributed in cereal boxes. How many boxes would a kid have to buy to collect them all on average?
Now suppose there are M kids efficiently trading. How many boxes sold before all kids have all toys?
Conversation
Expectation is linear, so it's the sum from i = 1 to n of the expected number of boxes you need to open to get something you don't already have given that you have i things already.
def f(n: Int) = (1 to n).map(i => 1.0 * n / i).sum
Seems to check out experimentally too
1
4
This is ugly but it works:
gist.github.com/jliszka/4ea988
It just does it by counting. It involves an infinite series that converges pretty quickly, so you can cut it off to get your desired level of accuracy.
1
3


