
March Madness Musings
Hi all,
There are a billion reasons why bracketology is a worthwhile pursuit. Suppose there are n teams entered in the NCAA tournament. I can represent the tournament as the complete binary tree with n leaves; each leaf node represents one team. The internal nodes (those with children) represent individual games. The first order of business is to determine the number of internal nodes. It's easy to see that the height of the tree is $h={\lceil \log_2(n)\rceil}$. Now there are two cases to consider:
1. All of the leaves are at level h; i.e. $n=2^h$ is a power of 2. Then there are $\sum_{i=0}^{h1}2^i=2^h1=n1$ internal nodes.
2. Some of the leaves are at level h  1. Suppose n is odd. Then there is one leaf node with no sibling; i.e. in the first round one team has no opponent. There are various ways to remedy this. One way is to count a "phantom" game where there is only the one team involved. The second way is to give some team a "bye" in the first round. The Wimbledon tennis tournament did this for a long time by having the previous year's champion play only in the championship match. By 1922, though, the English came to their senses and realized the fair way to do things is to start with an even number of players. But I digress; back to the problem. So assume that n is even. Then every internal node has exactly two children Suppose there are k internal nodes at level h  1. Then there are $2^{h1}k$ leaves at level h  1 and 2k leaves at level h. Thus $n=2^{h1}+k$. Now there are $\sum_{i=0}^{h2}2^i=2^{h1}1$ internal nodes at levels less than h  1. So in total there are $2^{h1}1+k=n1$ internal nodes.
Whew. Let me back off and regroup. Let's see. There is exactly one loser for each game played, and at tournament end there are n  1 losers (one winner). Ergo n  1 games.