Picking Winners in a Tournament

[Trojan Horse]

The Putnam Exam (a US national math contest for undergraduate students) was held yesterday, December 1st. There was one question on the exam that I found particularly interesting. Since I'm curious as to how you all would tackle it, I'm posting it here. Here it is:

[jadesmar]

[Zag]

He meant that every team plays one game every day, such that every team ends up playing every other team once.

I started trying to find a case where you couldn't make a selection on the last day, because the winners are all teams that you've already selected. However, I'm starting to become convinced that you can prevent this by which winner you choose each day, assuming you know the entire schedule in advance.

When you choose a winner, you choose from the ones playing already-selected teams on the last day(s). That way, the last day should end up with the two unselected teams playing each other, guaranteeing you a winner to choose. I haven't proven, though, that there aren't some cases where you just can't.

[Zag]

OK. n=2 provides a counter-example. I should have just started here rather than looking at more complex scenarios.

Day 1: A beats B, C beats D. You choose A.
Day 2: A beats C, B beats D. You have to choose B.
Day 3: A beats D, B beats C, and you don't have a team to choose.

If, on day 1, you had chosen C, you could similarly have gotten unlucky

Day 1: A beats B, C beats D. You choose C.
Day 2: C beats A, D beats B. You have to choose D.
Day 3: D beats A, C beats B, and you don't have a team to choose.

[novice]

I think the "choosing" means after the tournament's been finished and you know the full schedule.

[Zag]

What I had started with, and then talked myself out of stupidly, is this:

In choosing teams, you have to choose every team but one.
On day 1, half the teams have a win, and you can only choose one of them.
Pick one of the day one matchups from which you did not choose the winner. If the winner of that matchup never wins again, and the loser of that matchup never wins at all, then you are fundamentally forced to run out of choices.

[novice]

After the tournament finished, it will always be possible to pick one winner from each day without picking the same team twice. I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

[Zag]

[novice]

[Trojan Horse]

[Icarus]

Am I thinking this "too simple"?

You always have an even number of teams, yet you will have 1 "less" day of competition.

So with 10 teams pitted against each other requiring 9 days of competition, it is possible a "new" team won the tournament each day.

Maybe I'm making this too simple?

[jadesmar]

[Icarus]

You only have to pick 1 team at the end of each day, right?

So I can provide a scenario where it is possible

Scenario 1:
Teams A - J, Team J loses every match - therefore Day 1 you pick A, Day 2 pick B, etc. 9 days 9 different teams picked.

But what I think we should be looking for is: What scenario arises such that you cannot pick a unique winning team?

