?

Log in

No account? Create an account

Previous Entry | Next Entry

A puzzle...

I'm running a 6-team round-robin tournament. Here is a sample schedule, with the columns representing fields and the rows representing game numbers, but you don't have to use it as long as the constraints are satisfied (i.e. every team plays every other within the 5 rounds).

1 v 5 2 v 4 3 v 6
1 v 2 3 v 5 4 v 6
1 v 6 2 v 5 3 v 4
1 v 3 2 v 6 4 v 5
1 v 4 2 v 3 5 v 6

Now the problem with this is that team number one never has to change fields whereas team 3 is moving around every game. How do I optimize it for the least number of moves per team _and_ make it fair? What is that number? What does the schedule look like?

And, to make this a math/CS question, what's the generalized solution for n teams?

Right now I just need a solution for 6 teams, preferably by tomorrow morning! :)

Comments

( 6 comments — Leave a comment )
rupes
Apr. 3rd, 2009 08:06 am (UTC)
The lower bound appears to be 12 moves (4 transitions * 3 moves/transition), but I don't think that actually works - I always end up unable to conduct at least one match. I think you're going to have to stick one team with three moves.
sheenaqotj
Apr. 3rd, 2009 09:20 am (UTC)
Do you have a combo with one team having 3 moves? Please post it!
jwildstr
Apr. 3rd, 2009 02:03 pm (UTC)
I don't know if this is optimal, but I permuted yours a bit:

1 v 5 2 v 4 3 v 6
2 v 5 1 v 6 3 v 4
2 v 3 5 v 6 1 v 4
2 v 6 4 v 5 1 v 3
4 v 6 3 v 5 1 v 2

Every game is followed by one of the teams sticking around on their field. Moves by round (i.e., team moves after round i):
1: 2, 3
2: 1, 4
3: 2, 3, 4
4: 1, 3, 4
5: 2
6: 1, 3

5 gets to be the lucky team and only move once, but no-one moves more than 3 times (i.e., they have at least one pair of games on the same field. It MIGHT be possible to find one where one team moves 3 times and everyone else moves twice, but I've got other things to do :)
skydiamonde
Apr. 3rd, 2009 02:13 pm (UTC)
Are the teams seeded at all? For round robins, I'm used to initial seeding indicating how many times you have to move fields...
sheenaqotj
Apr. 3rd, 2009 03:36 pm (UTC)
Assume everything is equal.
zml
Apr. 3rd, 2009 04:19 pm (UTC)
I told her to do it by registration order. :)
( 6 comments — Leave a comment )

Latest Month

December 2015
S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
Powered by LiveJournal.com
Designed by Lizzy Enger