Google Answers Logo
View Question
Q: Unique combinations of 4 numbers between 1 to " N" ( Answered 5 out of 5 stars,   4 Comments )
Subject: Unique combinations of 4 numbers between 1 to " N"
Category: Science > Math
Asked by: tonyadam-ga
List Price: $20.00
Posted: 11 Nov 2003 15:25 PST
Expires: 11 Dec 2003 15:25 PST
Question ID: 274891
I need a formula or Excel spreadsheet that will do the following: 
Create a list of unique sets of 4 numbers from a super set of numbers
1,2,3,4 etc.  to "N".  No set of 4 numbers within the subset can
repeat itself.  Example of a valid set would be (1,25,42,31).  An
invalid set would be (1,51,42,25) since previous set already consisted
of 42 and 25. There is a finite number of unique sets based on "N".
For purposes of this request, I do not envision "N" ever being more
than 100.  The practical reason for this is to schedule periodic
dinner groups of 4 couples each so that no two couples will be at the
same dinner until all combinations have been scheduled.

Request for Question Clarification by mathtalk-ga on 11 Nov 2003 19:35 PST
Hi, tonyadam-ga:

These types of scheduling problems cannot be solved, generally
speaking, with formulas, although some techniques for constructing
solutions are known.  Computer programs can be written to search for
them, and in principle an Excel spreadsheet might be contrived to do

Before we explore possible answers to your question, let's pin down
the question itself a little better.  A typical way of scheduling
dinner groups would require that each of the N parties (which should
be a multiple of 4, in order to have any chance for the schedule to
work even once) gets assigned to a "table".

The property you described is that no pairing of values should occur
more than once, as you demonstrated by example by pairing 25 and 42
together twice.

The same sort of scheduling problem occurs with golf foursomes and
other contexts.  There are some software packages sold for this sort
of purpose, although I'm not aware of one targeting "dinner clubs"

If you picked a specific value of N, I can check and see if there
exists a "nice" solution, ie. a way of arranging that fully (N-1)/3
dinner seatings can be arranged for the group without duplicating a

Of course it's always possible (if 4 divides N) to arrange one seating
without fear of duplication, but you cannot get two seatings among
eight parties without a duplication.  If you have N=28, it's possible
to schedule a "full" nine seatings, in which each party is paired with
every other party exactly once (three of them per seating, all 27
other parties over the course of the nine seatings) with no

Please clarify where you'd like to go with this.  I can certainly give
a run down of the mathematical theory of combinatorial designs behind
these problems.

regards, mathtalk-ga

Clarification of Question by tonyadam-ga on 12 Nov 2003 06:25 PST
Each number (1 to N) represents one male/female couple.  There are
currently 52 couples but that could become 56, 60 etc.  52 divided by
4 is 13 which means that every period (in our case every other month),
13 individual dinners are scheduled and hosted by one of the four
couples in the set.  Each dinner consists of 4 couples.  I know that
there is a finite number of unique couple combinations. Since a dinner
is held every other month, there is a point in time when the cycle
must restart but with one dinner every other month will give us
several dinners without duplication of couples.  Thanks again for your
help on this.  i do find it interesting that you think there is no
formula for this. I thought this was a combinatorial function of some
sort but maybe not.

Clarification of Question by tonyadam-ga on 12 Nov 2003 17:00 PST
mathtalk-ga has it right.  Each number represents one spouse couple. 
There are 4 couples for dinner with one of the couples acting as a

Request for Question Clarification by mathtalk-ga on 15 Nov 2003 09:08 PST
Hi, tonyadam-ga:

Since you posted in the Science > Math section, you and others may be
interested in the basic "math facts" about such a problem.

Consider a set of N participants, where N is divisible by 4.  A "nice"
schedule would be one that provides, on a succession of occasions
where participants meet in groups of 4, for each participant to be in
a group with every other participant once and only once. 
"Participant" means a couple in your case, but would mean a golfer in
scheduling tee times for golf foursomes.

