Determine all ways to group 49 into groups of 7 such that

Factual Questions
1

…no item appears more than once in the same group with any other item.

I am trying to solve this in Excel for someone. I could write a VBA program to do it but I cannot imagine what the algorithm would be. The real-world application is you have a conference of some sort with 49 people. You want to seat them at tables of 7, and have 7 rounds of seatings. Therefore, each person will meet 42 people, and never sit at the same table with any other given person more than once.

First: Is it provable that this is mathematically possible?
Second: Is there an algorithm to generate the necessary seatings? Or do you have to do it by brute force? The brute force method would involve analyzing a number of permutations on the order of 10^6 so is likely intractable for practical purposes.

The question as worded did not require each person to meet all 48 other people, only 42. But I am following up to make sure that was what was intended.

2

I think what you’re looking for is mutually orthogonal 7 x 7 Latin squares and want 6 of them.

3

That sounds about right. But I don’t know how to generate them.

4

The Wikipedia article on the subject shows how to construct them when the order of the squares is prime, though it’s a bit buried in jargon. What it boils down to is that the (i,j) entry of the square r = 1 \dots 6 is given by

M_r(i,j) = i + rj \mod 7.

Note, however, that this only gives 6 rounds of seatings, not 7. I think that including r = 0 gives you another “seating” that’s orthogonal to the 6 Latin squares, even thought it’s not actually a Latin square.

More generally, what you’re looking for is called a block design. A design in which everyone meets everyone else once is a “balanced incomplete block design”; in a group of 49 people you would have

\begin{align} v &= 49 && \text{(total number of people)} \\ \lambda &= 1 && \text{(number of times each person sees anyone else)} \\ k &= 7 && \text{(people per block)} \\ r &= 8 && \text{(blocks in which each person appears)} \\ b &= 56 && \text{(total number of blocks)} \end{align}

Your question as originally posed would be a partially balanced block design, since there would be some pairs of elements that would not be in any “block” together.

The literature on the subject gets pretty jargony pretty fast, but hopefully it gives you something to Google on.

5

I would approach it something like this:
A row for each participant. Numbers 01 to 49
For each seating round, you’ll need a set of columns:
First column, a number 1 to 7 - table number.
Next column, create a string of other participants’ position number - so after a round of seating, the string would look something like this: “03 07 15 16 33 48”
Next column, that string concatenated with previous seating strings - essentially, a list by number of everyone they’ve already seated with so far.

You start a round of seating by assigning the first table number A not yet full to the first line/participant.
You then consider the next line/participant. If he has not sat with any of the particpants above for A, and table A has not reach 7 participants, he gets table A also. Otherwise, B. (Or C, etc.)
Repeat for each participant.
“Has not sat with” is simple - seach the concatenated string for an occurance of the line numbers.

Bob is number 6, Fred is number 7 Jim is number 22. Bob and Fred are assigned table B this round,
Can I seat Jim at Bob’s table B this round?
Simple - is “06” or “07” already in Jim’s string of “been there” participants?
No. Seat him at B
Yes. Consider Table C next - any conflict there? and so on.

Whether this would actually work, I don’t know.

6

I think it would work but I expect that this kind of “try everything and rule out invalid combinations” would be very computationally intense the further along you get, and might not be practical.

7

If you identify individuals by integers then in excel arrange them as:

1
2
3
4

(first column for group of 4 attendees - 2 tables)

For the next columns keep the first row fixed and shift the others down 1 by column. Bring the last attendee back to the top

111
243
324
432

Read off your tables as row1/row2 row3/row4
(1,2) (3,4)
(1,4) (2,3)
(1,3) (4,2)

I tried it for 6 attendees with tables of 3 and it works the same.

8

I don’t see it…

1 1
2 5
3 6

4 2
5 3
6 4 etc.
Already 2,3 and 5,6 have sat together

So: exclude double-ups
1 1
2 4
3 ?

4
5
6
There are already no 3 people who have not sat with any others.
The table cannot be too large. let’s try 9 by 3’s

111
245
379

422
554
688

