5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Note that each seating puts a person next to two others. But you ask for everyone to sit next to "every other person just once". Since there are 29 people that one would need to sit by, "just once" is unachievable (because 29 is not an even number). $\endgroup$ – hardmath Jun 1 '15 at 18:54
  • 1
    $\begingroup$ A problem such as this can be treated as a "graph covering" problem. That is, consider the complete graph $K_{30}$ whose edges correspond to all the pairings we want to attain in some seating. A seating consists of three disjoint ten-cycles $C_{10}$ to be imbedded in the complete graph. Clearly some minimum number of seatings/imbeddings of triple $10$-cycles will suffice to cover $K_{30}$, and that is what we are asked to find. $\endgroup$ – hardmath Jun 2 '15 at 0:41
  • $\begingroup$ @hardmath - Thanks for your comments. Yes, in this case the limiting constraint would be "at least once". The floor for the number of seating configurations required would be 15. $\endgroup$ – hypergeometric Jun 2 '15 at 14:30
  • $\begingroup$ This problem has gone a bit quiet. @hardmath - as you have expertise in graph theory, given your comments, would you be kind enough to work out and post the solution? $\endgroup$ – hypergeometric Jun 13 '15 at 6:47
  • $\begingroup$ So far we have worked out the lower bound of 15 seatings. There is an upper bound of 29 seatings that uses a little graph theory. While the problem interests me, and I have viewed it every few days to see if anyone has posted, I doubt my ability to find the optimal answer in short order. If you have some references for multi-table problems with equal sizes, this would make a good addition to the Question. $\endgroup$ – hardmath Jun 13 '15 at 12:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for posting a solution! Will go through it carefully and also await the diagram. $\endgroup$ – hypergeometric Jun 14 '15 at 16:24
  • $\begingroup$ I added a quick and dirty "diagram" posting from my phone on the road. $\endgroup$ – hardmath Jun 14 '15 at 16:30
  • $\begingroup$ Thanks for taking the time to work out a solution. (+1) $\endgroup$ – hypergeometric Jun 14 '15 at 16:35
  • $\begingroup$ It's a very logical approach and it's also very well-explained without using any graph theory technicalities. I've accepted the answer. Thanks! $\endgroup$ – hypergeometric Jun 16 '15 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.