Problem of the Month (July 2002)

Everyone knows that in the first round of a seeded tournament with n teams, the #1 seed plays the #n seed, the #2 seed plays the #(n-1) seed, etc. This schedule has the property that stronger teams play easier games.

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?


ANSWERS

Arjen Stolk made some progress on the problem, finding an algorithm to produce fair 2-schedules, but nothing precise.

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?

Number of Fair k-Schedules of n Teams

n \ k12345678910
21
301
4101
50101
611101
7010101
81175601
9040400901
101148180390731301
1106018640345502401
121246318678138881

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.

Number of Really Fair k-Schedules of n Teams

n \ k12345678910
21
301
4101
50001
610001
7000001
81040301
902000001
10100012000 1
1100000000 01
1210320

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:

Fair 2-Schedules with n Teams

n Fair 2-Schedules
3123
514325
6153426
71634527
817354628
9183654729, 183729 / 456, 159 / 267 / 348, 168 / 249 / 357
10193756482A
111A392B / 47658, 1A38492B / 567, 1A38567492B, 1A62B / 378 / 459, 1972A53B / 468, 1972B35A / 468
121B3A2C / 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.