Since a participant meets other participants three at a time (in a
group of four), for the schedule to work out exactly the number N-1
(of "other" participants) must be divisible by 3.

Now N-4 is divisible both by 3 and by 4, i.e. by 12.  That is, a
necessary condition for a "nice" schedule to exist is that N is
congruent to 4 mod 12 (a fancy way of saying that the remainder of N
divided by 12 is 4).

It turns out that this necessary condition is also sufficient. 
Whenever N is congruent to 4 mod 12, a nice schedule does exist, but
the proof is nontrivial.

The simplest case is N = 4.  One dinner and you're done!

The number of occasions required (to complete all the meetings between
participants, assuming that groups of participants meet in parallel on
common occasions) is easily computed to be (N-1)/3.

Here's a quick table of how many occasions are needed for values N =
16,...,100 such that a nice schedule is possible:

N =  16  ==>  5 occasions
N =  28  ==>  9 occasions
N =  40  ==> 13 occasions
N =  52  ==> 17 occasions
N =  64  ==> 21 occasions
N =  76  ==> 25 occasions
N =  88  ==> 29 occasions
N = 100  ==> 33 occasions

Since your dinners are to be held only every other month, it seems
unlikely that the set of couples participating would remain constant
long enough for more than the shortest of schedules to be completed.

Therefore you may want to consider the kinds of practical compromises
outlined in my Comment below, which suggests some approaches for
couples entering and leaving the schedules and points out advantages
and disadvantages to this.

regards, mathtalk-ga

Clarification of Question by tonyadam-ga on 19 Nov 2003 08:29 PST
mathtalk-ga, I don't quite understand how you came up with your table
of occasions needed for various values of "N".  For example, you
indicate that with N=16, 5 occasions are possible.  When I manually
manipulate a matrix of 16 numbers (1 to 16) where each number
represents a couple and where each seating consists of 4 couples, I
get 10 unique sets of 4 numbers or 10 seatings where no two couples
are at the same dinner.  I got this by just writing....

Visually, you can see that each horizontal row is unique, each
vertical column is unique and each diagonal is unique thereby creating
10 sets.  What I don't know is how to expand this to something like 52
sets or to calculate how many unique sets N will create.  This
shouldn't be that hard but apparently it is.

Request for Question Clarification by mathtalk-ga on 20 Nov 2003 18:45 PST
I notice that in the first row you have these couples:


while in the second _column_ you have these:


Doesn't this put the pair of couple 1 and 2 together on both occasions?

regards, mathtalk-ga

Clarification of Question by tonyadam-ga on 21 Nov 2003 05:08 PST
mathtalk-ga, did you write a routine to get the 5 seatings for 16
couples?  Can that routine be extended to "N" where N might be as many
as 60 couples? Every time I try to extend the matrix of 16, I get into

Request for Question Clarification by mathtalk-ga on 21 Nov 2003 08:08 PST
Yes, I did write a routine (in Prolog) to find that design for 16
couples, and yes, I was more or less suggesting that something of the
sort could be scaled up to solve the scheduling problem that you are
interested in.

As far as specifically 60 couples, since 60 is divisible by 12 without
remainder, there will not be a "nice" schedule for every couple to
dine with every other couple exactly once.  [Each couple would need to
attend 59/3 dinners for that to happen, which is not a whole number.]

However I feel confident that a program could schedule (say) a dozen
occasions, in which each couple attends one of fifteen separate
dinners (accounting for all 60 couples on each occasion).  Since you
only have these dinners bimonthly, that would actually schedule things
out for two years.

Let me know if you are interested in this sort of approach.  I looked
back over the work I'd done before, and for the case of 48 couples,
I'd computed a schedule of 13 occasions with no pair of couples dining
together more than once.

regards, mathtalk-ga

P.S.  On your example with the matrix rows, columns, and diagonals, I
now understand that there's an extra comma in the last line.  Your
approach to the case of 16 couples gives 10 dinners; another 10
dinners are needed to have every couple dine with every other just
once (20 dinners in all), and it's yet another step to arrange those
20 dinners into groups of 4 dinners on 5 occasions such that each
couple attends a dinner on each occasion.  But the approach of
rows/columns/diagonals is one of the kinds of constructions that
mathematicians have used to create these "designs".

