User:DukeEgr93/Chasing Cars
Kevin Kauffman posted the following on his Facebook page: <quote> I have two problems here, I want to see if anyone comes up with the same answers i did.
1) I have a bunch of cubes with blank sides. I have six colors of paint, how many unique painting combinations can there be using one color per side, with no 2 sides on the same cube having the same color
2) there is an infinite stretch of one lane highway, and as you know if you ever drove on a highway under construction, faster cars bunch up behind slower ones. So, on our infinite stretch we put N cars at random positions on the highway, all traveling at different, but constant speeds, all traveling in the same direction. After a long time, how many 'clumps' of cars are there, where a clump is any group of 2 or more cars? </quote>
What follows is my answer to the second problem.
First, there are bounds on the solution. At "best" for the cars concerned, they can be lined up in decreasing velocity such that the fastest car is first and the slowest car is last. Assuming a car's number is proportional to its velocity, and assuming the cars are going from left to right, this would be:
\( Cars = [1~2~3~4~5~6~7~8~...] \)
This results in no car ever "clumping."
At "worst," of course, the slowest car comes first, in which case all cars line up behind it at some point, for 1 clump. The greatest number of clumps, however, is floor(n/2) - this will happen if the "best" case above sees every set of two cars swapped:
\( Cars = [2~1~4~3~6~5~8~7~...] \)
In this case (with an even number of cars), each "even" car will get stuck behind the next-slowest vehicle - and the group will be going more slowly than the group ahead of it. With an odd number of cars,
\( Cars = [2~1~4~3~6~5~8~7~9~...] \)
has floor(n/2) clumps with one "free" car at the front.
So my first answer was [0 floor(n/2)]. Kevin modified the problem, though, to ask for the expected number of clumps for \(n\) cars, which is decidedly different from the range of clump numbers. So here goes for finding \(E(n)\)...
I started by counting the total number of clumps possible for every arrangement of cars. For 0 cars or 1 car, the answer is obvious - \(E(0) = E(1) = 1\) since there is no way to form a clump. For two cars, I decided to use some new terminology. \(TC(k)\) will be the total number of clumps for \(k\) cars. \(C(k, j)\) will be the average number of clumps for \(k\) cars assuming an arrangement where the slowest car is in the \(j^{th}\) position. With \(n\) cars, there are \(n!\) different possible arrangements for the cars. Also, the probability of the slowest car being in the \(j^{th}\) position is just \(1/n\).
