seating arrangement so nobody meets twice

[SusanS]

Hi,

There are 36 people, who will meet on 7 different evenings, and sit at tables for 6. That is 6 tables of 6 people each, every evening for 7 evenings.
Is it possible to arrange the seating so that each person will share a table with 5 new people every evening? So that by the end of the 7th evening, every person has sat with every other person?

Seems to me, it should be possible, because after 7 evenings, each person will have met (7 evenings time 5 new people) = 35 people. But is there some way to use excel to arrange them, or if not possible, then to have excel return an error?

I was thinking set up each evening as a 6 rows by 6 columns square, where each row would be one table. But I'm stumped how to proceed. I'm now able to set up 3 evenings. But those aren't necessarily the correct arrangements that will allow all 7 evenings to work. I think there's only one right answer.

Here's why theoretically seems to me it should work. Each table would have combin(6,2) = 15 unique pairs. There are 36 people so there are combin(36,2) = 630 unique pairs in total. 630 pairs/15 pairs per table = 42 tables. 7 evenings should do it perfectly.

Occurrs to me that this could be a 6/36 lottery question where someone wants to buy 42 tickets which collectively contain every unique pair from 1 to 36.

Using Windows 7, and Excel 2003. Any ideas how to proceed?
...Susan

 

[RSXchin]

Why does this sound like a homework assignment...?

 

[shg]

I think you have a tiger by the tail. There's an article on the web on the topic by two profs at Cal State Fullerton; Google Solving the Repeated Partition Scheduling Problem Using Metaheuristics

 

[SusanS]

LOL RsChin It DOES rather sound like a homework assignment! But I assure you it's not.


Shg4421 I did a quick search just to find definitions of metaheuristic - haven't actually read the article yet - Gawd it looks complicated! Travelling salesmen! Ant colonies! Guess this means there's no quick VBA macro for this. )

.....Susan

 

[shg]

I tried to do something almost identical a few years ago (arrange play dates for N kids in groups of M over a period of weeks with no repeat pairings) and was suprised to find that the class of problems is so complex.

 

[RSXchin]

well... if you do figure out how to do this. I have a similar, and much lamer, problem.

There is a video game called "Marvel Ultimate Alliance 2". And it has an achievement for performing a special move with every pair of 24 heroes. The team always must have 4 members.

What is the most efficient method of pairing?

The names of the heroes are:

CAPTAIN AMERICA
DAREDEVIL
DEADPOOL
GAMBIT
GREEN GOBLIN
HULK
HUMAN TORCH
ICEMAN
INVISIBLE WOMAN
IRON FIST
IRON MAN
JEAN GREY
LUKE CAGE
MR. FANTASTIC
MS. MARVEL
NICK FURY
PENANCE
SONGBIRD
SPIDER-MAN
STORM
THING
THOR
VENOM
WOLVERINE

Told you it was lame...
</pre>

 

[SusanS]

But I'm not trying to write a paper. I'm only learning VBA, without a programming background. This is a special case where the square root of the total number of people (n = 36) is equal to the number of chairs at each table (ie 6).

Here's the solution if there are 9 people at 3 tables for 3:
First evening:
1 2 3
4 5 6
7 8 9

Second evening
1 4 7
2 5 8
3 6 9

Third evening
1 5 9
2 6 7
3 4 8

fourth evening
1 6 8
2 4 9
3 5 7

It seems the number of arrays needed (ie the number of evenings) is always one more than the length of a side of an array.
And here's the solution if there are 16 people at 4 tables for 4:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

1 6 11 16
2 5 12 15
3 8 9 14
4 7 10 13

1 7 12 14
2 8 11 13
3 5 10 16
4 6 9 15

1 8 10 15
2 7 9 16
3 6 12 13
4 5 11 14
Also note that in all the arrarys after the first 2 arrays, the sum of the numbers in each row is constant. I figured that, in the VBA code, there would be several nested loops about if one cell value equals another,
then try the next combination of 6 cells from a list. Note that (for an array of 6 x 6) that each row, after the first 2 rows, would equal 111, that is in my specific question for arrays of 6 x 6. That doesn't have to be built into the code of course, but that fact might make it easier to create the code. This also might make the code easier - that each column (except the first array) consists of the same 6 numbers. (Hope that makes
sense.)
The code doesn't have to build the first 2 arrays, only the last 5. The first 2 would be:
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

1 7 13 19 25 31
2 8 14 20 26 32
3 9 15 21 27 33
4 10 16 22 28 34
5 11 17 23 29 35
6 12 18 24 30 36

RSxChin if you had only 16 heroes, 4 to a team, it would be solved above. But for 24 heros I'm clueless. Good luck. Maybe my observations will help.

Again, it would be great if someone could point me in the right direction. I really think there's gotta be a solution for this special case. Thanks again.

.....Susan

 

[rsulliva]

According to my calculations, actually everyone meets only once after 6 days. The 7th day would be a repeat of day 1. Tables are in columns.


TB1 TB2 TB3 TB4 TB5 TB6
Day 1
1a 1b 1c 1d 1e 1f
2a 2b 2c 2d 2e 2f
3a 3b 3c 3d 3e 3f
4a 4b 4c 4d 4e 4f
5a 5b 5c 5d 5e 5f
6a 6b 6c 6d 6e 6f

Day 2
1a 1b 1c 1d 1e 1f
2b 2c 2d 2e 2f 2a
3c 3d 3e 3f 3a 3b
4d 4e 4f 4a 4b 4c
5e 5f 5a 5b 5c 5d
6f 6a 6b 6c 6d 6e

Day 3
1a 1b 1c 1d 1e 1f
2c 2d 2e 2f 2a 2b
3d 3e 3f 3a 3b 3c
4e 4f 4a 4b 4c 4d
5f 5a 5b 5c 5d 5e
6b 6c 6d 6e 6f 6a

Day 4
1a 1b 1c 1d 1e 1f
2d 2e 2f 2a 2b 2c
3e 3f 3a 3b 3c 3d
4f 4a 4b 4c 4d 4e
5b 5c 5d 5e 5f 5a
6c 6d 6e 6f 6a 6b

Day 5
1a 1b 1c 1d 1e 1f
2e 2f 2a 2b 2c 2d
3f 3a 3b 3c 3d 3e
4b 4c 4d 4e 4f 4a
5c 5d 5e 5f 5a 5b
6d 6e 6f 6a 6b 6c

Day 6
1a 1b 1c 1d 1e 1f
2f 2a 2b 2c 2d 2e
3b 3c 3d 3e 3f 3a
4c 4d 4e 4f 4a 4b
5d 5e 5f 5a 5b 5c
6e 6f 6a 6b 6c 6d

 

[RSXchin]

Do you have a way of using vb to do that?

 

[rsulliva]

No VBA, just used a little brain power.