1

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.

Community
  • 1
  • 1
matt
  • 1,895
  • 5
  • 19
  • 26
  • '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 Jan 21 '11 at 06:05
  • possible duplicate of [Creating combinations that have no more one intersecting element](http://stackoverflow.com/questions/2955318/creating-combinations-that-have-no-more-one-intersecting-element) –  Jan 21 '11 at 07:18
  • http://en.wikipedia.org/wiki/Block_design is one starting point for the math problem. – mcdowella Jan 21 '11 at 19:26

2 Answers2

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

Kirk Broadhurst
  • 27,836
  • 16
  • 104
  • 169
  • It was possible for 16 people with 4 tables of 4: because 15 is divisible by 3 :) – Joel in Gö Jan 21 '11 at 10:08
  • @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 – Kirk Broadhurst Jan 22 '11 at 05:57
0

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

Catalin Marin
  • 1,252
  • 1
  • 11
  • 18
  • 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. – matt Jan 21 '11 at 22:22