The Golf Foursomes Problem

With solution by Aneel Nazareth, 11 Apr 2003

Problem: You have 16 golf players. You want them to play in foursomes, and you want every player to play with every other player. How many rounds of foursome play do you need? How do you arrange it?

Solution: You can do it in the minimum possible (5 rounds). It should be clear that this is the minimum, since each player must play with 15 others and will play with 3 others in each round.

A greedy algorithm turns out to be able to solve the problem. perl code. The patterning in the output of the program suggests to me that there is a concise group-theoretical method for determining this, but I'm too busy to think about that right now.

Here's the output:

New Round
group 0:  0  1  2  3 
group 1:  4  5  6  7 
group 2:  8  9 10 11 
group 3: 12 13 14 15 

 0 played this round:     1  2  3                                     
 1 played this round:  0     2  3                                     
 2 played this round:  0  1     3                                     
 3 played this round:  0  1  2                                        
 4 played this round:                 5  6  7                         
 5 played this round:              4     6  7                         
 6 played this round:              4  5     7                         
 7 played this round:              4  5  6                            
 8 played this round:                             9 10 11             
 9 played this round:                          8    10 11             
10 played this round:                          8  9    11             
11 played this round:                          8  9 10                
12 played this round:                                        13 14 15 
13 played this round:                                     12    14 15 
14 played this round:                                     12 13    15 
15 played this round:                                     12 13 14    

 0 has played:     1  2  3                                     
 1 has played:  0     2  3                                     
 2 has played:  0  1     3                                     
 3 has played:  0  1  2                                        
 4 has played:                 5  6  7                         
 5 has played:              4     6  7                         
 6 has played:              4  5     7                         
 7 has played:              4  5  6                            
 8 has played:                             9 10 11             
 9 has played:                          8    10 11             
10 has played:                          8  9    11             
11 has played:                          8  9 10                
12 has played:                                        13 14 15 
13 has played:                                     12    14 15 
14 has played:                                     12 13    15 
15 has played:                                     12 13 14    

New Round
group 0:  0  4  8 12 
group 1:  1  5  9 13 
group 2:  2  6 10 14 
group 3:  3  7 11 15 

 0 played this round:              4           8          12          
 1 played this round:                 5           9          13       
 2 played this round:                    6          10          14    
 3 played this round:                       7          11          15 
 4 played this round:  0                       8          12          
 5 played this round:     1                       9          13       
 6 played this round:        2                      10          14    
 7 played this round:           3                      11          15 
 8 played this round:  0           4                      12          
 9 played this round:     1           5                      13       
10 played this round:        2           6                      14    
11 played this round:           3           7                      15 
12 played this round:  0           4           8                      
13 played this round:     1           5           9                   
14 played this round:        2           6          10                
15 played this round:           3           7          11             

 0 has played:     1  2  3  4           8          12          
 1 has played:  0     2  3     5           9          13       
 2 has played:  0  1     3        6          10          14    
 3 has played:  0  1  2              7          11          15 
 4 has played:  0              5  6  7  8          12          
 5 has played:     1        4     6  7     9          13       
 6 has played:        2     4  5     7       10          14    
 7 has played:           3  4  5  6             11          15 
 8 has played:  0           4              9 10 11 12          
 9 has played:     1           5        8    10 11    13       
10 has played:        2           6     8  9    11       14    
11 has played:           3           7  8  9 10             15 
12 has played:  0           4           8             13 14 15 
13 has played:     1           5           9       12    14 15 
14 has played:        2           6          10    12 13    15 
15 has played:           3           7          11 12 13 14    

New Round
group 0:  0  5 10 15 
group 1:  1  4 11 14 
group 2:  2  7  8 13 
group 3:  3  6  9 12 

 0 played this round:                 5             10             15 
 1 played this round:              4                   11       14    
 2 played this round:                       7  8             13       
 3 played this round:                    6        9       12          
 4 played this round:     1                            11       14    
 5 played this round:  0                            10             15 
 6 played this round:           3                 9       12          
 7 played this round:        2                 8             13       
 8 played this round:        2              7                13       
 9 played this round:           3        6                12          
10 played this round:  0              5                            15 
11 played this round:     1        4                            14    
12 played this round:           3        6        9                   
13 played this round:        2              7  8                      
14 played this round:     1        4                   11             
15 played this round:  0              5             10                

 0 has played:     1  2  3  4  5        8    10    12       15 
 1 has played:  0     2  3  4  5           9    11    13 14    
 2 has played:  0  1     3        6  7  8    10       13 14    
 3 has played:  0  1  2           6  7     9    11 12       15 
 4 has played:  0  1           5  6  7  8       11 12    14    
 5 has played:  0  1        4     6  7     9 10       13    15 
 6 has played:        2  3  4  5     7     9 10    12    14    
 7 has played:        2  3  4  5  6     8       11    13    15 
 8 has played:  0     2     4        7     9 10 11 12 13       
 9 has played:     1     3     5  6     8    10 11 12 13       
