There are $30$ people at an alumni dinner, seated at $3$ round tables of $10$ seats each.
After every time interval $\Delta t$, a position change event is required where everyone changes position simultaneously, in order to have the opportunity to sit next to someone different on his/her left and right. This results in a different seating configuration.
What is the minimum number of seating configurations (i.e. number of position change events $+1$) required for everyone to have sat next to every other person just once?
NB – If this is not possible then the last condition can be modified from “just once” to “at least once”, but please specify accordingly.
I tried to work this out for a smaller number $n$ of up to $10$ people, seated only on $1$ table, and found that the minimum number of configurations is $\displaystyle\bigg\lfloor\frac n2\bigg\rfloor$.
However, it gets complicated when there are different tables.
This is an example of the Oberwolfach problem, and various papers and articles on this are available on the web, most of them dealing with generalized cases and require a fairly good understanding of graph theory.
It would be appreciated if anyone could derive a user-friendly solution to the question in this particular case.
Best Answer
The Comments above note a lower bound of 15 on the seatings of 30 people at three tables of 10, so that every pair is seated next to each other.
An upper bound of 29 for the minimum number of seatings to achieve this is also mentioned in the Comments. We give an improved upper bound by constructing an 18 seating solution.
Let the 30 participants be partitioned into six subgroups of 5 people each. We will devote 3 seatings to cover all "intramural" pairings (pairs within a subgroup) and 15 seatings to cover all "extramural" pairings (pairs across distinct subgroups).
Intramural pairings
Assign half the circumference of a table to seating a subgroup of five people. Each pair in this subgroup can covered in three seatings, as illustrated by the following labels 1 to 5:
$$ \cdots 1 2 3 4 5 \cdots $$
$$ \cdots 3 1 5 2 4 \cdots $$
$$ \cdots 1 4 2 3 5 \cdots $$
Of course we would do this for all six subgroups in parallel since we have six halves of the three tables to work with. So 3 seatings suffice to cover all intramural pairings.
Extramural pairings
To cover all pairs between participants in distinct subgroups, begin by partioning pairing between subgroups. In a seating we will alternate people from two subgroups around each table. There are three tables, so we partition the 15 pairs of subgroups into five subsets of 3 subgroup pairs.
Each pair of subgroups can be covered with three seatings as we illustrate with labels 1 to 5 for one subgroup and A to E for another. These three lines are meant to wrap around a table:
$$ \cdots 1 A 2 B 3 C 4 D 5 E 1 \cdots $$
$$ \cdots 1 D 2 E 3 A 4 B 5 C 1 \cdots $$
$$ \cdots 1 B 2 C 3 D 4 E 5 A 1 \cdots $$
So all the extramural pairings can be covered in three times five or 15 seatings.