A round-robin tournament among $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?
There is a solution by applying Hall's theorem, but I was wondering if there exists an elementary solution that someone without knowledge of Hall's theorem could find during the test.
This question was simple enough, and did not require Hall's theorem at all. Consider the question. We need to choose a distinct winning team for each of $2n-1$ days. Thus, in order to fail this condition, we must only have $2n-2$ teams with a win, or put another way, only $2$ of the $2n$ teams without a win. This is clearly impossible because at some point those two teams must have played one another, and one team would have won the game, and thus not be winless. Therefore, it is impossible to have less than $2n-1$ teams with a win, and thus it is always possible to select a distinct winning team for each of $2n-1$ days of the tournament.