Traffic Jam Harmony

So this week’s Riddler caused me a bit of trouble, even though I got the a right answer pretty quickly. It’s not that I was wrong; it’s that my answer was so convoluted when there is such a better way to say it. Here’s what I wrote:

Average number of packs A(n) is equal to: Num(n) / Denom(n) where:
    Num(1) = 1, Denom(1) = 1.
    Num(n) = Num(n – 1) * n + Denom(n – 1).
    Denom(n) = Denom(n – 1) * n.  (this is n-factorial).

But here’s the much better way to say that:

Average number of packs for n cars = 1 + 1/2 + 1/3 + 1/4 + 1/5 … + 1/n.

This is, as pointed out by Alex Mahdavi, a Harmonic Series. Commenter Abe then offered  a pretty good explanation for why this is the right answer.

Start adding cars slowest to fastest.

For car k there are k places to place the new car, only one of which will add a new group: adding at the front. Otherwise you’re putting it behind a slower car and it will join that car’s group.

So:

Groups(n) = Groups(n – 1) * (n – 1)/n + (Groups(n -1) + 1)/n — the number of groups from before times the chance it isn’t at the fron, and one more than last time, times the chances it is at the front.

This reduces to:

Groups(n) = Groups(n-1) + 1/n, which is the harmonic series.

Thanks Abe! That does make it easier. If I know how many packs I have with N cars, and I add one more car, then there’s N+1 possible speeds for that car, and a 1/N+1 chance that that car will form a new pack. Makes sense.

Anyway, all that code I wrote before is really unnecessary now. You can find the answer very quickly:

void AverageJams(int carCount)
{
    double avg = 0;

    for(int i = 1; i <= carCount; i++)
    {
        avg += 1.0 / (double)i;
    }
    double perN = avg / (double)carCount;
    printf("Average jams for %d cars = %.6f or %.6fn\n", carCount, avg, perN);
}

 

Note: this would be a good candidate for memoization, but I didn’t bother.

And some output:

Average jams for 1 cars = 1.000000 or 1.000000n
Average jams for 2 cars = 1.500000 or 0.750000n
Average jams for 3 cars = 1.833333 or 0.611111n
Average jams for 4 cars = 2.083333 or 0.520833n
Average jams for 5 cars = 2.283333 or 0.456667n
Average jams for 6 cars = 2.450000 or 0.408333n
Average jams for 7 cars = 2.592857 or 0.370408n
Average jams for 8 cars = 2.717857 or 0.339732n
Average jams for 9 cars = 2.828968 or 0.314330n
Average jams for 10 cars = 2.928968 or 0.292897n
Average jams for 11 cars = 3.019877 or 0.274534n
Average jams for 12 cars = 3.103211 or 0.258601n
Average jams for 13 cars = 3.180134 or 0.244626n
Average jams for 14 cars = 3.251562 or 0.232254n
Average jams for 15 cars = 3.318229 or 0.221215n
Average jams for 16 cars = 3.380729 or 0.211296n
Average jams for 17 cars = 3.439553 or 0.202327n
Average jams for 18 cars = 3.495108 or 0.194173n
Average jams for 19 cars = 3.547740 or 0.186723n
Average jams for 20 cars = 3.597740 or 0.179887n
Average jams for 21 cars = 3.645359 or 0.173589n
Average jams for 22 cars = 3.690813 or 0.167764n
Average jams for 23 cars = 3.734292 or 0.162361n
Average jams for 24 cars = 3.775958 or 0.157332n
Average jams for 100 cars = 5.187378 or 0.051874n
Average jams for 10000 cars = 9.787606 or 0.000979n
Average jams for 1000000 cars = 14.392727 or 0.000014n

 

So, I was technically correct with my long, terrible explanation, but the better answer was very simple. The original code I wrote to find the answer was helpful however. Without it, I probably wouldn’t have ever gotten to even the answer I got, much less the harmonic series.

Author: Wiesman

Husband, father, video game developer, liberal, and perpetual Underdog.

4 thoughts on “Traffic Jam Harmony”

  1. Here’s another transport-related riddle for you, one of my own making. It’s based (loosely) on a real question I would ask myself on train journeys: if you really want to get to your destination, do you want the train to slow down or not. Here it is, let me know if you think it’s interesting.

    You are on a non-stop night train journey on the Eurostar from London to Avignon in the South of France. The train leaves London at 9pm, is due to exit the Channel tunnel on the French side after 1 hour, and will arrive in Avignon at 3 a.m.
    You fall asleep just as the train is going into the Channel tunnel and wake up some time later. Your phone has run out of battery so you have no idea of the time, you can see nothing but black out the window, and there is no one else in the train carriage to ask the time. As a cool millennial, you do not wear a watch yourself, although you do carry an old mechanical stop-watch, which you set going after you wake up.
    You have no idea how long you have been asleep. All you know is that you can still feel the train moving.
    You desperately need to pee, but have a horrible phobia about train toilets; your plan was to wait until the train arrived at Avignon before heeding the call of nature.
    According to your stop-watch, three minutes after you wake up, you feel the train slowing down.
    At first you are overjoyed: the train must be coming in to the station! But then you remember that, just before you dozed off, there was an announcement regarding a 10% chance that a track repair job somewhere on the French leg of the journey would not be complete, causing the train to stop for a few minutes.

    You now have mixed emotions.

    Question 1: Should you be optimistic that the train is slowing down because it is coming into Avignon station? Or pessimistic that it is slowing down for the track repairs?

    Question 2: Same scenario as above, except that this time the train is slowing down as you wake up- it was the slowing down which jolted you from your sleep. Should you be pessimistic or optimistic?

    Question 3: Same scenario as 1, but after you wake up, the train doesn’t slow down for ages. As you increasingly need to pee, you wonder if it would be a good thing if the train were to start slowing down, or not. As time passes, is there a point at which your optimism/pessimism switches? If so, when?

    1. Interesting question. Without doing too much analysis my feeling is that I should always be optimistic as there’s only a 10% chance that repairs were necessary, so a 90% chance that the slowing down is because we are approaching the station. Slightly less optimistic in scenario 2, since waking up naturally would seem to indicate that I’ve slept longer, and therefore being jolted from sleep could mean that repairs were necessary.

      Thanks for the question!

Disagree?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s