A group combination and constraint solving problem. What algorithm can I use?

Question

This problems feels like it should have a name. Hopefully someone can recognize it.

There is a 32 member club. Every week the members have dinner together, dividing themselves into 8 tables of 4 members each. Each week they arrange themselves such that they are always sitting with different people.

Is it possible to have every person be seated with every other person exactly once?

I've tried programming a greedy approach, but it didn't work for these numbers (it did work for a 16 member club with 4 tables of 4 each, but not 36 members with 6 tables of 6 people)

Though this sounds like a homework problem, this is actually from my friend's mom, who is trying to organize these dinners.

'from my friend's mom', that's great! This is really a math problem so better suited to math.stackexchange.com, but you'll probably get an answer here. — Kirk Broadhurst
– Kirk Broadhurst, Commented Jan 21, 2011 at 6:05
possible duplicate of Creating combinations that have no more one intersecting element — Aryabhatta
– Aryabhatta, Commented Jan 21, 2011 at 7:18
en.wikipedia.org/wiki/Block_design is one starting point for the math problem. — mcdowella
– mcdowella, Commented Jan 21, 2011 at 19:26

Kirk Broadhurst · Accepted Answer · 2011-01-21 06:08:13Z

4

There are 32 people in the group, so you need to have dinner with the other 31 people.

Therefore, no you cannot have dinner with every other person exactly once.

31 is a prime number. You have to have dinner with 3 people at a time, as there are 4 to a table. It's not possible to have dinner with 31 people, 3 people at a time, without repeating or skipping anyone. (31 is not divisible by 3).

QED

answered Jan 21, 2011 at 6:08

Kirk Broadhurst

28.9k20 gold badges111 silver badges179 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Joel in Gö Over a year ago

It was possible for 16 people with 4 tables of 4: because 15 is divisible by 3 :)

Kirk Broadhurst Over a year ago

@Joel Yes, same for 36 people (35 divisible by 5); but you'd need a more rigourous proof than that ;) There is probably more to it - this divisibility pattern is necessary but not be sufficient

Catalin Marin · Accepted Answer · 2011-01-21 12:43:48Z

0

Then go for backtracking this will give you all the possible combinations.

answered Jan 21, 2011 at 12:43

Catalin Marin

1,2421 gold badge11 silver badges19 bronze badges

1 Comment

matt Over a year ago

I assume this would lead to an unfeasibly large compute time given n=32. If Kirk hadn't proved the problem impossible I would have tried though.

Collectives™ on Stack Overflow

A group combination and constraint solving problem. What algorithm can I use?

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related