Clarification of Question by tonyadam-ga on 21 Nov 2003 14:15 PST
Mathtalk-ga...I think you are the person that solved this for me some
months ago when we had 48 couples in the dinner group.  You referenced
that solution in your comments.  I looked all over my notes for your
name or email address prior to submitting the question to GOOGLE but
could not find a way to contact you.  I would be very interested in a
routine that would create the combinations for N realizing that it
will not be a perfect set except for some values of N.  You mentioned
PROLOG.  I am unfamilar with that compiler but aren't there some free
versions of this compiler?  Is this something simple to do?  Is the
$20 offered sufficient to provide me with a routine that will maximize
the number of combinations for a given N? I doubt that N will ever get
larger than 100. Look forward to hearing from you.  PS...I'm glad to
know that at least I was on the right track by looking at the
horizontal, vertical and diagonal vectors.  I did find two more for
the 16 couple example which would have given me 12 but now realize
based on your comments that there really are 20 combinations of 4
couples.  I have no idea how to find the other 8.  Thanks again for
your help.

Request for Question Clarification by mathtalk-ga on 23 Nov 2003 10:26 PST
Thanks, tonyadam.  I guess I'm wondering whether you really want a
focus on developing some general software, that keeps a history of
what couples have already dined together, and schedules forward a few
months, or whether you are more interested in some relatively
"complete" schedules for a fixed number of couples, eg. 52, 56, 60,
etc., that are "static" solutions.

Yes, there are Prolog implementations which are free, possibly with a
restriction to personal use.  Prolog is one of the "constraint
programming languages", which makes it a natural platform for the sort
of task you are tackling.  As a very high level language, however, it
is often critiqued for inefficiency and difficulty to
optimize/performance tune.  The 16 couple task is solved almost
instantly, but how well this scales up depends to some extent on good
"search strategies".  In doing the 48 couple schedule, one might
"hope" for something approaching 15 occasions (without seating the
same couple together twice), but extensive computing on a pretty fast
machine only got the 13 occasions I reported to you then.

You may find so lengthy of a schedule to be overkill.  In that case I
think a Prolog scheduling program, with the ambition of only going a
few months into the future, would prove very useful in managing a
varying number of couples.

regards, mathtalk-ga

Clarification of Question by tonyadam-ga on 23 Nov 2003 11:22 PST
mathtalk-ga, the reason for my asking for a routine that was generic
was to have a solution that could be applied whenever "N" changes. 
Today it is 52.  However, next year, it is likely to be 60 etc.  I
wish I knew more about Prolog.  It sounds like a very interesting
language.  For purposes of this question, can you please run the
routine so that I have a set of seatings that will accommodate 52
couples?  If you can do that, we'll call it quits for now so that you
can at least get your $20 for all of the work you've already done. 
Thanks again for your help.

Request for Question Clarification by mathtalk-ga on 24 Nov 2003 08:41 PST
Okay, I dug out my old code for the 48 couple problem and took a look
at it.  I'm pretty sure I can modify it to get a schedule for 13
(bi-)months of dinners for 52 couples.

Of course I'll tack on a bunch of math stuff at the end, but that's
the kind of person I am!

regards, mathtalk-ga
Subject: Re: Unique combinations of 4 numbers between 1 to " N"
Answered By: mathtalk-ga on 26 Nov 2003 08:45 PST
Rated:5 out of 5 stars
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

Request for Answer Clarification by tonyadam-ga on 27 Nov 2003 07:13 PST
mathtalk-ga, I will hold off on rating the response until you get back
to me.  This will work for now.  Thanks again and I look forward to
hearing from you.

Clarification of Answer by mathtalk-ga on 11 Dec 2003 17:23 PST
To begin let's illustrate an interaction between symmetry and block
design by revisiting the 16 points (couples) situation.

