Golf Tournaments, Polyhedra, and Latin Squares

Suppose we need to schedule 32 golfers into foursomes for five rounds
of a tournament, in such a way that no one is in the same foursome with
anyone else more than once.  This is not too hard, because we have 
enough players to easily avoid repeated pairings.  For example, we can
use the simple pattern shown below, where the first round has the 32 
players listed horizontally, the second round has them listed vertically, 
and the subsequent rounds skew the successive columns of the vertical 
listing by 1, 2, and 3 rows per column, respectively.

Four-                           Round                            
some        1            2            3            4            5
-----  -----------  -----------  -----------  -----------  -----------
  1     1  2  3  4   1  9 17 25   1 16 23 30   1 15 21 27   1 14 19 32
  2     5  6  7  8   2 10 18 26   2  9 24 31   2 16 22 28   2 15 20 25  
  3     9 10 11 12   3 11 19 27   3 10 17 32   3  9 23 29   3 16 21 26  
  4    13 14 15 16   4 12 20 28   4 11 18 25   4 10 24 30   4  9 22 27  
  5    17 18 19 20   5 13 21 29   5 12 19 26   5 11 17 31   5 10 23 28  
  6    21 22 23 24   6 14 22 30   6 13 20 27   6 12 18 32   6 11 24 29  
  7    25 26 27 28   7 15 23 31   7 14 21 28   7 13 19 25   7 12 17 30  
  8    29 30 31 32   8 16 24 32   8 15 22 29   8 14 20 26   8 13 18 31  

However, suppose we have only 24 players, instead of 32.  This is a
bit more challenging, since we have to work harder to avoid repeated
pairings.  This is a standard problem in combinatorial design.  One
simple approach would be to start with four pair-wise orthogonal
latin squares of size 5x5.  (For any prime power N there exist
N-1 pairwise orthogonal Latin squares of size NxN.)

   0 1 2 3 4     0 1 2 3 4    0 1 2 3 4    0 1 2 3 4   
   1 2 3 4 0     2 3 4 0 1    3 4 0 1 2    4 0 1 2 3  
   2 3 4 0 1     4 0 1 2 3    1 2 3 4 0    3 4 0 1 2  
   3 4 0 1 2     1 2 3 4 0    4 0 1 2 3    2 3 4 0 1   
   4 0 1 2 3     3 4 0 1 2    2 3 4 0 1    1 2 3 4 0 

Here we've used the integers (mod 5), and the values of the
kth array for k=1,2,3,4 are given by 

        A_k(i,j) =  k (i-1)  +  (j-1)      (mod 5)

for i,j = 1,2,3,4,5.  These arrays are called "latin squares" because 
each element appears exacly once in each row and column.  They are 
said to be "pairwise orthogonal" because if you super-impose one on 
top of the other you get all 25 distinct combinations (i,j) with 
i,j = 0,1,2,3,4.  In other words, each element of one array matches 
up with each element of the other array exactly once.

So, if we let the elements of the first array represent the first five 
players, and the elements of the second array represent the next five 
players, and so on, we can create 25 foursomes from the 20 players 
by superimposing the four arrays.  Since the arrays are pairwise 
orthogonal, we are assured that no one plays in a foursome with the 
same person twice.

But we actually need 30 foursomes involving 24 players.  This can be 
done by mixing in four more players, taking advantage of the fact that 
none of the five players in a given array have yet played with each 
other.  Thus, numbering the players 1 through 24, we have the following 
five days worth of foursomes.  Each of the 24 players plays once per 
day, and no one plays with the same person twice.

 Four-
 some     Day 1         Day 2         Day 3       Day 4        Day 5
 ----  -----------   -----------  -----------  -----------  -----------
  1     1  6 11 16   22  8 14 20   3 10 12 19   4  7 15 18   5  9 13 17
  2     2  7 12 17   23  9 15 16   4 24 13 20   5  8 24 19   1 10 14 23
  3     3  8 13 18   24 10 11 17   5 21 14 16   1  9 21 20   2  6 15 24
  4     4  9 14 19    5  6 12 18   1 22 15 17   2 10 22 16   3  7 11 22
  5     5 10 15 20   21  7 13 19   2 23 11 18   3  6 23 17   4  8 12 21
  6    21 22 23 24    1  2  3  4   6  7  8  9  11 12 13 14  16 18 19 20

