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.

Upper and Lower Bound

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~...~(n-2)~~(n-1)~~(n)]\,\! \)

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~..~(n-2)~~(n-3)~~(n)~~(n-1)]\,\! \)

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~...~(n-1)~~(n-2)~~(n)]\,\! \)

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

Lots and Lots of LaTeX

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) = 0\) 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\,\! \)

The Punch Line

All that is to say->

\( E(n)=\gamma+\psi_0(n+1)-1\,\! \)

where, as listed by Wolfram, "\(\gamma\) is the Euler-Mascheroni constant and \(\psi_0(x)\) is the digamma function."

The last part, of course, makes me think there is a much easier way of thinking about this problem...

The Much Easier Way of Thinking About This Problem

Turns out, this problem and several like it are on the Puzzles page of the XKCD Wiki. And the Discussion page for Puzzles has...discussions...about the solutions. The problem above attracted quite a bit of attention. And the easier way - or really - much much better way - of thinking about the problem came from a user named Evan, who wrote

I think I've found the easiest way to prove the harmonic series result. In the 1/n of the arrangements of n cars in which the last car is the slowest, it falls behind, so the number of clumps is the same as if the last car were not there. In the other (n-1)/n arrangements, the last car is part of a clump containing the slowest car and zero or more other cars. If there are other cars in the clump, it would exist without the final car. Thus the presence of the last car creates a clump only in the 1/(n-1) of these arrangements in which the clump consists of the last car and the slowest car. So a clump is added in ((n-1)/n)(1/(n-1)) = 1/n of the possible arrangements, and E(n) = E(n-1) + 1/n. Since E(1) = 0 we have E(n) = 1/2 + 1/3 + 1/4 + ... + 1/n for n>1. -- Evan

which I paraphrased as

Ohhhh - that's good. The only way adding a new car to the end will form a new clump is if (a) the new car is not the slowest and (b) the penultimate car was the slowest of the n-1 cars. As an aside - how does XKCDB not have math tags? DukeEgr93

Since Pundit does have math tags, I can re-write the above as saying

\( E(n)=E(n-1)+\left(\frac{n-1}{n}\right)\left(\frac{1}{n-1}\right)=E(n-1)+\frac{1}{n} \)

Meaning I could get rid of all the LaTeX stuff above, but why would I?

External Links

• XKCD Wiki
• XKCD Comic