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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.