Re: Magic Scheduling Algorithms

reelgore · Wed, 06 Jun 2001 16:32:11 -0700

Edmund said:

"I can generate the pairings
for central-source tournaments with even numbers of
teams; my only problem is distributing the rooms evenly
that they play in."

You want what's called a
"balanced tournament design" (BTD) for N teams.

A
BTD exists for all N except 4.

-------
Case
1: N is not congruent to 4 (mod
6).
-------

See J. Haselgrove and J. Leech, A tournament design
problem, 
Amer. Math. Monthly 84 (1977)
198-201.

Alternatively, use the following, which comes from a post by
Matt Bruce:

First let's agree on what to do for
N odd. In the first round, put team 1
in the
first room, team 2 in the second room, ... , (N+1)/2 in
the last
room. Then work backwards, putting team
(N+3)/2 in the last room, ...,
team N in the second
room. The first room gets a bye. So for
N=11,

Round 1: 1-BYE 2-11 3-10 4-9 5-8 6-7

In all
subsequent rounds, let team k go where team (k-1) played in
the
previous round, except for team 1, which should go where
team 11 played.
The bye does not move. So for
N=11,

Round 2: 2-BYE 3-1 4-11 5-10 6-9 7-8

Continuing,
this gives a BTD for N odd.

For N even [but not
congruent to 4 (mod 6)], construct the odd BTD for
N-1
teams as described above. Then put the Nth team where
the bye was.
This is unsatisfactory because team N
plays all its games in one room. 
So in that room,
switch matches as follows: have team 1 play its LAST

round in that room, team 2 play its NEXT-TO-LAST round
there, ... 
team N-1 play its FIRST round there. Move
the game that had been 
in that room into the
newly vacated room. This yields a BTD for
N = 6, 8,
12, 14, 18, 20, 24, 26, 30, 32,
.....

-------
Case 2: N is congruent to 4 (mod 6),

-------

See P.J. Schellenberg, G.H.J. van Rees, and S.A.
Vanstone, 
The existence of balanced tournament designs,
Ars Combin. 3 (1977) 303-318.

For N=4, no BTD
exists. For N=10, Lamken and Vanstone give this
example:

Round
 1: 4-8 3-9 5-6 1-2 7-10
 2: 2-9 5-8 3-10 4-7
1-6
 3: 1-3 4-6 7-8 9-10 2-5
 4: 5-7 2-10 1-9 6-8
3-4
 5: 6-10 1-7 2-4 3-5 8-9
 6: 2-3 4-9 6-7 8-10
1-5
 7: 4-5 2-8 1-10 6-9 3-7
 8: 7-9 5-10 3-8 1-4
2-6
 9: 1-8 3-6 5-9 2-7 4-10

For N=16, 22, 28,
...., the Schellenberg, van Rees, and Vanstone
article
gives an algorithm, but it is several dense pages long,
and I do not have
a brief
description.

-Roger Lee