733
86?
99
I reach this point and ?? among them have sat with the entire group 1-9
(Just going down the list, picking someone who has not sat with someone else.

There in a group of 49, 49x48/2 = 1176 unique pairs when order does not count. (1,2 same as 2,1 and of course 1,1 etc not allowed)
Each table, one seating, eliminates 7x6/2=21 pairs
Each seating therefore eliminates 7x21=147 pairs, so 7 seatings requires 1,029 unique pairs

it would seem to be mathematically possible.

maybe you can create a list of all pairs;
assign the first round of tables by picking a table-full of pairs where the first number matches
Now delete all the pairs that the table eliminates.
I.e. (1,2), (1,3) and (1,4) eliminates 2,3 and 2.4 and 3,4 also. (“They have now already sat together”)

Presumably your pairs were generated lower number first, but you may have to pick a table where the first or last number matches (I.e. a table for #4 is 4,5 and 2,4)

Things would get complicated if you toward the end do not have 7 pairs that include the same number to assign to a table.

How you would do this in a spreadsheet without macros I have no idea.

9

Let me look at it again

10

Slightly less generally, it is a Steiner system, and less generally than that it’s a case of the Social Golfer Problem. Somewhat related is the Kirkman’s schoolgirl problem.

I think a general solution is unknown, but there’s a list of available solutions here:
http://web.archive.org/web/20050308115423/http://www.icparc.ic.ac.uk/~wh/golf/

Here’s a 7-7-7 solution:

[[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]]
[[1, 8, 15, 22, 29, 36, 43], [2, 9, 17, 25, 33, 41, 49], [3, 10, 18, 26, 34, 42, 48], [4, 11, 19, 27, 35, 40, 47], [5, 12, 20, 28, 32, 39, 46], [6, 13, 21, 24, 31, 38, 45], [7, 14, 16, 23, 30, 37, 44]]
[[1, 10, 17, 23, 31, 39, 47], [2, 8, 16, 24, 32, 40, 48], [3, 11, 15, 25, 30, 38, 46], [4, 12, 18, 22, 33, 37, 45], [5, 13, 19, 26, 29, 41, 44], [6, 14, 20, 27, 34, 36, 49], [7, 9, 21, 28, 35, 42, 43]]
[[1, 9, 18, 27, 32, 38, 44], [2, 14, 15, 26, 35, 39, 45], [3, 8, 19, 28, 31, 37, 49], [4, 10, 20, 24, 30, 41, 43], [5, 11, 21, 23, 33, 36, 48], [6, 12, 16, 25, 29, 42, 47], [7, 13, 17, 22, 34, 40, 46]]
[[1, 14, 19, 24, 33, 42, 46], [2, 13, 18, 28, 30, 36, 47], [3, 9, 20, 23, 29, 40, 45], [4, 8, 21, 25, 34, 39, 44], [5, 10, 16, 22, 35, 38, 49], [6, 11, 17, 26, 32, 37, 43], [7, 12, 15, 27, 31, 41, 48]]
[[1, 13, 20, 25, 35, 37, 48], [2, 12, 19, 23, 34, 38, 43], [3, 14, 21, 22, 32, 41, 47], [4, 9, 16, 26, 31, 36, 46], [5, 8, 17, 27, 30, 42, 45], [6, 10, 15, 28, 33, 40, 44], [7, 11, 18, 24, 29, 39, 49]]
[[1, 12, 21, 26, 30, 40, 49], [2, 11, 20, 22, 31, 42, 44], [3, 13, 16, 27, 33, 39, 43], [4, 14, 17, 28, 29, 38, 48], [5, 9, 15, 24, 34, 37, 47], [6, 8, 18, 23, 35, 41, 46], [7, 10, 19, 25, 32, 36, 45]]
11

Incidentally, the upper bound on an N\times N system will be N+1 rounds.

There are N^2 total people, and thus each person would ideally be paired with each of the other N^2-1 people. Each round introduces a person to N-1 other people, so at most (and optimally) there can be \frac{N^2-1}{N-1} = N+1 rounds.

Only some combinations actually reach this optimal result, though. Somewhat weirdly, the 6x6 case only reaches 3 rounds, due to how Latin Squares work. But 4x4 can reach 5 rounds.

12

This represents 7 tables with 7 attendees each at one sitting. If you rotate the top row for each of 7 sittings then the top row will have met all of the attendees, but each of the others will only have met 13 attendees. Any shifting of the matrix below the first row will reduce the number of unique encounters.

However, it really doesn’t make any difference because the attendees will move the place cards to sit where they want. Ask me how I know.

13

The “Latin squares” approach I mentioned above allows you to do a careful system of rotations of all of the rows so that everyone gets to meet (almost) everyone. It boils down to:

  • Round 1: Use the columns as listed.
  • Round 2: Keep the top row where it is. Rotate row 1 one place to the right; Row 2 two places to the right; Row 3 three places to the right; etc.
  • Round 3: Keep the top row where it is. Rotate row 1 two places to the right; Row 2 four places to the right; Row 3 six places to the right; etc.
  • Round 4: Keep the top row where it is. Rotate row 1 three places to the right; Row 2 six places to the right; Row 3 nine places to the right (or equivalently, two places to the right); etc.

This leads to the following system of rotations:

Round 1 2 3 4 5 6 7
Row 1 0 0 0 0 0 0 0
Row 2 0 1 2 3 4 5 6
Row 3 0 2 4 6 1 3 5
Row 4 0 3 6 2 5 1 4
Row 5 0 4 1 5 2 6 3
Row 6 0 5 3 1 6 4 2
Row 7 0 6 5 4 3 2 1

where the numbers in each row of this table tells you how many rows to rotate the given row of your original table. No one person will meet another person twice in this system, because no two rows get rotated by the same amount in two distinct rounds.

In this seating schedule, nobody meets anyone in the same row of your original table. But if you want to do that, make Round 8 so that the meetings are between the people in the same row of the original table.

Be sure to impress upon your attendees the elegance and mathematical beauty of this plan. They will be so deeply emotionally moved by its zen-like simplicity that they will not dare deviate from it.

14

That is brilliant. I can use that directly without needing a general solution. Thank you very much. The link doesn’t have the 7-7-7 solution–where did you get it?

15

It’s in there, but the page is kinda hard to use. The full solution page is here:
http://web.archive.org/web/20050407074608/http://www.icparc.ic.ac.uk/~wh/golf/solutions.html

Search for “7 groups of 7 golfers for 7 weeks”, or just scroll down (it’s not that long a page).