User:DukeEgr93/Chasing Cars

Kevin Kauffman posted the following on his Facebook page:

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?

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\).

Note that:

\( TC(k)=\sum_{j=1}^{k}C(k, j)~(k-1)!=(k-1)!~\sum_{j=1}^{k}C(k, j)\,\! \)

since there are \((k-1)!\) different arrangements for \(k\) cars once the slowest car is placed in the \(j^{th}\) spot. Also,

\( E(n)=\frac{TC(n)}{n!}=\frac{\sum_{j=1}^{n}C(n, j)}{n}\,\! \)

So - for two cars, the slowest car is either in the first or second position. If it is in first, all other cars pile behind it and there is 1 clump; if it is in second, there are no clumps - and there is a free car in front of it. Basically, this means

\( TC(2)=1!~(C(2,1)+C(2,2)) \,\! \)
\( TC(2)=1!~(1+0)\,\! \)

In general, the average number of clumps for a particular placement of the slowest car will depend on whether the slowest car is last or not. As long as the slowest car is not last, there will always be at least one clump - the one behind the slowest car. The average number of clumps ahead of it will be the expected number of clumps for that number of cars. If the slowest car is last, the average number of clumps ahead of it will be the expected number of clumps for that many cars, and the slowest car will not cause a clump. That means that

\( C(n,k)=1+E(k-1), k\neq n\,\! \)
\( C(n,n)=E(n-1)\,\! \)

and since

\( TC(k)=(k-1)!~\sum_{j=1}^{k}C(k, j)\,\! \)

we can write

\( TC(n)=(n-1)!~\left(\sum_{j=1}^{n}C(n, j)\right) \)
\( TC(n)=(n-1)!~\left(E(n-1)+\sum_{j=1}^{n-1}\left(1+E(j-1)\right)\right)\,\! \)

Or, taking out the \(n-1\) from the 1 term in the summation,

\( TC(n)=(n-1)!~\left(\left(n-1\right)+\sum_{j=1}^{n}\left(E(j-1)\right)\right)\,\! \)

and

\( E(n)=\frac{TC(n)}{n!}=\frac{1}{n}~\left(n-1+\sum_{j=1}^{n}E(j-1)\right)\,\! \)

with

\( E(0)=0\,\! \)

However, note that you can also do the following for \(n\geq2\):

\( E(n-1)=\frac{1}{n-1}~\left(n-2+\sum_{j=1}^{n-1}E(j-1)\right)\,\! \)
\( (n-1)E(n-1)=\left(n-2+\sum_{j=1}^{n-1}E(j-1)\right)\,\! \)
\( (n-1)E(n-1)+1=\left(n-1+\sum_{j=1}^{n-1}E(j-1)\right)\,\! \)
\( (n-1)E(n-1)+1+E(n-1)=\left(n-1+\sum_{j=1}^{n}E(j-1)\right)\,\! \)

For the left side,

\( (n-1)E(n-1)+1+E(n-1)=n~E(n-1)+1\,\! \)

and for the right,

\( \left(n-1+\sum_{j=1}^{n}E(j-1)\right)=n~E(n)\,\! \)

so

\( n~E(n)=n~E(n-1)+1\,\! \)

which yields

\( E(n)=E(n-1)+\frac{1}{n}~,~n\geq2\,\! \)

given

\( E(0)=E(1)=0\,\! \)

meaning

\( E(n)=\sum_{k=2}^{n}\frac{1}{k},~n\geq 2\,\! \)