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.

Imagine the following Problem.

The Student Union wants to organise a tournament with 2k participants ( $k \in \mathbb{N}$ ). There are to be m rounds and in each round players should be paired according to some rule s.t. no pair that already met meets again in the same tournament (i.e. it s not an elimination tournament; each player plays once in each round and gets ranked at the end or whatever ... )

The committee is concerned that after a certain number of rounds a clash will be unavoidable, so they want to come up with the clever way to pair players to avoid this.

My question is, how many legal rounds can we be sure of even if we organise it without any consideration for later rounds on an ad-hoc basis round by round. Whats the way to maximise the number of legal rounds and what is that maximum number ?

I am also very interested in the way people would model this situation and the reasoning/motivation that leads them to a proof/result.

share|improve this question
    
Unless I missed something, this is a target for round-robin: en.wikipedia.org/wiki/… –  leonbloy Feb 2 '12 at 19:14
add comment

2 Answers

To answer your question partly.

Let $n = 2k$.

You can do $n-1$ rounds and that is best you can do (as you can use up at most $n/2$ pairings of the total $n(n-1)/2$ in each round).

This follows from the fact that the complete graph $K_{2n}$ admits a $1$-factorization. Look at this for a simple proof: http://en.wikipedia.org/wiki/Graph_factorization#Complete_graphs

share|improve this answer
    
stupid way = without foresight I guess (i.e. I don t mean to say you just make sure there s a clash in round 2 or something of that sort :) –  Beltrame Feb 2 '12 at 19:17
    
@PeeJay: The answer might depend on how you do your picking exactly. For instance,one could luck out and get the 1-factorization. –  Aryabhata Feb 2 '12 at 19:19
    
good point, you might of course just hit the optimum by pure chance. I guess this means it s the minimum number of legal pairings after which we run into trouble that s relevant for that part. I.e. how many rounds can we be sure of if we pair in a legal but worst possible way in each round. –  Beltrame Feb 2 '12 at 19:22
add comment

In a 6-way round robin, you can always play three rounds, but if you aren't careful you won't be able to play a fourth. Divide the players into two groups of three, and let the first three rounds pair up players in one group with those in the other. Then in the fourth round each player needs to play within his/her group, and since there's an odd number in the group, that's impossible.

By the way, I've actually seen this happen at a (very low-level) chess tournament that was organized into groups of 6 who were supposed to play a round-robin. The tournament director was unaware that some care was needed, and wound up making the pairings for one group of 6 in such a way that byes and an extra round were needed.

In general, if the number of players is $n=4m+2$ then if your first $2m+1$ rounds leave you with two $2m+1$-player round robins then you won't be able to play round $2m+2$. Again, this can happen if you split the players into two groups of $2m+1$ and have people play outside their groups for the first $2m+1$ rounds. I don't know whether there's a way to run into trouble earlier than round $2m+2$.

The other case is $n=4m$ for some $m$. You could have a group of $2m-1$ players play their first $2m+1$ games against outsiders, leaving them with no way to schedule round $2m+2$. Again, I don't know whether that's the fastest way to get into trouble.

share|improve this answer
add comment

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.