View Question
Q: Unique combinations of 4 numbers between 1 to " N" ( Answered ,   4 Comments )
 Question
 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 this. 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" specifically. 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 pairing. 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 duplications. 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 host/hostess.``` 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.... 1,2,3,4, 5,6,7,8 9,10,11,12 13,1,4,15,16 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: 1,2,3,4 while in the second _column_ you have these: 2,6,10,1 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 duplicates.``` 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:
 ```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: X O O O 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 blocks. Watch what happens, however if we try the most obvious choice, running a diagonal line through the first point: X O O O 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 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```
 tonyadam-ga rated this answer: ```mathtalk-ga solved a very difficult problem and we truly appreciate his help and education.```

 ```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.```
 ```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```
 ```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 fours. 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```
 ```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```