I like to make a rotation schedule for a dinner party where everyone is new, so the idea is that everyone gets a chance to meet as many new people as possible.
Setup:
I have 6 persons attending (lets name them A to F).
I have 2 locations (tables) with each location able to seat 3 persons.
3 rounds are held (so we switch places 2 times).
Rules:
Each person sits together with every person at least once.
Each person sits together with someone for at most two times.
Example of round 1:
Table 1: A B C
Table 2: D E F
Now I tried several combinations but I keep ending up with people not sitting together in any round. Like this faulty try:
A B C
D E F
A D E
B C F
A F E
B C D
Any good way to make a schedule?
PS: Now if it is impossible to have everyone sit with each other, what is the closest alternative to it?
Best Answer
It is impossible, as illustrated in your attempt in the question, which also represent one kind of as-near-as-possible attempt.
Consider A. There are five other people to sit with, so the groupings for A can be ABC, ADE, AFX where X is to be determined.
However this forces the other table on the first two occasions to be DEF and BCF. This means that both B and C have never sat with either D or E, and we cannot fulfill that in one sitting. One of the four has to sit with AF, which means that person will have missed out on sitting with two different people.
We could aim to arrange things so that no-one misses out on more than one pairing:
$\begin{array}{c} ABC & DEF \\ ABD & CEF \\ ACE & BDF \\ \end{array}$
In this version everyone misses out on sitting with exactly one person.
In terms of graph theory, this should be related to some sort of clique edge cover problem (depending on the size of the set and the tables). Here we're looking to cover as many edges as possible with a set of disjoint $K_3$ covers of $K_6$.
I like playing with words also, so I attempted to name your characters...they are now Abe, Bea, Ced, Dee, Edd and Fae. ;-)