For any non-negative integer, $n$, suppose there are $2^n$ teams in a round robin tournament, and every team plays against each other team exactly once. Prove that 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. (Note: No game can end in a tie) I'm having trouble figuring out how to go about proving this problem.
[Math] Round Robin Tournament
discrete mathematicsinduction
Best Answer
There are $2^n(2^n-1)/2$ games, so at least one team must have won
$$ \left\lceil\frac{2^n(2^n-1)/2}{2^n}\right\rceil=2^{n-1} $$
games. Now argue by induction with respect to the round-robin tournament between the $2^{n-1}$ opponents who lost those games.