Can You Survive March Madness?

While the first part is fairly straightforward to do by hand, I thought it'd be easier to program everything, as I was going to utilize it for the extra credit :)

The first step is to determine seeding relative to position in the bracket. For a tournament with $N$ rounds, there are $2^N$ seeded teams. For $N=1$, it is seed 1 vs. seed 2. Afterwards, we pit seed 1 against seed 4, and we pit seed 2 against seed 3. Essentially, when we double the number of teams, we increase the round count ($N$) by 1. To determine their matchup, we pit them, in an earlier round, against an existing seeded team such that the sum of their seeds is equal to $2^N+1$. It's a unique fractal pattern that can determined recursively.

So for a 16-player bracket, the lineup would be 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11, where adjacently listed seeds face off against each other. The strength is always determined by the stronger team in the next round, so we can define a recursive function like so:

from functools import cache


@cache
def strength_prod(seed: int, rounds: int) -> int:
    if rounds == 0:
        return 1
    opponent = 2**rounds + 1 - seed
    return opponent * strength_prod(min(seed, opponent), rounds - 1)

If there are no rounds left, we multiply against the identity (1). Otherwise, we calculate our opponent for this round, and we multiply their seed by the strength of the matchup in subsequent rounds. Note that we use @functools.cache to cache our results (dynamic programming). Also note that using a simple product is sufficient in place of finding the geometric mean here since we are only interested in relative strengths (this helps us keep everything in integers).

Finding the toughest schedule strength for a 4-round bracket can be achieved by:

for seed in range(1, 17):
    print(seed, strength_prod(seed, 4))

Output:

1 1024
2 315
3 168
4 130
5 96
6 66
7 60
8 72
9 64
10 42
11 36
12 40
13 40
14 36
15 42
16 64

Seeds 11 and 14 have it the roughest, bearing a geometric mean of $36^{1/4}\approx2.4495$.

Continuing to the extra credit, while I wasn't sure how to derive a strict mathematical limit, I was able to view the data in larger brackets (this loop shows data up to $N=16$):

for rounds in range(1, 17):
    num_seeds = 2**rounds
    min_strength = min(strength_prod(i, rounds) for i in range(1, num_seeds + 1))
    ans_seeds = [
        seed
        for seed in range(1, num_seeds + 1)
        if strength_prod(seed, rounds) == min_strength
    ]
    print(rounds, [seed / num_seeds for seed in ans_seeds])

Output:

1 [1.0]
2 [0.75, 1.0]
3 [0.75, 0.875]
4 [0.6875, 0.875]
5 [0.6875, 0.84375]
6 [0.671875, 0.84375]
7 [0.671875, 0.8359375]
8 [0.66796875, 0.8359375]
9 [0.66796875, 0.833984375]
10 [0.6669921875, 0.833984375]
11 [0.6669921875, 0.83349609375]
12 [0.666748046875, 0.83349609375]
13 [0.666748046875, 0.8333740234375]
14 [0.66668701171875, 0.8333740234375]
15 [0.66668701171875, 0.833343505859375]
16 [0.6666717529296875, 0.833343505859375]

The tuple listed here is the pair of fractions we're interested in, each representing the respective seed's proportion to the number of total teams. They clearly trend towards $\frac{2}{3}$ and $\frac{5}{6}$, so those will have to be my answers. Looking forward to see if there's a more rigid mathematical approach to this!

Final Answers

This Week's Fiddler: 11 and 14

Extra Credit: 2/3 and 5/6