1

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?

Paul
  • 113

2 Answers2

0

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. ;-)

Joffan
  • 39,627
0

Analysis with Python shows that rule 1 is impossible to satisfy and furthermore for any valid schedule, if the schedule satisfies rule 2 then it must have 12 unique pairings (out of 15). I.e. all schedules satisfying rule 2 are equally good alternatives. I would image that the relationship is an iff since allowing more non-unique pairings would decrease the number of unique pairings, but did not check it going the other way. 

import itertools

persons = [0, 1, 2, 3, 4, 5]
possible_tables = list(itertools.combinations(persons, 3))
possible_arrangements = list(itertools.combinations(possible_tables, 2))

def valid_arrangement(table1, table2):
    for person in table1:
        if person in table2:
            return False
    return True

def generate_schedules(arrangements):
    possible_schedules = []
    for i in arrangements:
        for j in arrangements:
            for k in arrangements:
                possible_schedules.append([i, j, k])
    return possible_schedules

valid_arrangements = [a for a in possible_arrangements if valid_arrangement(*a)]
possible_schedules = generate_schedules(valid_arrangements)

def generate_meetings(arrangement):
    meetings = []
    for table in arrangement:
        meetings += [(table[0], table[1]), (table[0], table[2]), (table[1], table[2])]
    return meetings

def evaluate_schedule(schedule):
    unique_meetings = 0
    met = {}
    for arrangement in schedule:
        for pair in generate_meetings(arrangement):
            if pair[0] > pair[1]:
                pair = pair[::-1]

            if pair in met:
                met[pair] += 1
            else:
                met[pair] = 1

    for v in met.values():
        if v > 2:
            return
        else:
            unique_meetings += 1

    print("Found valid schedule with " + str(unique_meetings) + " unique meetings: ")
    print(schedule)
    print(met)

    #if unique_meetings != 12:
    #   print("Found valid schedule with != 12 unique meetings")

for s in possible_schedules:
    evaluate_schedule(s)
yeons
  • 295