Dear Uncle Colin,
I’m trying to organise a tournament involving seven teams and two pitches. The following conditions must hold:
- Each team plays four games
- No pair of teams meets more than once
- Each team must play at most one pair of back-to-back matches
How would you solve this?
- Bit Of Hard Rescheduling
Hi, BOHR, and thanks for your message! I found this quite tricky, but eventually came up with a schedule that works:
1 v 7
5 v 3
2 v 1
6 v 4
3 v 2
7 v 5
4 v 3
1 v 6
5 v 4
2 v 7
6 v 5
3 v 1
7 v 6
4 v 2
Proof that it meets the conditions
You could check each team, obviously, but I can show it works: working modulo 7, each team (numbered $i$) plays four games:
- in week $i$, they play $i-1$ on pitch 1;
- in week $i+1$, they play $i+1$ on pitch 1;
- in week $i+3$, they play $i-2$ on pitch 2;
- and in week $i + 5$, they play $i + 2$.
Clearly, each team plays four matches, meets no team more than once, and only plays one pair of back-to-back matches.
How I worked it out
I mean, I worked it out by throwing down numbers until it was satisfactory, but there were two keys to my approach: first, to write down when each team must play (if they only have one back-to-back pair, they must play on-on-off-on-off-on-off starting in some week).
The next trick was to schedule the back-to-back teams against each other (so the team in the second of their back-to-back games plays the team in the first of theirs). Once I’d done that, the other matches scheduled themselves!
This schedule also has the nice property that if there’s some sort of “home-team” advantage, it’s somewhat neutralised: each team plays two home games and two away.
Are there other solutions? (By ‘other’, I mean ones that can’t be reached by a trivial relabelling of teams or weeks.)
Hope that helps!
- Uncle Colin
A selection of other posts
subscribe via RSS