combinatorics and sports leagues

Factual Questions
1

OK, let’s say you’re trying to schedule a sports league, so that every team plays one game a week, and every team gets to play every other team by the end of the season, with no team playing any other team more than once. (The season would of course have to be one week shorter than the number of teams in the league, since each team plays everyone but themselves.)

In other words, you have N items, you’re partitioning them into groups of 2, and you want to create N-1 such partitions so that no two partitions contain any of the same pairings as each other.

Obviously it can’t be done for odd N. But what I want to know is for what values of N can it be done?

2

Maybe I’m missing something, but wouldn’t it work for any even N? (N mod 2 = 0) I also stumbled on this paper, where they take your basic concept, but extend the constraints to include time slots for each week.

3

I’ve been thinking about it a bit more, and I think I’ve figured out an algorithm that gives a solution for any even N. Specifically:

Team 1’s schedule: N, 2, 3, 4, 5, . . . , N-1
Team 2’s schedule: N-1, 1, N, 3, 4, 5, . . . , N-2
Team 3’s schedule: N-2, N-1, 1, 2, N, 3, 4, 5, . . . , N-3
.
.
.
Team i’s schedule (i < N): N-i+1, N-i+2, N-i+3, . . ., N-1, 1, 2, 3, . . ., i-1, N, i+1, i+2, . . ., N-i
.
.
.
Team N-1’s schedule: 2, 3, 4, . . . N-2, N,
Team N’s schedule: 1, N/2 + 1, 2, N/2 + 2, 3, N/2 + 3, . . . , N/2 + (N/2 - 1), N/2
So for example if you had a six team league (with team’s numbered 1 to 6), team 1 could play teams 6, 2, 3, 4, 5 in that order. Team 2 could play teams 5, 1, 6, 3, 4, in that order. Team 3 would play 4, 5, 1, 2, 6, etc. Obviously you can permute the order of the games as long as you apply the same permutation to every team’s schedule.

So it seems like it works for any even N. However, it doesn’t seem obvious (to me anyway), because determining one team’s schedule fixes positions in another team’s schedule, such that if you choose the matchups at random you’re likely to get stuck part way through. If I look a little more at why the method I just came up with appears to work, it could probably be turned into some sort of proof . . . but at any rate, if there’s a simple proof that it can always be done for even N, I’d like to see it.

4

Thanks, micahjn. I’ll have a look at that paper.