Round robin with $2^n$ teams.

Question

Show that if there are $2^n$ teams in a round robin tournament, and every team plays against each other team exactly once, we can find n+1 teams who can be listed in a column such that each team in the column has won games against every other team below that team in the column.

How would you got about showing this with induction?

Answer 1

HINT: We assume that there are no ties. It’s clearly true for $n=1$. Suppose that it’s true for some $n\ge 1$, and consider a tournament with $2^{n+1}$ teams. Let $T$ be a team with the smallest number of wins.

• Show that $T$ was beaten by at least $2^n$ teams. (It will be helpful to compute first how many matches were played in the tournament altogether.)
• Use $T$ and a set of $2^n$ teams that beat $T$ to find $n+2$ teams that can be arranged in the desired column.