Can You Survive March Madness?

In a $16$-team region seeded $1$ to $16$ in the usual single-elimination bracket, measure a team’s strength of schedule by the geometric mean of the strongest opponents it could face in each of the four rounds, where “strongest” means the lowest-numbered seed that the bracket could send its way (assuming better seeds win). Which two seeds have the toughest strength of schedule?

The Fiddler, Zach Wissner-Gross, March 22, 2024(original post)

Solution

A tough schedule means meeting low-numbered seeds, so we want the seed whose four strongest possible opponents are as small as possible all at once. Two facts about the standard bracket pin those opponents down. First, assuming the better seed always wins, the strongest team a given seed can meet in round $r$ is the lowest seed sitting in the sibling block of size $2^{r-1}$ that feeds the same game. Second, as the rounds advance each block sends its best team forward, so the round-$r$ opponents available across the whole region are exactly the seeds $1,2,\dots,16/2^{r-1}$, one drawn from each surviving block.

For the $16$-team region the four rounds have block sizes $1,2,4,8$, so every seed’s strongest opponents are its first-round partner, then the best of the adjacent pair, the adjacent four, and the adjacent eight. The last of these is always seed $1$ or $2$ (the two halves of the draw), and the best-of-four is one of $1,2,3,4$; the room to choose lies in the early rounds. A top seed wastes its early games on weak opponents (seed $1$ opens against seed $16$), so its geometric mean is dragged up. The middle of the list is treated worst: seed $11$ is routed into the best-of-each-block at every stage, meeting seeds $6,3,2,1$, and its mirror image seed $14$ meets $3,6,2,1$. Both give $$\sqrt[4]{6\cdot3\cdot2\cdot1}=\sqrt[4]{36}=\sqrt6\approx2.449,$$ and sweeping all sixteen seeds shows no seed does worse. So the toughest two are the $$\boxed{11\text{ and }14\text{ seeds},}$$ each with strength of schedule $\sqrt6$.

The computation

To confirm that no seed beats $11$ or $14$, build the actual bracket and, for each seed, read off the lowest seed reachable in each round directly from the seeding order, then take the geometric mean. The minimum over all sixteen seeds is $\sqrt6$, at seeds $11$ and $14$.

import math
def bracket(n):                                    # standard seeding order
    s = [1]
    while len(s) < n:
        m = len(s) * 2; s = [x for p in s for x in (p, m + 1 - p)]
    return s
def schedule(n):
    order = bracket(n); pos = {s: i for i, s in enumerate(order)}
    out = {}
    for s in range(1, n + 1):
        i = pos[s]; opps = []
        for r in range(int(math.log2(n))):
            blk = 1 << r; start = ((i // blk) ^ 1) * blk
            opps.append(min(order[start:start + blk]))   # strongest reachable in round r+1
        out[s] = math.prod(opps) ** (1 / len(opps))
    return out
sc = schedule(16)
print(sorted(sc, key=sc.get)[:2], round(min(sc.values()), 3))   # [11, 14] 2.449

Extra Credit

With $2N$ seeds and $N$ very large, the two toughest seeds approach fixed fractions of $2N$. What are they?

Solution

The same principle scales: the toughest seed is the one steered into the strongest available opponent in every round. Label a seed by the binary digits of its position in the draw. Reading the bracket from the coarsest split inward, each binary digit decides whether that round’s game pairs the seed against the stronger or the weaker side of the relevant block. To meet a low seed in every round, the digits must keep choosing the stronger side, which means they must alternate: a run of equal digits would hand the seed an easy round. Exactly two positions down the list have an alternating binary expansion, $$0.101010\ldots_2=\tfrac23\qquad\text{and}\qquad 0.110101\ldots_2=\tfrac56,$$ so the two toughest seeds approach $$\boxed{\tfrac23\,(2N)\quad\text{and}\quad\tfrac56\,(2N),}$$ two-thirds and five-sixths of the way down the seed list. A full proof of the limit is more than the puzzle needs; the alternating-digit structure is the reason, and the computation below confirms the two fractions.

The computation

Running the bracket of the previous section for growing $2N$ and reading off the two toughest seeds, their positions in the list converge to $0.6667$ and $0.8333$, that is $\tfrac23$ and $\tfrac56$.

for n in (1024, 16384, 65536):
    sc = schedule(n); a, b = sorted(sc, key=sc.get)[:2]
    print(n, round(a / n, 4), round(b / n, 4))     # -> 0.6667, 0.8333