MHB Can one choose a winning team from each day in a round-robin tournament with no repeats?

[Ackbach]

Here is this week's POTW:

-----

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?

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

No one solved this week's POTW, which was Problem B-3 in the 2012 Putnam Archives. The solution, attributed to Kiran Kedlaya and associates, follows.

[sp]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.[/sp]