CODEWITHSUNDEEP
algorithmmathconstraints
matt
matt

Reputation: 1915

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

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.

Upvotes: 1

Views: 416

Answers (2)

Catalin Marin
Catalin Marin

Reputation: 1242

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

Upvotes: 0

Kirk Broadhurst
Kirk Broadhurst

Reputation: 28698

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

Upvotes: 4

Related Questions