Hi, keithadler-ga:
In addition to the links already provided above, I wanted to give an example.
9 rounds of golf foursomes among 32 golfers, such that no two golfers
play together in the same foursome more than once, can be arranged as
follows.
First divide the 32 golfers into four groups of 8 golfers. Then 8
rounds can be scheduled by taking combinations which draw one golfer
from each of the four groups. [The existence of such an 8 round
schedule is equivalent to the existence of three mutually orthogonal
Latin squares of order 8. There are formulas behind such a
construction which involve a fancy kind of arithmetic (finite field of
order 8). Details available on request.]
A final 9th round can then be added by dividing each group of 8 into
two foursomes. This round is the only one that puts players of the
same group of 8 together in a foursome.
Details of a 9 round schedule for 32 golfers in foursomes
=========================================================
Let the four groups of 8 golfers be labelled like this:
{A1,A2,A3,A4,A5,A6,A7,A8}
{B1,B2,B3,B4,B5,B6,B7,B8}
{C1,C2,C3,C4,C5,C6,C7,C8}
{D1,D2,D3,D4,D5,D6,D7,D8}
All rounds will then consist of 8 foursomes.
Round 1:
========
{ {A1,B1,C1,D1}, {A2,B2,C2,D2}, {A3,B3,C3,D3}, {A4,B4,C4,D4},
{A5,B5,C5,D5}, {A6,B6,C6,D6}, {A7,B7,C7,D7}, {A8,B8,C8,D8} }
Round 2:
========
{ {A1,B2,C3,D5}, {A2,B1,C4,D6}, {A3,B4,C1,D7}, {A4,B3,C2,D8},
{A5,B6,C7,D1}, {A6,B5,C8,D2}, {A7,B8,C5,D3}, {A8,B7,C6,D4} }
Round 3:
========
{ {A1,B3,C5,D4}, {A2,B4,C6,D3}, {A3,B1,C7,D2}, {A4,B2,C8,D1},
{A5,B7,C1,D8}, {A6,B8,C2,D7}, {A7,B5,C3,D6}, {A8,B6,C4,D5} }
Round 4:
========
{ {A1,B4,C7,D8}, {A2,B3,C8,D7}, {A3,B2,C5,D6}, {A4,B1,C6,D5},
{A5,B8,C3,D4}, {A6,B7,C4,D3}, {A7,B6,C1,D2}, {A8,B5,C2,D1} }
Round 5:
========
{ {A1,B5,C4,D7}, {A2,B6,C3,D8}, {A3,B7,C2,D5}, {A4,B8,C1,D6},
{A5,B1,C8,D3}, {A6,B2,C7,D4}, {A7,B3,C6,D4}, {A8,B4,C5,D2} }
Round 6:
========
{ {A1,B6,C2,D3}, {A2,B5,C1,D4}, {A3,B8,C4,D1}, {A4,B7,C3,D2},
{A5,B2,C6,D7}, {A6,B1,C5,D8}, {A7,B4,C8,D5}, {A8,B3,C7,D6} }
Round 7:
========
{ {A1,B7,C8,D6}, {A2,B8,C7,D5}, {A3,B5,C6,D8}, {A4,B6,C5,D7},
{A5,B3,C4,D2}, {A6,B4,C3,D1}, {A7,B1,C2,D4}, {A8,B2,C1,D3} }
Round 8:
========
{ {A1,B8,C6,D2}, {A2,B7,C5,D1}, {A3,B6,C8,D4}, {A4,B5,C7,D3},
{A5,B4,C2,D6}, {A6,B3,C1,D5}, {A7,B2,C4,D8}, {A8,B1,C3,D7} }
Round 9:
========
{ {A1,A2,A3,A4}, {B1,B2,B3,B4}, {C1,C2,C3,C4}, {D1,D2,D3,D4},
{A5,A6,A7,A8}, {B5,B6,B7,B8}, {C5,C6,C7,C8}, {D5,D6,D7,D8} }
More generally...
=================
If there are some other number N of golfers, then the "test" that you thought up:
N is divisible by 4 and N-1 is divisible by 3
is both necessary and sufficient for a "nice" solution to exist, i.e.
a schedule in which the N golfers can be "partitioned" into foursomes
on (N-1)/3 occasions in such a way that every pair of golfers plays a
round together exactly once.
This is not the hardest or messiest thing to prove I've ever come
across, but it doesn't lend itself to a quick elegant proof either.
Suffice it to say that a mathematician name Richard M. Wilson
pioneered the techniques for proving such things exist for all
sufficiently large N (they go by the name of "resolvable 2-designs of
block size 4") back in the mid 1970's, and from there it was just a
matter of supplying enough "small" examples to make sure there are no
exceptions.
Here's a reference for those "nice" cases, like when N = 28 or 40.
The trouble is that you asked about N = 32, and unfortunately 3 does
not go into 31 a whole number of times. So N = 32 is one of the "not
nice" cases. The schedule presented above seems rather tight; at the
end each player has exactly for others that they've been teamed with,
but all for of those have teamed with one another, so not only can
another round not be scheduled, it is not even possible to put
together one more foursome (without repeating some pairings). My
instinct is that 10 rounds are not possible, though it is no proof of
this merely to give the example of 9 rounds shown above.
Thanks for posting the interesting Question. Any Clarifications
needed, I'll be glad to help.
regards, mathtalk-ga |