Traffic jams

[bonanova]

At 5-second intervals, 1024 automobiles enter a straight (and otherwise empty) single-lane highway traveling at initial speeds chosen at random from the interval [50, 70] miles per hour. Cars may not pass nor collide with other cars. When a slower car is encountered, a car must simply reduce its speed, and for the purposes of this puzzle we may consider the cars in such a case become permanently attached, traveling at the slower car's speed.

Eventually there will be N clusters of cars. What is the expected value of N? (Equivalently, what is the expected cluster size?)

Edited February 17, 2018 by bonanova
change to 1024 cars

[plainglazed]

okay, not too proud to start this off with some probably way simplistic maths:

Spoiler

six or seven clusters.  if you can have a fraction of a cluster would guess 6 5/9.

Think the time and speed intervals are red herrings.  Once the slowest car enters the highway all other vehicles will line up behind/cluster with it, eventually.  The slowest cars expected position would be 50.  Then the same scenario repeats so the second slowest expected at 25; then 12 1/2, 6 1/4, 3 1/8, 1 5/9.  But can you have a fraction of a car thus six or seven or on average 6 5/9?

 

[bonanova]

plainglazed suggests an analysis amenable to powers of 2. I'll amend the OP to make it 1024 cars instead of 100 cars.

[plasmid]

This might count as an ah-hah if it's true.

Spoiler

The first car out on the road will of course be the first car in its cluster.
The second car will be the first car of its cluster if and only if it’s going slower than the first car, which will happen with probability 1/2.
The third car will be the first car of its cluster if and only if it’s going slower than both the first car and the second car, which will happen with probability 1/3.
The nth car will be the first car of its cluster with probability 1/n.

And the number of clusters is, of course, equal to the number of first cars in a cluster.
So the expected number of clusters (if I’m understanding the meaning of expected values correctly, which I might not be) is Sum _n=1-1024 (1/n) which is a tad over 7.5.

[bonanova]

@plainglazed (first) and @plasmid (with a formula) both have it.
Both posts show how to get the answer, with the formula garnering "best answer" designation. Nice job both.

Spoiler

plainglazed's construction of successively halving the group implies logarithmic dependence on n, while plasmid produces the n^th partial sum of the harmonic series. These differ only by the addition of the Euler constant (.577...). Because that's so close to 1/2 it may just represent the dilemma of whether or not, in plainglazed's method, to halve the final car.

Answers given in the posts differ, because I changed n from 100 to 1024 at one point.