# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="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.[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Elethiomel
Posted: Sun Feb 24, 2013 11:29 am    Post subject: 1

Nice and simple!
Trojan Horse
Posted: Sun Feb 24, 2013 12:11 am    Post subject: 0

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.
Trojan Horse
Posted: Mon Dec 17, 2012 4:21 am    Post subject: -1

DejMar wrote:
The number of winners in a day is equal to the number of matches in a day, which is 2n - 1.

Uh, there's only n matches per day.
DejMar
Posted: Mon Dec 17, 2012 3:28 am    Post subject: -2

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
Posted: Mon Dec 17, 2012 12:58 am    Post subject: -3

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

gftt* wrote:
L'lanmal wrote:
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.

Check out Hall's Marriage Theorem.

I was happy when gftt posted this, and I was disappointed when no one posted after that. Keep following this path, and you'll get to the solution.

As for Oscar's post: I'm not yet sure whether his plan would always work. But it sounds very similar to the usual proof of Hall's Marriage Theorem, so it just might work out.
gftt*
Posted: Wed Dec 05, 2012 12:21 pm    Post subject: -4

L'lanmal wrote:
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.

Check out Hall's Marriage Theorem.
Oscar
Posted: Wed Dec 05, 2012 9:49 am    Post subject: -5

This is a process which I '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.

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.

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.
3iff
Posted: Wed Dec 05, 2012 8:21 am    Post subject: -6

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.
L'lanmal
Posted: Tue Dec 04, 2012 11:23 pm    Post subject: -7

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.
Icarus
Posted: Mon Dec 03, 2012 10:58 pm    Post subject: -8

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?
Posted: Mon Dec 03, 2012 10:37 pm    Post subject: -9

Icarus wrote:
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?

There are only n winners every day. So, you can only pick from 5 of the 10, on each of the 9 days.

Can it be shown that exactly one team loses every match.. and exactly one team wins every match?
Icarus
Posted: Mon Dec 03, 2012 10:22 pm    Post subject: -10

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?
Trojan Horse
Posted: Mon Dec 03, 2012 12:36 am    Post subject: -11

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

Correct.
novice
Posted: Sun Dec 02, 2012 11:50 pm    Post subject: -12

Zag wrote:
If there are no teams which won no games, there can only be three teams that won only 1, and those three wins have to be on separate days (because they are against each other). Pick any one of these on the game he won. Now pick his opponent on every other day.

There can be at most 3 such teams, but there can be 0 such teams, in which case your method breaks down.
Zag
Posted: Sun Dec 02, 2012 11:29 pm    Post subject: -13

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

~rereads the problem~ You could be right. It doesn't say that you have to choose as you go. If you can choose retrospectively, I suspect that there's always a way to do it.

If one team won no games, then there can only be one team which won only 1 game. (Because everyone beat the 0-winner. If you say that there's a team for which that was their only victory, everyone else beat that team.) You can always just choose the 0-winner's opponent, and you always have a different team to select.

If there are no teams which won no games, there can only be three teams that won only 1, and those three wins have to be on separate days (because they are against each other). Pick any one of these on the game he won. Now pick his opponent on every other day.
novice
Posted: Sun Dec 02, 2012 11:07 pm    Post subject: -14

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
Posted: Sun Dec 02, 2012 11:03 pm    Post subject: -15

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
Posted: Sun Dec 02, 2012 11:00 pm    Post subject: -16

I think the "choosing" means after the tournament's been finished and you know the full schedule.
Zag
Posted: Sun Dec 02, 2012 10:53 pm    Post subject: -17

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.
Zag
Posted: Sun Dec 02, 2012 10:08 pm    Post subject: -18

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.
Posted: Sun Dec 02, 2012 9:21 pm    Post subject: -19

Trojan Horse wrote:
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:

Quote:
A round-robin tournament among 2n teams lasted for 2n-1 days, as follows. On each day, every team played 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?

Note: I do know the answer to this problem, and I am prepared to give hints as necessary.

Isn't this a matter of trying to fit 2n pigeons into 2n-1 boxes.

Oh it's backwards from that. Nevermind.

So, on day 1, n teams win.. and you pick one.
On day 2, a different (or the same) n teams win and you pick one

Or, is there elimination?

Without elimination it seems like if the same n teams win every day, then no, at day n+1, all the winning teams have already been selected.

So, the same n teams can't win every day because some of them play each other on day 2.

Wait.. did you say "On each day, every team played against another team" does that exclude the same matches being played " Presumably any time you play a match, it's against another team.

I should probably figure out what round robin means.
Trojan Horse
Posted: Sun Dec 02, 2012 9:11 pm    Post subject: -20

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:

Quote:
A round-robin tournament among 2n teams lasted for 2n-1 days, as follows. On each day, every team played 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?

Note: I do know the answer to this problem, and I am prepared to give hints as necessary.