Hi, tonyadam-ga:
I modified my program for the 48 couple situation and produced this
schedule (13 lists of 13 lists!) for 52 couples in parties of 4:
[
[1, 50, 27, 36], [5, 2, 31, 40], [9, 6, 35, 44], [13, 10, 39, 48]
[17, 14, 43, 52], [21, 18, 47, 4], [25, 22, 51, 8], [29, 26, 3, 12]
[33, 30, 7, 16], [37, 34, 11, 20], [41, 38, 15, 24], [45, 42, 19, 28]
[49, 46, 23, 32]
]
[
[1, 46, 31, 28], [5, 50, 35, 32], [9, 2, 39, 36], [13, 6, 43, 40]
[17, 10, 47, 44], [21, 14, 51, 48], [25, 18, 3, 52], [29, 22, 7, 4]
[33, 26, 11, 8], [37, 30, 15, 12], [41, 34, 19, 16], [45, 38, 23, 20]
[49, 42, 27, 24]
]
[
[1, 42, 35, 48], [5, 46, 39, 52], [9, 50, 43, 4], [13, 2, 47, 8]
[17, 6, 51, 12], [21, 10, 3, 16], [25, 14, 7, 20], [29, 18, 11, 24]
[33, 22, 15, 28], [37, 26, 19, 32], [41, 30, 23, 36], [45, 34, 27, 40]
[49, 38, 31, 44]
]
[
[1, 38, 19, 8], [5, 42, 23, 12], [9, 46, 27, 16], [13, 50, 31, 20]
[17, 2, 35, 24], [21, 6, 39, 28], [25, 10, 43, 32], [29, 14, 47, 36]
[33, 18, 51, 40], [37, 22, 3, 44], [41, 26, 7, 48], [45, 30, 11, 52]
[49, 34, 15, 4]
]
[
[1, 34, 51, 32], [5, 38, 3, 36], [9, 42, 7, 40], [13, 46, 11, 44]
[17, 50, 15, 48], [21, 2, 19, 52], [25, 6, 23, 4], [29, 10, 27, 8]
[33, 14, 31, 12], [37, 18, 35, 16], [41, 22, 39, 20], [45, 26, 43, 24]
[49, 30, 47, 28]
]
[
[1, 30, 43, 20], [5, 34, 47, 24], [9, 38, 51, 28], [13, 42, 3, 32]
[17, 46, 7, 36], [21, 50, 11, 40], [25, 2, 15, 44], [29, 6, 19, 48]
[33, 10, 23, 52], [37, 14, 27, 4], [41, 18, 31, 8], [45, 22, 35, 12]
[49, 26, 39, 16]
]
[
[1, 26, 15, 52], [5, 30, 19, 4], [9, 34, 23, 8], [13, 38, 27, 12]
[17, 42, 31, 16], [21, 46, 35, 20], [25, 50, 39, 24], [29, 2, 43, 28]
[33, 6, 47, 32], [37, 10, 51, 36], [41, 14, 3, 40], [45, 18, 7, 44]
[49, 22, 11, 48]
]
[
[1, 22, 47, 40], [5, 26, 51, 44], [9, 30, 3, 48], [13, 34, 7, 52]
[17, 38, 11, 4], [21, 42, 15, 8], [25, 46, 19, 12], [29, 50, 23, 16]
[33, 2, 27, 20], [37, 6, 31, 24], [41, 10, 35, 28], [45, 14, 39, 32]
[49, 18, 43, 36]
]
[
[1, 18, 39, 12], [5, 22, 43, 16], [9, 26, 47, 20], [13, 30, 51, 24]
[17, 34, 3, 28], [21, 38, 7, 32], [25, 42, 11, 36], [29, 46, 15, 40]
[33, 50, 19, 44], [37, 2, 23, 48], [41, 6, 27, 52], [45, 10, 31, 4]
[49, 14, 35, 8]
]
[
[1, 14, 23, 44], [5, 18, 27, 48], [9, 22, 31, 52], [13, 26, 35, 4]
[17, 30, 39, 8], [21, 34, 43, 12], [25, 38, 47, 16], [29, 42, 51, 20]
[33, 46, 3, 24], [37, 50, 7, 28], [41, 2, 11, 32], [45, 6, 15, 36]
[49, 10, 19, 40]
]
[
[1, 10, 7, 24], [5, 14, 11, 28], [9, 18, 15, 32], [13, 22, 19, 36]
[17, 26, 23, 40], [21, 30, 27, 44], [25, 34, 31, 48], [29, 38, 35, 52]
[33, 42, 39, 4], [37, 46, 43, 8], [41, 50, 47, 12], [45, 2, 51, 16]
[49, 6, 3, 20]
]
[
[1, 6, 11, 16], [5, 10, 15, 20], [9, 14, 19, 24], [13, 18, 23, 28]
[17, 22, 27, 32], [21, 26, 31, 36], [25, 30, 35, 40], [29, 34, 39, 44]
[33, 38, 43, 48], [37, 42, 47, 52], [41, 46, 51, 4], [45, 50, 3, 8]
[49, 2, 7, 12]
]
[
[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]
[17, 18, 19, 20], [21, 22, 23, 24], [25, 26, 27, 28], [29, 30, 31, 32]
[33, 34, 35, 36], [37, 38, 39, 40], [41, 42, 43, 44], [45, 46, 47, 48]
[49, 50, 51, 52]
]
This schedule cannot be extended any further. A different schedule is
possible that would run out to 17 occasions, but this is beyond the
capability of my program's approach. If you need the extra length (2
years and 10 months vs. 2 years and 2 months), then I can probably
look it up at the university library for you next week.
Hopefully this will be of use to you. I need to tinker some with my
code to make it work for general multiples of 4, but soon I'll post a
follow-up comment giving my Prolog code. I'll also give some of the
math history, so if you like you can hold off on rating my Answer
until those things are there.
regards, mathtalk-ga |
Clarification of Answer by
mathtalk-ga
on
12 May 2005 18:38 PDT
Hi, tonyadam-ga:
At last I've gotten around to writing up some of the technical
aspects of the dinner club scheduling problem, which is also
known as the Social Golfers Problem.
The Social Golfers Problem asks us to "schedule" N participants
in groups of size k each "week" for as many weeks as possible
without any two participants being scheduled in a group together
more than once. This assumes k divides N as otherwise not even
one such week could be scheduled.
A perfect schedule would group every pair of participants exactly
once. This is called a resolvable 2-design with block size k.
Here "2-design" means a set of groups (of size k) such that every
pair of participants appears exactly once, and "resolvable" means
that the set of groups can be partitioned so that each subset of
groups contains each participant once (equivalent to one week on
the schedule).
In combinatorics the partition is often referred to as "parallel
classes" because groups within a "class" are disjoint and two
groups from different "classes" can intersect in at most one
participant. Otherwise some pair of participants would "meet"
more than once.
For the existence of a perfect schedule it is necessary that in
addition to N being divisible by k:
N*(N-1) is divisible by k*(k-1)
which is a consequence of the possible pairs of N participants
being divided up into pairs within groups of size k.
R. Wilson showed that these two necessary conditions are also
sufficient for "big enough" N, where "big enough" depends on k.
It has been shown by R. Wilson and others that for block size 4,
resolvable 2-designs do exist for all N congruent to 4 mod 12,
eg. N = 4, 16, 28, 40, etc. A full account may be found here:
A. E. Brouwer, Block Designs, in: "Handbook of Combinatorics",
R.L. Graham, M. Grötschel and L. Lovász, eds,
North Holland (1995), Chapter 14, pp. 693-745.
But what about the "imperfect" cases? One possibility might
be to let go of resolvability, ie. of the scheduling of each
participant exactly once per week, yet still retaining the idea
that every pair of participants must meet exactly once.
This would allow the flexibility to have N not divisible by k,
although N*(N-1) is still going to be divisible by k*(k-1).
There exists, for example, a 2-design of block size 4 on 13
points (participants) which is nonresolvable:
{ {1,2,3,4}, {1,5,6,7}, {1,8,9,10}, {1,11,12,13},
{2,5,8,11}, {2,6,9,12}, {2,7,10,13},
{3,5,9,13}, {3,6,10,11}, {3,7,8,12},
{4,5,10,12}, {4,6,8,13}, {4,7,9,11} }
However the spirit of the Social Golfers Problem (and of the
dinner club considered here) is to schedule participants
on a weekly basis but allow that some pairs of participants
will never meet. The rest of this note is concerned with a
construction of such "packing designs" related to mutually
orthogonal Latin squares (MOLS), which naturally we must first
define.
* * * * * * * * * * * * * * * * * * * * *
For further details about what follows, the interested reader
may consult:
A Course in Combinatorics, Ch. 17 & 22
J. H. van Lint and R. M. Wilson
Cambridge University Press (1992)
A Latin square of order n is an nxn matrix whose entries are
taken from a set of n symbols, eg. {1,..,n}, in such a way
that every row and every column of the matrix contains each
symbol exactly once.
Two Latin squares of order n, say matrices A and B, are said
to be orthogonal iff the set of ordered pairs:
{ (A(i,j),B(i,j)) | i,j = 1,..,n }
contains all n˛ possible ordered pairs, each exactly once.
A set of Latin squares is said to be mutually orthogonal iff
every pair of distinct Latin squares in the set is orthogonal.
As already indicated, mutually orthogonal Latin squares will
be abbreviated by MOLS.
Here for the sake of illustration are three mutually orthogonal
Latin squares of order 4:
4 1 2 3 4 1 2 3 4 1 2 3
1 4 3 2 2 3 4 1 3 2 1 4
2 3 4 1 3 2 1 4 1 4 3 2
3 2 1 4 1 4 3 2 2 3 4 1
There can be at most n-1 MOLS of order n, so a set of MOLS of
this size is said to be complete, as in the example above. We
know how to construct complete sets of MOLS when n is a prime
or a power of a prime, but it is an open question whether any
complete sets of MOLS exist for other values of n.
So trivially there do not exist a pair of MOLS of order 2, and
Euler found that there also is no pair of MOLS of order 6.
Based on this he conjectured that pairs of MOLS would not
exist when n is congruent to 2 mod 4, but this turned out to
be entirely wrong. Bose et al showed that pairs of MOLS
exist for all orders greater than 2, except 6.
It is still unknown whether three MOLS of order 10 can exist,
although it is known there does not exist a complete set of
MOLS of order 10, ie. nine are not possible. For n > 51, it
is known that at least three MOLS exist. MacNeish showed long
ago how to construct r MOLS's of order mn from r MOLS's each
of order m and order n.
* * * * * * * * * * * * * * * * * * * * *
Return now to the case when N is divisible by k, say N = n*k.
Let the N participants be partitioned into k "leagues" of n
participants each. Consider a schedule which consists of only
groups that consist of one participant from each league.
Since these groups of size k have one participant from each of
the k leagues, two participants from the same league will never
belong to the same group. Because of this, we can "economize"
on notation and refer only to the participants by a number from
1 to n within their league, and a group denoted by a k-tuple
of such integers with the league indicated by the position of
an entry in that k-tuple. Thus (1,1,...,1) would be a group
containing the first participant from each league.
Such a schedule is equivalent to having a set of k-1 MOLS of
order n. The correspondance is briefly sketched as follows.
Let M_1 be the nxn matrix whose i'th row has value i in all of
its entries. Let M_2,..,M_k be k-1 matrices of order n. Set
the schedule for week j to be the groups:
W_j = { (M_1(i,j), M_2(i,j),..., M_k(i,j)) | i = 1 to n }
The conditions that:
(1) every participant in each league appears in the schedule
once in every week, and that:
(2) two participants from different leagues meet in one and
only one week
are then equivalent to M_2,...,M_k being a set of k-1 MOLS of
order n.
Let's illustrate the idea by constructing a schedule of groups
of size four for 16 participants:
A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,D3,D4
separated into four leagues. Consulting the set of three MOLS
of order 4 mentioned earlier, we have for the first week:
{ {A1,B4,C4,D4}, {A2,B1,C2,D3}, {A3,B2,C3,D1}, {A4,B3,C1,D2} }
for the second week:
{ {A1,B1,C1,D1}, {A2,B4,C3,D2}, {A3,B3,C2,D4}, {A4,B2,C4,D3} }
for the third week:
{ {A1,B2,C2,D2}, {A2,B3,C4,D1}, {A3,B4,C1,D3}, {A4,B1,C3,D4} }
and for the fourth week:
{ {A1,B3,C3,D3}, {A2,B2,C1,D4}, {A3,B1,C4,D2}, {A4,B4,C2,D1} }
Furthermore there is a "free" fifth week we can schedule by
taking the four leagues themselves as the groups of fours:
{ {A1,A2,A3,A4}, {B1,B2,B3,B4}, {C1,C2,C3,C4}, {D1,D2,D3,D4} }
Altogether these five weeks are a perfect schedule (resolvable
2-design) in which every pair of players meets exactly once.
regards, mathtalk-ga
|
