How Many Cars Will Get Stuck In Traffic?

Welcome to The Riddler. Every week, I offer up a problem related to the things we hold dear around here — math, logic and probability. These problems, puzzles and riddles come from lots of top-notch puzzle folks around the world, including you, the readers. You’ll find this week’s puzzle below.

Mull it over on your commute, dissect it on your lunch break, and argue about it with your friends and lovers. When you’re ready, submit your answer using the form at the bottom. I’ll reveal the solution next week, and a correct submission (chosen at random) will earn a shoutout in this column. Important small print: To be eligible for the shoutout, I need to receive your correct answer before 11:59 p.m. EST on Sunday — have a great weekend!

Before we get to the new puzzle, let’s return to last week’s. Congratulations to 👏 John B. Schmidt 👏 of Atlanta, our big winner. You can find a solution to the previous Riddler at the bottom of this post.

Now, here’s this week’s Riddler, which comes to us from Django Wexler, a fantasy novelist from Seattle. He first encountered it after his friend was asked a version of it as part of a job interview.

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be N groups — no car ever gets stuck behind a slower car.

Extra credit: It’s time to offer up another 🏆 Coolest Riddler Extension Award 🏆. Spice up this mathematical roadtrip problem for your fellow readers. Alter the road, add a lane, enact some traffic laws, or something far more creative than I can think of. Submit a description and analysis in the form below, or shoot me a link to your work on Twitter. We’ll publish a winner next week.

Need a hint? You can try asking me nicely. Want to submit a puzzle or problem? Email me.

And here’s the solution to last week’s Riddler, concerning the secret election held by a group of politicians (who we’ll call A, B, C, D, and E), which came to us from Laura Feiveson, via Barry Nalebuff, via Thomas Schelling.

In summary: Initially, D will be chosen as the candidate. If A has the flu, he should transfer his vote to E. In that case, A will win. And no, A should not get the flu vaccine.

To get there, work backwards. In Round 4, E will face either A, B, C or D, and the winner will be the candidate. The winners of those potential Round 4 matchups will be A, B, E and D, respectively, per the candidates’ listed preferences. Then move on to Round 3, where D will face either A, B or C. If A wins, A will win the next round, too, and thus the election. Ditto B. But if C wins in Round 3, we know E will win in Round 4. In other words, a vote for C in Round 3 is a vote for E as the ultimate nominee. The winner of Round 3 is always D. You can keep going like this, tracing through the implications of each round’s voting. The winner, if Candidate A is healthy and voting, will be Candidate D.

But if A gets the flu and can’t vote, he should give his vote to E. If he does so, A himself will become the nominee! By giving his vote to his least preferred opponent, he can clinch the nomination for himself — his most preferred outcome!

Therefore, he should not get the flu vaccine (assuming winning the nomination is worth suffering through an illness, and that he can’t fake sick, etc.). In fact, he should do everything he can to get sick and avoid the vote. As reader Nikko Pomata wrote, “With an opportunity like that, he should probably move all his campaign stops to hospitals and clinics.”

Here’s my artistically indefensible attempt to illustrate the solution:

Zach Wissner-Gross, Friend Of The Riddler (FOTR)™, analyzed a cool generalization of the problem, where each candidate prefers himself first, and then the others randomly. Turns out that puts Candidate E at a big disadvantage.

Before I go, I’d like to shout out to some other Riddler respondents, because you all are the reason I get out of bed each week: shoutout to Höskuldur Pétur Halldórsson for best real name, shoutout to Dub Step Stego for best fake name, shoutout to Eric for listing his hometown as “Home of MLB World Champs,” shoutout to Ben Kester for being from my hometown, and shoutout to Linda Yancey for reminding everyone, “I’m a board-certified infectious-disease physician. Everyone should get the flu shot.”

Have a great weekend, everybody, and be well.

Oliver Roeder is a senior writer for FiveThirtyEight.

Filed under