Now suppose you want to schedule n teams in a tournament to play TWO games each against different teams, so that the higher seeds have strictly easier schedules. This means the sum of the seeds that each team plays should be strictly decreasing with seed number. We call such a schedule a **fair 2-schedule**. For example, the only fair 2-schedule for 6 teams is:

game1 game2 #1 seed plays #5 and #6 #2 seed plays #6 and #4 #3 seed plays #4 and #5 #4 seed plays #3 and #2 #5 seed plays #1 and #3 #6 seed plays #2 and #1

What are the possible fair 2-schedules for n teams? Is such a schedule always possible? When n is even, is it always possible to schedule the games in a fair 2-schedule so that all the games get played at two times (like the example above)? Of all the possible fair 2-schedules, are some "fairer" than others? What about k-schedules for larger k?

Ulrich Schimke and Joseph DeVincentis proved that for n ≥ 5, there is always a fair 2-schedule, and that for even n there exists one that could be played at two times. Their proofs are by induction, where the middle 5 or 6 teams play one another, and the top teams play the bottom teams according to a smaller fair 2-schedule.

Ulrich Schimke also showed that for even n ≥ 4 there is a fair 3-schedule. His proof is by induction, where the middle 4 teams play one another, and the top teams play the bottom teams according to a smaller fair 3-schedule that needs to be carefully constructed.

Ulrich Schimke also noted that there is no k-schedule at all for n teams when nk is odd, and there is no fair (n-2)-schedule for n teams.

Claudio Baiocchi, Ulrich Schimke, and Joseph DeVincentis noted that there is exactly one fair 1-schedule for n even, and exactly one fair (n-1)-schedule (a round robin).

Here's the number of fair k-schedules of n teams, as computed by Claudio Baiocchi. Can you extend the table?

n \ k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|

2 | 1 | |||||||||

3 | 0 | 1 | ||||||||

4 | 1 | 0 | 1 | |||||||

5 | 0 | 1 | 0 | 1 | ||||||

6 | 1 | 1 | 1 | 0 | 1 | |||||

7 | 0 | 1 | 0 | 1 | 0 | 1 | ||||

8 | 1 | 1 | 7 | 5 | 6 | 0 | 1 | |||

9 | 0 | 4 | 0 | 40 | 0 | 9 | 0 | 1 | ||

10 | 1 | 1 | 48 | 180 | 390 | 73 | 13 | 0 | 1 | |

11 | 0 | 6 | 0 | 1864 | 0 | 3455 | 0 | 24 | 0 | 1 |

12 | 1 | 2 | 463 | 18678 | 138881 |

Joseph DeVincentis suggested the fairness of a schedule could be measured by the maximum difference between the sum of the seeds played. He noted that a reasonably fair schedule (with maximum difference 2) is one in which most seeds #i play seeds #(n-i) and #(n+1-i). Clearly n should be odd so that a team doesn't play itself.

Claudio Baiocchi suggested that we call a fair schedule **really fair** if the total of the seed numbers that each team plays are in arithmetic progression with difference 1. Obviously all fair 1-schedules are really fair. The smallest really fair 2-schedules are the 9 team schedules shown below:

#1 seed plays #5 and #9 #1 seed plays #6 and #8 #2 seed plays #6 and #7 #2 seed plays #4 and #9 #3 seed plays #4 and #8 #3 seed plays #5 and #7 #4 seed plays #3 and #8 #4 seed plays #2 and #9 #5 seed plays #1 and #9 #5 seed plays #3 and #7 #6 seed plays #2 and #7 #6 seed plays #1 and #8 #7 seed plays #2 and #6 #7 seed plays #3 and #5 #8 seed plays #3 and #4 #8 seed plays #1 and #6 #9 seed plays #1 and #5 #9 seed plays #2 and #4

Here's the number of really fair k-schedules of n teams, as computed by me, using a computer program of Claudio Baiocchi.

n \ k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|

2 | 1 | |||||||||

3 | 0 | 1 | ||||||||

4 | 1 | 0 | 1 | |||||||

5 | 0 | 0 | 0 | 1 | ||||||

6 | 1 | 0 | 0 | 0 | 1 | |||||

7 | 0 | 0 | 0 | 0 | 0 | 1 | ||||

8 | 1 | 0 | 4 | 0 | 3 | 0 | 1 | |||

9 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 1 | ||

10 | 1 | 0 | 0 | 0 | 12 | 0 | 0 | 0 | 1 | |

11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |

12 | 1 | 0 | 32 | 0 |

To show a 2-schedule, we can arrange the teams in rings so that each team plays the two neighboring teams. We can list the team seeds along the rings with slashes inbetween them. In this form, the only fair 2-schedule for 6 teams is 153426. Here are the small fair 2-schedules:

n | Fair 2-Schedules |
---|---|

3 | 123 |

5 | 14325 |

6 | 153426 |

7 | 1634527 |

8 | 17354628 |

9 | 183654729, 183729 / 456, 159 / 267 / 348, 168 / 249 / 357 |

10 | 193756482A |

11 | 1A392B / 47658, 1A38492B / 567, 1A38567492B, 1A62B / 378 / 459, 1972A53B / 468, 1972B35A / 468 |

12 | 1B3A2C / 486759, 1B3957684A2C |

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 8/9/02.