So this week’s Riddler caused me a bit of trouble, even though I got
the a right answer pretty quickly. It’s not that I was wrong; it’s that my answer was so convoluted when there is such a better way to say it. Here’s what I wrote:
Average number of packs A(n) is equal to: Num(n) / Denom(n) where:
Num(1) = 1, Denom(1) = 1.
Num(n) = Num(n – 1) * n + Denom(n – 1).
Denom(n) = Denom(n – 1) * n. (this is n-factorial).
But here’s the much better way to say that:
Average number of packs for n cars = 1 + 1/2 + 1/3 + 1/4 + 1/5 … + 1/n.
This is, as pointed out by Alex Mahdavi, a Harmonic Series. Commenter Abe then offered a pretty good explanation for why this is the right answer.
Start adding cars slowest to fastest.
For car k there are k places to place the new car, only one of which will add a new group: adding at the front. Otherwise you’re putting it behind a slower car and it will join that car’s group.
Groups(n) = Groups(n – 1) * (n – 1)/n + (Groups(n -1) + 1)/n — the number of groups from before times the chance it isn’t at the fron, and one more than last time, times the chances it is at the front.
This reduces to:
Groups(n) = Groups(n-1) + 1/n, which is the harmonic series.
Thanks Abe! That does make it easier. If I know how many packs I have with N cars, and I add one more car, then there’s N+1 possible speeds for that car, and a 1/N+1 chance that that car will form a new pack. Makes sense.
Anyway, all that code I wrote before is really unnecessary now. You can find the answer very quickly:
Note: this would be a good candidate for memoization, but I didn’t bother.
And some output:
So, I was technically correct with my long, terrible explanation, but the better answer was very simple. The original code I wrote to find the answer was helpful however. Without it, I probably wouldn’t have ever gotten to even the answer I got, much less the harmonic series.