Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
There is some discussion at artofproblemsolving.com/Forum/viewtopic.php?f=80&t=509875 –  Gerry Myerson Dec 3 '12 at 6:18

1 Answer 1

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.

share|improve this answer
3  
Why is the only way to fail to have 2n-2 teams with a win? I don't see how this rules out the possibility that each team has at least one win but that those wins 'constructively interfere' so that you can't choose uniquely each day. –  Steven Stadnicki Jan 9 '13 at 6:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.