Jump to content
BrainDen.com - Brain Teasers
  • 0

Traffic Jams


BMAD
 Share

Question

You have N cars that are all traveling the same direction on an infinitely long one-lane highway. Unfortunately, they are all going different speeds, and cannot pass each other. Eventually the cars will clump up in one or more traffic jams.
In terms of N, what is the expected number of clumps of cars?
Link to comment
Share on other sites

9 answers to this question

Recommended Posts

  • 0

Without loss of generality, we may assume that the speeds for N


cars are the numbers from 1 to N inclusive. Their distribution
along the highway corresponds to a permutation of these N numbers.
Consider all x-long cycles of all of these permutations. These can
be put in 1-1 correspondence to x-long jams (pick your favorite
way to do this). Now, we want to average over all permutations,
which is the same thing as adding up all cycle lengths (jam lengths)
of all permutations and dividing by N!. I remembered, from my
youth, that the sum of all cycle lengths of the permutations of
N objects is given by the unsigned sterling numbers of the first
kind, which are recursively given by f(n+1)=(n+1)f(n)+n!. Now,
dividing this by (n+1)! to get the average for f(n+1), we get
g(n+1)=g(n)+1/(n+1), where g(m)=f(m)/m!. Since g(1)=1, we have
the required result that g(N)=1+1/2+1/3+1/4+...+1/N. I have stood
on the shoulders of others in that the stirling number thing has
been used, but not understood, by me.
Link to comment
Share on other sites

  • 0

I find that answer surprising if true.

Let A be the slowest car in the group. Since every car behind A will eventually catch up to A and be stuck behind it, there will be one traffic jam with A and all subsequent cars, and howevermany traffic jams involving the cars in front of A. If there are M cars in front of A then there can be no more than M+1 traffic jams, and that's only in the special case where every car in front of A is traveling slower than the car in front of it (if you count a single unimpeded car to be a traffic jam). In general there will be less than M+1. So if car A is randomly distributed among the pack, M will on average be about N/2 and the total number of traffic jams should be less than that.

Link to comment
Share on other sites

  • 0

Without loss of generality, we may assume that the speeds for N

cars are the numbers from 1 to N inclusive. Their distribution

along the highway corresponds to a permutation of these N numbers.

Consider all x-long cycles of all of these permutations. These can

be put in 1-1 correspondence to x-long jams (pick your favorite

way to do this). Now, we want to average over all permutations,

which is the same thing as adding up all cycle lengths (jam lengths)

of all permutations and dividing by N!. I remembered, from my

youth, that the sum of all cycle lengths of the permutations of

N objects is given by the unsigned sterling numbers of the first

kind, which are recursively given by f(n+1)=(n+1)f(n)+n!. Now,

dividing this by (n+1)! to get the average for f(n+1), we get

g(n+1)=g(n)+1/(n+1), where g(m)=f(m)/m!. Since g(1)=1, we have

the required result that g(N)=1+1/2+1/3+1/4+...+1/N. I have stood

on the shoulders of others in that the stirling number thing has

been used, but not understood, by me.

I sensed a log2(n) dependence, which is precisely the partial sums of the harmonic series. My post 5 answer was a clumsy straight-line fit to a semi log plot of simulated numbers. I got the intercept wrong and missed the formula thereby (slope obviously should have been unity.) When you posted your answer I wrote out the permutations for 1 2 3 and 4 cars and counted from the right, marking the smallest of the remaining numbers, and got 1/1, 3/2, 11/6 and 25/12 for those cases. I programmed the process for p random strings of up to 100,000 numbers to verify the result for larger numbers. Then I looked up the harmonic series for closed forms and found log2(n) sandwiched between the nth and (n+1)st partial sum of 1/n, confirming my log2 suspicions. I saw Stirling there also, but out of a sense of self protection kept my distance. ;)

e.g. for n=3, cars moving to the left, numbers are speeds, red numbers are "lead" cars of a clump:

1 2 3 1

1 3 2 1

2 1 3 2

2 3 1 2

3 1 2 2

3 2 1 3

--

11/6 = 1/1 + 1/2 + 1/3 = (6+3+2)/6

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...