Problem Of The Week # 304 - Mar 30, 2018

Status
Not open for further replies.

Ackbach

Indicium Physicus
Staff member
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?

-----

Ackbach

Indicium Physicus
Staff member
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.

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$
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