[L'lanmal]

Since you asked for approaches, here are the first things that came to mind when I read this problem:

As my professor used to note, "the problem contains an 'N', so you should probably use 'N-duction'."

1. If you are trying a constructive solution, as Zag notes, the easiest scenario is when a team loses every game, because then you can pick their opponent. (This is good for NFL survival leagues too.) Induct on the number of losses of the worst team, perhaps using the fact that all teams that worst team beats have to play each other a different week. This could help patch the gaps, or help you determine a counter-example where half the teams lose the same number of games.

2. Icarus notes that it seems possible because there are at least as many distinct winners as games. This can be seen to not be sufficient because of a scenario with 6 teams and 5 games: The teams each play the same opponent each week (not round-robin) and the winners the first 4 weeks are the same, and the last week are opposite. Then there are 6 winners over 5 weeks, but in the first four weeks there are only 3 winners. It is necessary that for any subset of weeks, there be at least as many winners as weeks. If you could show that this is also a sufficient condition, you could try to use the round-robinness to show such a situation can't/may occur.

3.After picking 2n-1 winners, there is one team left over. Introduce a week 2n where every team is deemed to win. Then write the winners as a 2n x 2n matrix where column represents team and row represents week, with 1s being wins and 0s being losses. This gives you a big 0,1 matrix where you are looking to pick a 1 in each row and each column. There are lots of algebraic things you can do with matrices.

At this point, I had to consult my mathematical intuition. It thought one of these methods was likely to reach an answer quickly, one would get too muddled to be done in the Putnam timescale, and one was pretty much pointless.

[3iff]

The only thought I had is that there can only be one team (at most) that loses all their games. Whenever two sides that have yet to win a game play each other, one must end up with a win.

[Oscar]

This is a process which I [edit]'insert 'used to' here (see later edits) [/edit] believe guarantees finding a different winner for each round:

As Zag noted, if a team has lost all their matches or only won one, choosing the winner of each of that team's matches will guarantee 2n -1 different winners in every round.

If the losingmost team (team A, say) has won 2 matches then still select the winner of each of A's matches - this will give you a list of 2n - 3 unique winners plus A twice.
A has beaten team B and C (say) and neither of these can feature in that list since they can only have played A once and lost to them, but we also know that both of these have won at least 2 matches against teams other than A.
Arbitrarily select B and check which team it played in the round where A beat C - if B beat team D (say) then merely replace that A in the list with B - you now have 2n -1 unique winners with only C missing.
If B lost to D in that round then replace that A in the list with D (you now have a list of 2n -3 unique winners plus 2 D's) , then check who B played in the round where A lost to D (E, say) If B beat E then replace that D with B. You now have all unique winners, missing only C. If E beat B then replace that D with E then check the round where A lost to E. (Your list is now 2n -3 unique winners plus 2 E's) If B wins here then replace that E with B and you are again finished, otherwise move on. Eventually, since you are never re-testing an already changed winner you will find a round where B beat R (say) when B will replace (R - 1) and D will be the selected winner for the round where A beat C. Thus you can always select unique winners when the losingmost team has 0, 1 or 2 wins.

[edit] Thinking further about this I need to make an adjustment:
If the team which B loses against when checking any round is actually C (e.g. the team we have designated as E happens to be also C) then the process can terminate there. i.e. you will have replaced D with C and the team missing from the 2n -1 unique teams list will be B not C[/edit]

When the losingmost team has 3 wins then the same process applies except A will have beaten B, C and D (say). Arbitrarily selecting B and seeing if it beat E (say) in the round when A beat C and applying the same process as above will eventually reduce the problem to a list with 2n -3 unique winners (including B) plus 2 instances of A (missing C and D).
We now repeat the process checking for C beating F (say) in the round where A beat D - eventually we will end up with all unique winners missing only D.

[edit]After yet more thought this also needs adjusting:
The list containing the unique winners has been shuffled and B added to it. The driver/index for checking the next round needs to be the current listed number and not the team which beat A in that round. In the light of this my subsequent claim about 'intuition' is bogus and the only way to prove this method is to write a successful program. Since I don't plan to do this and suspect no-one else will either I shall just leave the rest of this post unchanged, as a warning against premature posting [/edit]
In similar manner we can reduce from 4 duplicates of A down to 3, since by definition every other team has now won at least 4 games.
Intuitively I think we can reduce from any r duplicates of A to (r -1) and hence down to 0 duplicates.

How you might state any of this mathematically I haven't the faintest idea.

[gftt*]

[Trojan Horse]

Since this thing seems to have died out, I guess it's up to me to get things going again.

[DejMar]

The total number of matches in the round robin [RR]is equal to T!/(M!*(T-M)!). Given 2n teams [T=2n] with a match consisting of 2 individual teams [M=2], by substitution
RR = (2n)!/(2!*(2n - 2)!)
= n*(2n - 1).
Therefore there are a total of (n*(2n - 1)) possible winners, not necessarily
distinct. [Note: n matches per day * (2n - 1 days) = n*(2n - 1) matches, and by definition of round robin, an individual team therefore will be involved in (2n - 1) total matches, i.e., one match per day.]

There are (2n - 1) days of choosing a winner, therefore there are (2n - 1)
chosen winners. As there are 2n teams, 1 team at least will not be chosen.Thus one can necessarily choose one winning team from each day without choosing any team more than once.

(This, of course, principally depends on what is meant by choosing a winner.)

[Trojan Horse]

[Trojan Horse]

I guess I really let this lapse, didn't I? My apologies.

Let me give you guys my solution, just for the record. (By the way, I was never able to figure out if Oscar's method always works. Probably it does.) Here's the solution:

As gftt pointed out, Hall's Marriage Theorem gives a necessary and sufficient condition for us to be able to pick a different winner from each day. The condition: given any subset of the days, if there are r days in that subset, then there were at least r distinct winners on those days.

Okay, so assume that doesn't happen. Say we can find a set of r days where all the wins were recorded by r-1 teams. (Call those teams the "winners".) In other words, on those r days, the other 2n-r+1 teams (call them the "losers") lost every game they played. But that means those "losers" never played each other during those r days. (If two of those "losers" did play each other, one of them must have won.)

Okay, so every game between two "losers" occurred outside of those r days. Since there are 2n-r+1 "losers", they need at least 2n-r days to complete all of the games against each other. Add that to the original r days, and you get at least 2n days... but this is impossible, since the tournament only lasts 2n-1 days. Contradiction.

That completes the proof. Given any set of r days, at least r distinct teams recorded wins during those days. So, we can pick different winners from each day.

Again, sorry for letting this lapse.

[Elethiomel]

Nice and simple!