I’ve noticed a few Grade 6 math problems on Facebook that I’m sure Einstein would be embarrassed to see his picture on. I’m not sure which is sadder, that people consider a problem given to 11-year olds genius-level, or that only 50% of adults got the answer right.

I’m much more interested in the problems that FiveThirtyEight has been posting for their Riddler series. This week the problem involves cars getting stuck in traffic. Thankfully, not something I normally have to deal with, but I think I figured out the answer.

The Problem:

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

My solution:

f(N) <- average number of car groups if there are N cars
f(0) = 0
f(1) = 1

If we have 2 cars there is 50% chance of the first car being faster, which would create 2 groups; and 50% chance of the 2nd car being faster and merging into a single group.
f(2) = 0.5 * 2 + 0.5 * 1 = 1.5

More generally, if we just consider the first 2 cars. There’s a 50% chance of there being a solo lead car plus the groups that form behind it, and a 50% chance of the first car merging into the group behind it. We can define the average number of cars recursively, where:
f(N) = 0.5 * (1 + f(N-1)) + 0.5 * f(N-1)

that equation reduces to:
f(N) = 0.5 + f(N-1)

testing it out:
f(2) = 0.5 + f(1) = 1.5
f(3) = 0.5 + f(2) = 2
f(4) = 0.5 + f(3) = 2.5
…

Which is an arithmetic series that can be reduced to:
f(N) = 0.5 + 0.5 * N

or more succinctly:
f(N) = 0.5 * (N + 1) (for N >= 1)
f(N) = 0 (for N < 1)