Putnam 2012, Problem B-3

A round-robin tournament of $2n$ teams lasted for $2n - 1$ days, as follows. On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once?

Solution:
The answer is yes. We first note that for any collection of $m$ days with $1 \leq m \leq 2n-1$, there are at least $m$ distinct teams that won a game on at least one of those days. If not, then any of the teams that lost games on all of those days must in particular have lost to $m$ other teams, a contradiction.

If we now construct a bipartite graph whose vertices are the $2n$ teams and the $2n-1$ days, with an edge linking a day to a team if that team won their game on that day, then any collection of $m$ days is connected to a total of at least $m$ teams. It follows from Hall's Marriage Theorem that one can match the $2n-1$ days with $2n-1$ distinct teams that won on their respective days, as desired.