It's natural, when thinking of arrangements of 4-blocks (four points
or couples in each set) which must "cover" the total set of 16 without
overlapping, to think of the rows and columns of a 4x4 square array:

X X X X    O O O O    O O O O    O O O O
O O O O    X X X X    O O O O    O O O O
O O O O    O O O O    X X X X    O O O O
O O O O    O O O O    O O O O    X X X X

X O O O    O X O O    O O X O    O O O X
X O O O    O X O O    O O X O    O O O X
X O O O    O X O O    O O X O    O O O X
X O O O    O X O O    O O X O    O O O X

To find additional 4-blocks we must avoid pairing two of the same
points (or couples) again, which would be the case if we could find
more "straight lines" since lines either don't intersect (parallel),
or coincide completely, or have one point in common.  We can also look
at which points are _not yet_ paired up with the "first" point in the
upper left hand corner:

O ? ? ?
O ? ? ?
O ? ? ?

To get a "nice" design we will want each of these question marks to
get paired up with that first point.  Since there are nine of them
(and a 4-block allows the first point to be paired with three other
points), we should expect to squeeze in three more "parallel" sets of

Watch what happens, however if we try the most obvious choice, running
a diagonal line through the first point:

O X ? ?
O ? X ?
O ? ? X

This seems okay at first, because the diagonal line (and ones
"parallel" to it) only intersect each row or column in a single point.
 But actually we have "painted ourselves into a corner" because it's
not possible to extend the design beyond this as far as the first
point is concerned.  That is, after picking up the diagonal block with
the first point, there are no three "question marks" left which could
be combined (into an additional 4-block with the first point) without
repeating a pair that was already made with the original rows and
columns.  (Try it!)

But if the diagonal line turns out to be a dead end, "reflect" on how
its symmetry may be partly its appeal.  The rows and columns, for
instance, with which we begin share with the square array as a whole a
symmetry, in that rotations and reflections that "preserve" the square
also map any given 4-block into some other given 4-block.

We can use this "preservation of symmetry" to guide us through to
completing a "nice" design.  While we cannot take as a 4-block the
entire diagonal, we must (in some 4-block of a nice design) pair up
each of those points with the first point.  So let's consider our
options for pairing the first two points on the diagonal:

X O O O 
O X * *
O * ? ?
O * ? ?

Since the second diagonal point eliminates the other points in the
same row or column (as already having been paired with it) and since
the entire diagonal has already been ruled out, we see that the only
option is to use the two other points out of the four remaining (the
off-diagonal pair).  Then by rotations we get an entire set of
additional 4-blocks (that cover the square):

X O O O    O O X O    O X O O    O O O X
O X O O    O O O X    X O O O    O O X O
O O O X    O X O O    O O X O    X O O O
O O X O    X O O O    O O O X    O X O O

In fact now that we know to look for 4-block "shapes" that are
preserved by rotation and reflection (in a collective sense), we
easily work out these two other parallel coverings (based on the
additional blocks needed for the first point):

X O O O    O O O X    O X O O    O O X O
O O X O    O X O O    O O O X    X O O O
O X O O    O O X O    X O O O    O O O X
O O O X    X O O O    O O X O    O X O O

X O O O    O X O O    O O X O    O O O X
O O O X    O O X O    O X O O    X O O O
O O X O    O O O X    X O O O    O X O O
O X O O    X O O O    O O O X    O O X O

Thus we get a complete schedule for five occasions at which 4 sets of
4 couples will dine together, so that overall each couple is paired
with each other couple exactly once.

Next we delve into the "not nice" cases and the algorithm I used to
devise a suitable schedule for them.  (Stay tuned...)

-- mathtalk-ga

Request for Answer Clarification by tonyadam-ga on 12 Dec 2003 05:24 PST
mathtalk-ga, you're pretty incredible.  In a very simplistic sense, I
was on the right track but did not see the very interesting symetry
that you exposed.  I'll look for your next note but am posting a
rating.  thanks again.

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

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

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:


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
tonyadam-ga rated this answer:5 out of 5 stars
mathtalk-ga solved a very difficult problem and we truly appreciate
his help and education.

