BrainDen.com - Brain Teasers
• 0

# Traffic jams

## Question

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 by bonanova
change to 1024 cars

## Recommended Posts

• 1

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.

##### Share on other sites

• 1

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?

##### Share on other sites

• 0

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

##### Share on other sites

• 0

@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 nth 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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.