10 has played:  0     2        5  6     8  9    11       14 15 
11 has played:     1     3  4        7  8  9 10          14 15 
12 has played:  0        3  4     6     8  9          13 14 15 
13 has played:     1  2        5     7  8  9       12    14 15 
14 has played:     1  2     4     6          10 11 12 13    15 
15 has played:  0        3     5     7       10 11 12 13 14    

New Round
group 0:  0  6 11 13 
group 1:  1  7 10 12 
group 2:  2  4  9 15 
group 3:  3  5  8 14 

 0 played this round:                    6             11    13       
 1 played this round:                       7       10    12          
 2 played this round:              4              9                15 
 3 played this round:                 5        8                14    
 4 played this round:        2                    9                15 
 5 played this round:           3              8                14    
 6 played this round:  0                               11    13       
 7 played this round:     1                         10    12          
 8 played this round:           3     5                         14    
 9 played this round:        2     4                               15 
10 played this round:     1                 7             12          
11 played this round:  0                 6                   13       
12 played this round:     1                 7       10                
13 played this round:  0                 6             11             
14 played this round:           3     5        8                      
15 played this round:        2     4              9                   

 0 has played:     1  2  3  4  5  6     8    10 11 12 13    15 
 1 has played:  0     2  3  4  5     7     9 10 11 12 13 14    
 2 has played:  0  1     3  4     6  7  8  9 10       13 14 15 
 3 has played:  0  1  2        5  6  7  8  9    11 12    14 15 
 4 has played:  0  1  2        5  6  7  8  9    11 12    14 15 
 5 has played:  0  1     3  4     6  7  8  9 10       13 14 15 
 6 has played:  0     2  3  4  5     7     9 10 11 12 13 14    
 7 has played:     1  2  3  4  5  6     8    10 11 12 13    15 
 8 has played:  0     2  3  4  5     7     9 10 11 12 13 14    
 9 has played:     1  2  3  4  5  6     8    10 11 12 13    15 
10 has played:  0  1  2        5  6  7  8  9    11 12    14 15 
11 has played:  0  1     3  4     6  7  8  9 10       13 14 15 
12 has played:  0  1     3  4     6  7  8  9 10       13 14 15 
13 has played:  0  1  2        5  6  7  8  9    11 12    14 15 
14 has played:     1  2  3  4  5  6     8    10 11 12 13    15 
15 has played:  0     2  3  4  5     7     9 10 11 12 13 14    

New Round
group 0:  0  7  9 14 
group 1:  1  6  8 15 
group 2:  2  5 11 12 
group 3:  3  4 10 13 

 0 played this round:                       7     9             14    
 1 played this round:                    6     8                   15 
 2 played this round:                 5                11 12          
 3 played this round:              4                10       13       
 4 played this round:           3                   10       13       
 5 played this round:        2                         11 12          
 6 played this round:     1                    8                   15 
 7 played this round:  0                          9             14    
 8 played this round:     1              6                         15 
 9 played this round:  0                    7                   14    
10 played this round:           3  4                         13       
11 played this round:        2        5                   12          
12 played this round:        2        5                11             
13 played this round:           3  4                10                
14 played this round:  0                    7     9                   
15 played this round:     1              6     8                      

 0 has played:     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 
 1 has played:  0     2  3  4  5  6  7  8  9 10 11 12 13 14 15 
 2 has played:  0  1     3  4  5  6  7  8  9 10 11 12 13 14 15 
 3 has played:  0  1  2     4  5  6  7  8  9 10 11 12 13 14 15 
 4 has played:  0  1  2  3     5  6  7  8  9 10 11 12 13 14 15 
 5 has played:  0  1  2  3  4     6  7  8  9 10 11 12 13 14 15 
 6 has played:  0  1  2  3  4  5     7  8  9 10 11 12 13 14 15 
 7 has played:  0  1  2  3  4  5  6     8  9 10 11 12 13 14 15 
 8 has played:  0  1  2  3  4  5  6  7     9 10 11 12 13 14 15 
 9 has played:  0  1  2  3  4  5  6  7  8    10 11 12 13 14 15 
10 has played:  0  1  2  3  4  5  6  7  8  9    11 12 13 14 15 
11 has played:  0  1  2  3  4  5  6  7  8  9 10    12 13 14 15 
12 has played:  0  1  2  3  4  5  6  7  8  9 10 11    13 14 15 
13 has played:  0  1  2  3  4  5  6  7  8  9 10 11 12    14 15 
14 has played:  0  1  2  3  4  5  6  7  8  9 10 11 12 13    15 
15 has played:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14