Combinatorics: Unique Groupings

Date: 5/30/96 at 3:5:33
From: Anonymous
Subject: Unique groupings

Twenty-four friends want to play as many rounds of golf as they can. 
The conditions are (1) that they play each round in groups of four 
members, i.e. six groups; (2) that no member can play with any other 
member twice; and (3) that each member get to play with all the other 
members once. How many unique rounds of golf can they play?

I don't know where to start. What kind of maths is involved?

Thanks for your help,

Douglas Corin

Date: 5/31/96 at 15:14:33
From: Doctor Ceeks
Subject: Re: Unique groupings

Hi Douglas,

Your answer involves a branch of mathematics known as combinatorics.
In particular, your question asks for a special kind of 'block 
design'. You can read more about these in M. Hall's "Combinatorial 
Theory", although that book is over 25 years old.

The short answer to your question is that it is impossible to have
24 people play golf according to your constraints.

To see why, note that each person plays a round with three other 
people. Your conditions 2 and 3 mean that each person plays each round 
with three different people each time, yet manages to play exactly one 
round with each of the 23 other people.  Because 3 does not divide 23, 
this situation is impossible.

However, your question is a special instance of a more general 
question, which is this:  N friends play golf in several rounds.  In 
each round, they play in groups of size G.  Each friend is to play a 
round with another friend exactly once.  How many ways is this 
possible?

To begin, N must be divisible by G.  The generalization of the 
analysis for your specific case (N=24, G=4) shows that in addition,
N-1 must be divisible by G-1.

So for a solution, it is necessary that G|N and (G-1)|(N-1), where
A|B means that A divides B.

However, these conditions are not sufficient for a solution.  For 
instance, if N=36 and G=6, I don't think there is a solution.

There is a nice application of the theory of 'finite fields' to this
problem which gives an immediate solution to the case where, for 
instance, N=p^2 and G=p, where p is a prime.  To explain this would 
require quite a bit more writing, however.  If you're interested, you 
could read about these in Emil Artin's "Geometric Algebra".  (This 
book is written roughly at an advanced college level.)

-Doctor Ceeks,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/