Can You Beat the Heats?

There are $25$ sprinters with a fixed but unknown speed ranking, and five run in each heat, the heat revealing only their relative order. You want to identify, with certainty, the first, second, and third fastest overall. What is the fewest heats that always suffices?

The Fiddler, Zach Wissner-Gross, May 3, 2024(original post)

Solution

Run five heats so that every sprinter races once, then a sixth heat among the five heat-winners. Order those winners $W_1>W_2>W_3>W_4>W_5$ by the sixth race. The overall fastest is $W_1$: everyone else lost to their own heat-winner, who at best placed behind $W_1$.

Now prune the field for second and third. Anyone in the heats of $W_4$ or $W_5$ sits behind a sprinter who is already only fourth-fastest among the winners, so they cannot reach the top three. In $W_1$’s heat the second and third finishers $A_2,A_3$ are still alive; in $W_2$’s heat only the runner-up $B_2$ is; and $W_2,W_3$ themselves remain. That leaves exactly five live candidates, $W_2,W_3,A_2,A_3,B_2$, and a seventh heat among them delivers second and third outright. Fewer than seven cannot guarantee it (the first five heats are forced if everyone is to race, and one race among the winners cannot separate the next two places), so the answer is $$\boxed{7}$$ heats. This is the familiar “$25$ horses, five tracks, find the top three”.

The computation

Encode the procedure and stress it: assign a random true ranking, run the five heats, the winners’ heat, and the seventh heat among the five survivors, and check the three it names are really the fastest three. It is correct every time.

import numpy as np
rng = np.random.default_rng(0)
def find_top3():
    rank = rng.permutation(25)          # rank[s] = true speed rank of sprinter s (0 fastest)
    sprinters = list(range(25)); rng.shuffle(sprinters)
    heats = [sorted(sprinters[5*i:5*i+5], key=lambda s: rank[s]) for i in range(5)]
    order = sorted(range(5), key=lambda i: rank[heats[i][0]])   # heats by winner speed
    h1, h2, h3 = heats[order[0]], heats[order[1]], heats[order[2]]
    W1 = h1[0]
    cands = [h2[0], h3[0], h1[1], h1[2], h2[1]]                  # five survivors
    cands.sort(key=lambda s: rank[s])
    pred = [W1, cands[0], cands[1]]
    return pred == [list(rank).index(r) for r in (0, 1, 2)]
print(all(find_top3() for _ in range(200_000)))    # True

Extra Credit

At another meet there are six sprinters racing strictly head-to-head, two at a time. What is the fewest races that guarantees the complete fastest-to-slowest order?

Solution

A head-to-head race is one comparison, so finding the full order is exactly sorting six items by comparisons. Each comparison has two outcomes, so $r$ comparisons can distinguish at most $2^r$ orderings; to tell apart all $6!=720$ possible rankings needs $2^r\ge720$, that is $r\ge\lceil\log_2 720\rceil=10$. Ten is also achievable, by the Ford–Johnson merge-insertion ordering, so $$\boxed{10}$$ races always suffice and are sometimes necessary.

The computation

The lower bound comes straight from the count of orderings each comparison can resolve.

import math
print(math.ceil(math.log2(math.factorial(6))))     # 10  (met by merge insertion)