Problem: Clusters of Cars

The following problem popped into my head this morning on the one hour drive home to Gympie from Rainbow Beach.

In the oncoming traffic, cars often appeared in clusters. Indeed, if there is one car that is going more slowly than the others, then they are all pretty much stuck behind it (unless they overtake).

The problem I’m thinking of is this: what is the expected number of cars in each cluster?

Like most problems that just pop into my head, this one has likely been thought of and solved many years ago. It’s also not very well-formed. So let’s develop a simpler statement and have a think about it.

Problem. Consider 100 cars all of which are travelling along a road in a randomly chosen order. At first, the cars are all travelling at distinct speeds as they are spaced out enough. Over time, however, some of the cars will catch up to slower ones and will also have faster cars catch up to them. When this happens, the faster car that comes up the back must slow down.

Once the cars have all settled into their clusters, how many of these clusters do we expect there to be?

I have not really thought about this yet. I would love a solution in the comments or even a link to a place this has been solved before.

My first go-to is to scale down the problem and just consider 10 cars all travelling at different speeds $(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)$ . Now, if I place these randomly on a road, it could look like this:

$5, 9, 2, 4, 7, 6, 10, 8, 1, 3$

Let’s suppose these cars are heading from left to right. Then actually, the rightmost car (speed = 3) will do it’s own thing because the car behind it is the slowest (speed = 1) and so everyone will get trapped behind it. In this case there will be two clusters.

For another example, I get:

$2, 7, 5, 1, 3, 6, 9, 8, 10, 4$

For simplicity, I will use car $N$ to mean the car travelling at speed $N$ , Thinking through the above, car 4 is going to have 4 cars trapped behind it all of them stuck travelling at the speed of 4. Then car 3 will be all by itself in a trivial cluster of 1 car. Then car 1 will be at the front of the final remaining cluster.

I feel like there is some realisation I have to make here but I am not yet making it. If somebody could make it for me, that would be lovely! And if they could generalise it to $N$ cars then I would be very happy.

One comment