Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
bonanova

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

Share this post


Link to post
Share on other sites

4 answers to this question

  • 1

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

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×