Subject: Re: Unique combinations of 4 numbers between 1 to " N"
From: respree-ga on 11 Nov 2003 21:03 PST
Admittedly, I'm no math whiz...

But don't you need to consider which numbers represents male versus female?

Of course, this assumes that a 'couple' is one male and one female.

It seems to me if you just try to come up with combinations of numbers
(representing people), some of your combinations will result in all
males or all females.

Just a thought.
Subject: Re: Unique combinations of 4 numbers between 1 to " N"
From: mathtalk-ga on 12 Nov 2003 14:34 PST
Hi, respree-ga:

Apparently each number is a couple, and the dinner is actually for eight people.

One of the four couples hosts the dinner, if I've understood
tonyadam-ga's description correctly.

regards, mathtalk-ga
Subject: Re: Unique combinations of 4 numbers between 1 to " N"
From: mathtalk-ga on 14 Nov 2003 16:05 PST
Let me point out one aspect of the scheduling "design".

The number of couples participating will naturally vary over time. 
The first "seating" in any schedule can be done fairly arbitrarily. 
The couples need only be order in any fashion and then grouped by

Therefore in going from the first seating of a schedule to the second
one, it is possible to incorporate any number of additional couples
(provided their number is a multiple of four) if the new couples are
treated "as if" they had been seated together in groups of four for
the purpose of the previous dinners.

The schedule going forward can then be revised to incorporate these
new couples as if the larger number of couples had been planned from
the beginning.  However this means a complete revision of most of the
future schedule, so one needs to balance this easy way of accomodating
an increase in participants with the possibly disruptive effect on
plans based on any already announced schedule.

Furthermore this quick and easy approach will not help with adding new
couples after the second seating.

The most flexible approach I can imagine is that one plans the dinners
no more than a year in advance.  This would mean (since dinners are
held every other month) that only six seatings need to be arranged. 
Introduction of new couples participating during this time _may_ be
offset by departures of existing participants, so where it makes sense
the new couple might be used as a replacement for a departing couple.

I believe a program could be written to schedule ahead to the end of
the year, allowing for interim revisions to the schedule if necessary
to accomodate a significant number of new participants.

As I previously commented, it's possible with 28 couples to devise a
schedule for nine seatings, in which every couple dines with every
other couple exactly once.  With the seatings taking place every other
month, this would amount to an 18 month schedule, well over a year.

Even if new couples are introduced early in the year or late, it will
probably be possible to accomodate them with having two couples dine
together twice.  At the least I could write a program to search out
such schedules and either report one if found or report impossibility.
 In the latter extremis I suppose it would be desirable to produce a
schedule which strictly minimizes the numbers of duplications.

regards, mathtalk-ga
Subject: Re: Unique combinations of 4 numbers between 1 to " N"
From: mathtalk-ga on 20 Nov 2003 18:53 PST
The interested readers may want to check this "nice" solution,
scheduling five occasions for 16 couples to dine in parties of four.

Let the couples be numbered from 1 to 16, and let the groupings be
arrayed in lists:

Occasion 1:
[[2, 5, 10, 15], [3, 7, 9, 14], [4, 6, 11, 13], [1, 8, 12, 16]]

Occasion 2:
[[2, 6, 9, 16], [3, 8, 10, 13], [4, 5, 12, 14], [1, 7, 11, 15]]

Occasion 3:
[[2, 7, 12, 13], [3, 5, 11, 16], [4, 8, 9, 15], [1, 6, 10, 14]]

Occasion 4:
[[2, 8, 11, 14], [3, 6, 12, 15], [4, 7, 10, 16], [1, 5, 9, 13]]

Occasion 5:
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

No two couples ever dine together more than once.  However on each
occasion, a couple dines with three others.  Therefore after five
occasions, each couple has dined with every other.

regards, mathtalk-ga

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy