How Many Brackets Can You Bust?

Riddler Classic

From Lucas Fagan comes a buster of brains and brackets that’s just in time for March Madness:

Consider a single-elimination tournament with four teams that hold a definitive ranking — that is, one team is the best, another team is second-best and so on. In each game, the better team wins. When the tournament is complete, you know for certain which team is the best. However, you can’t make similar claims about the remaining teams.

Suppose the winning team is A, and it plays B in the first round. Meanwhile, the team that loses in the final is C, whose opponent in the first round is D. With this bracket, there are three possible rankings of teams from best to worst: A/B/C/D, A/C/B/D and A/C/D/B.

For this week’s puzzle, instead of four teams, consider a single-elimination tournament with eight teams. How many possible rankings of teams are possible for a given completed bracket?

Extra credit: Instead of eight teams, suppose there are 2^N teams. In terms of N, how many possible rankings of teams are possible for a given completed bracket?

Solution

N = 1

If there are two teams, there is only one way the teams can be ranked.

$$R(1) = 1$$

N = 2

If there are four teams, two $N = 1$ brackets come together before the final match.

Since one player is the clear winner, the loser to the winner in the first round can be ranked in any spot between the two teams from the other bracket.

$$R(2) = \dfrac{3!}{1!2!} \cdot R(1) \cdot R(1) = 3$$

Answer

N = 3

If there are eight teams, two $N = 2$ brackets come together before the final match.

Since one player is the clear winner, the three losers from the winner's bracket can be ranked in any spot between the four losers from the other bracket.

$$R(3) = \dfrac{7!}{3!4!} \cdot R(2) \cdot R(2) = 35 \cdot 3 \cdot 3 = 315$$

Extra Credit

I will use induction to show that:

$$R(k) = \dfrac{(2^k-1)!}{2^{2^k-k-1}}$$

$k = 1$:

$$R(1) = \dfrac{(2^1-1)!}{2^{2^1-1-1}} = \dfrac{1}{1} = 1$$

$k = N-1$:

Assume

$$R(N-1) = \dfrac{(2^{N-1}-1)!}{2^{2^{N-1}-(N-1)-1}} = \dfrac{(2^{N-1}-1)!}{2^{2^{N-1}-N}}$$

$k = N$:

From above, if there are $2^N$ teams, two $2^{N-1}$ brackets come together before the final match.

Since one player is the clear winner, the $2^{N-1}-1$ losers from the winner's bracket can be ranked in any spot between the $2^{N-1}$ losers from the other bracket.
$$R(N) = \dfrac{(2^{N}-1)!}{(2^{N-1}-1)!(2^{N-1})!} \cdot \big(R(N-1)\big)^2$$
$$ = \dfrac{(2^{N}-1)!}{(2^{N-1}-1)!(2^{N-1})!} \cdot \dfrac{(2^{N-1}-1)!}{2^{2^{N-1}-N}} \cdot \dfrac{(2^{N-1}-1)!}{2^{2^{N-1}-N}}$$
$$ = \dfrac{(2^{N}-1)!}{2^{N-1} \cdot 2^{2^{N-1}-N} \cdot2^{2^{N-1}-N}}$$
$$ = \dfrac{(2^N-1)!}{2^{2^N-N-1}}$$

Rohan Lewis

2023.03.06