Second-Fastest Horse with Limited Race Tracks

Brain Teaser · Hard · Free problem

You have

000$ horses and want to rank their speeds, but you can only race them in heats. Each race uses one of $5$ identical tracks and can run at most $5$ horses at a time (one per lane), giving you only their relative finishing order within that heat -- no times. There is no other way to compare horses.

What is the minimum number of races needed to identify the second-fastest horse among all

000$?

Hints

  1. Reduce it to the famous 25-horses problem: with $5$ lanes and only relative orderings, first race disjoint groups, then race the group winners.
  2. After you know the fastest horse $H$, the only horses that can be second are those that lost exclusively to $H$ -- anyone who lost to a non-champion is out by transitivity.
  3. Track every horse that finished directly behind $H$ in a race $H$ actually ran; with $5$ lanes there are at most $5$ such contenders, so one final heat decides second place.

Worked Solution

How to Think About It: This is the classic 25-horses puzzle scaled up. The structure is the same regardless of the herd size: you can only compare $5$ horses per race and you learn only their order. The trick is that finding the single fastest is cheap, but finding the runner-up requires reasoning about which horses could still possibly be second once you know the champion. The candidates for second place are sharply limited by transitivity: a horse that already lost to two others cannot be second.

Approach: Race in groups to get a champion, then assemble the short list of genuine contenders for second.

Formal Solution: With

000$ horses and $5$ lanes:

  1. Round 1 -- group races. Partition into
00$ groups of $5$ and race each: 00$ races. Record each group's internal ranking.
  1. Find the overall fastest. The fastest horse is the winner of some group, so it is among the 00$ group winners. We must race those 00$ winners. With $5$ lanes, ranking enough to find the top of 00$ horses takes a knockout: race $40$ heats of the 00$ winners ($40$ races), then the $40$ heat-winners need $8$ races, then those $8$ winners need $ races, then the $ winners plus a tiebreak need more races. To simply *find the fastest* of 00$ via single-elimination on group-winners costs $\lceil 200/5 \rceil + \lceil 40/5 \rceil + \lceil 8/5 \rceil + \lceil 2/5 \rceil = 40 + 8 + 2 + 1 = 51$ races. Call the champion $H$.
  1. Short-list for second place. Only horses that have lost *only* to $H* can be second. Tracing the elimination bracket and $H
    s original group, the contenders are: the horse that finished second to $H$ in each race $H$ ran. $H$ ran in its original group of $5$ (one direct runner-up) plus the $4$ elimination heats it won (one runner-up each), giving at most
    + 4 = 5$ direct contenders -- exactly $5$ horses.
  1. Final race. Race those (up to) $5$ contenders in one heat:
    $ race. The winner is the second-fastest overall.

Total: 00 + 51 + 1 = 252$ races.

Answer: 52$ races suffice (and are necessary under single-elimination structure): 00$ to rank initial groups, $51$ to determine the overall fastest among the 00$ winners, and

$ final race among the at-most-$5$ horses that lost only to the champion.

Intuition

The whole family of these puzzles hinges on one idea: with only ordinal (relative) information, you cannot compare horses that never met, so you must engineer enough overlapping comparisons. Finding the maximum is the easy part -- it falls out of any tournament. The subtlety is the runner-up: candidates are exactly the horses defeated only by the eventual champion, which the elimination structure caps at the lane count. That bounding-the-candidates move is the reusable insight, and it generalizes to finding the $k$-th element with limited comparators.

In quant interviews this tests whether you can manage information you do not have (no times, only order) and reason about comparison budgets -- the same mindset as selection algorithms and tournament-based median finding. The common mistake is to over-race trying to fully sort, when you only ever need to fully order the tiny contender set. The exact race count depends on the assumed scheme; the structure (group, champion, contender heat) is what interviewers want to hear.

Open the full interactive solver →