This is good, but we can do even better.  It's possible to schedule 24
players into foursomes for SEVEN days in such a way that no two players
are in the same foursome twice.  Obviously this means each player is
matched with 21 other players, so he is never matched with 3 of the
others.  This partitions the players into eight groups of 3, consisting
of those who never play together.  For convenience, let's say these
exclusion groups are i,i+8,i+16 modulo 24 for i=1 to 8.  Our arrangement
will be symmetrical in these sets.  Now, the players 1, 9, 17 never
play together, so we can put them in foursomes #1, #2, and #3 respectively
on each of the seven days.  Then we can fill in the other 21 players
in Foursome #1 in such a way we can create foursomes #2 and #3 simply
by adding 8 (modulo 24) to each player of the preceding foursome.

Then we can create Foursome #4 using just the 21 players, excluding
players 1, 9, and 17, in such a way that (again) Foursomes #5 and #6
are simply the preceding foursome incrementd by 8 (mod 24).  The
result is summarized below:
                                  Foursome
Day     1          2           3         4          5            6
--- ---------  ---------  ----------  --------  ----------  -----------
 1  1 2 11 21  9 10 19 5  17 18 3 13  4 7 6 24  8 12 14 15  16 20 22 23
 2  1 3 12 22  9 11 20 6  17 19 4 14  5 8 7 18  2 13 15 16  10 21 23 24
 3  1 4 13 23  9 12 21 7  17 20 5 15  6 2 8 19  3 10 14 16  11 18 22 24
 4  1 5 14 24  9 13 22 8  17 21 6 16  7 3 2 20  4 10 11 15  12 18 19 23
 5  1 6 15 18  9 14 23 2  17 22 7 10  8 4 3 21  5 11 12 16  13 19 20 24
 6  1 7 16 19  9 15 24 3  17 23 8 11  2 5 4 22  6 10 12 13  14 18 20 21
 7  1 8 10 20  9 16 18 4  17 24 2 12  3 6 5 23  7 11 13 14  15 19 21 22


For another interesting problem, suppose you're planning a golf tournament 
in which 12 players will each play one round per day for 4 days.  You 
need to decide how to split up the 12 players into 3 foursomes each 
day, and you want to choose the foursomes to minimize the number of 
repeated pairings.  Ideally you'd like to have each pair of players 
placed together in the same foursome only once, but that's obviously 
not possible with the conditions of this problem, so the objective 
is to minimize the repeated pairings AND to make the schedule as 
symmetrical as possible for the 12 players.  What's the "best" (most 
equally distributed) solution?

In this case it isn't obvious, a priori, how to even precisely 
characterize the "best" solution, because minimizing the number 
of repeated pairs doesn't necessarily give a symmetrical solution.
One approach is to think of a fairly symmetrical polyhedron with 
suitable properties.  The rhombic dodecahedron comes to mind, 
because it has 12 faces, each of which has 4 neighbors, and there 
are 3 dual pairs of mutually exclusive partitions of the 12 faces 
into three sets of four.  Here's the graph of this solid

       

The only pairs of faces whose sets of neighbors are mutually
exclusive are [(1,10),(2,8)], [(3,6),(4,7)], [(5,11),(9,12)].
The largest number of faces that are all mutually non-neighbors
is four, and each face is a member of exactly three such sets.
This gives the partitions

         1  2  8 10     1  2  9 11     1  3  7  8
         3  4  5  9     3  4  6  7     2  4  6 10
         6  7 11 12     5  8 10 12     5  9 11 12

To give a 4th partition, notice that "1" and "10" are each already 
paired twice with "2" and twice with "8", and these are the dual sets 
of opposite faces [(1,10),(2,8)].  Also, the opposite faces "1" and 
"10" are already paired once with each other.  Similar pairings exist 
for the other two dual sets.  This suggests that we create three new 
foursomes by combining non-dual pairs.  There are eight distinct ways 
of doing this.  For example, if we combine (1,10) with (4,7), and 
combine (2,8) with (9,12), and so on, we have

      1  4  7 10
      2  8  9 12
      3  5  6 11

Using this partition for the 4th round, each player's schedule
includes four "doubles" and four "singles".  No two people are on 
the same foursome more than twice, and each person plays (at least 
once) with exactly 8 (of the 11) other players.  Is this the best 
that can be done?

Return to MathPages Main Menu