Prove that the 25 people can be seated in this way

Question

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table.

Prove that the 25 people can be seated such that, if A and B are two different people with the same specialty (for example, two mathematicians), then the people sitting to the immediate left of A and to the immediate left of B are of different specialties (for example, a biologist and a chemist).

I thought to use induction, since $n=1$ and $n=2$ are easy to do. However, I don't know how to continue.

Answer 1

We prove this generalization: If there are $n$ people each of $n$ different specialties, then the $n^2$ people can be seated around a round table such that, if $A$ and $B$ are two different people with the same specialty, then the people sitting to the immediate left of A and to the immediate left of $B$ are of different specialties. (Our problem is the case $n=5$.)

If $n=1$, then there is only one person, so the statement we're trying to prove is trivial. If $n=2$, then there are two people in each of two specialties. They can be seated so that both pairs of people of the same specialty are next to each other; this seating satisfies the requirements of the problem. We now continue by induction.

Suppose that we can seat $n$ people in each of $n$ specialties according to the conditions of the problem. Now consider the problem with $n+1$ people in each of $n+1$ specialties. To our existing $n$-specialty seating, we need to add $1$ additional person from each of the original $n$ specialties, plus $n+1$ people from the new specialty, which we'll call $Z$.

Let $S$ be one of the original $n$ specialties, and consider the left neighbors of the original $n$ people from $S$. Those neighbors must all have different specialties (among the original $n$ specialties), so among them there must be exactly one from each original specialty, including S itself. Thus there must be a pair of specialists in $S$ in adjacent seats. We seat the $(n+1)^{\text{th}}$ person from $S$ and one person from $Z$ (in either order) between the adjacent pair of people from $S$. We have thereby put a specialty-$Z$ person to the left of a specialty-$S$ person, and a specialty-$S$ person to the left of a specialty-$Z$ person; this is all we've done. So, it's still the case that no two people from the same specialty have people from the same specialty as their neighbors to the left. We repeat this operation for all $n$ choices of specialty $S$.

Finally, we need to add the $(n+1)^{\text{th}}$ specialty-$Z$ person. We can simply seat her next to any other specialty-$Z$ person. By construction, all the specialty-$Z$ people will have left neighbors of different specialties.

As an example, in our problem, we have $5$ people each of specialties M,B,C,P, and E. We can iterate the above process as follows, where the lists below are thought of as starting at some point on the table and going clockwise:

$\begin{align} M \\MMBB \\ MMCCMBBCB\\ MMPPMCCPCMBBPBCB\\MMEEMPPEPMCCECPCMBBEBPBCB \end{align}$

Note that in each list, no letter pair appears twice in the sequence.

Answer 2

It's a graph theory problem. What you're looking for is an Eulerian circuit in a complete directed graph of order $5$, consisting of five vertices $M,B,C,P,E$ and $25$ directed edges, one going from every vertex to every other vertex and also one looping from each vertex to itself. The existence of an Eulerian circuit (i.e. traversing each edge exactly once) in your graph is easily shown; see the answer to this question.

For generalizations look up De Bruijn sequence.

Answer 3

You can construct a solution by induction. Assume you have a solution for $n$. There are $n$ doubles- put an $n+1$ between each pair and two of them in one of the spaces. Now all of $1$ to $n$ have the required neighbors except themselves so double one of each. So starting from $1221$ we go to $1233213$ and then to $112233213$ The next one is then to $141242344213$ and to $114122423344213$

Answer 4

An inductive proof can be made according to the following schema:

$$A\to A(ABB)\to A(ACBCC)(ABB)\to A(ADBDCDD)(ACBCC)(ABB)\to A(AEBECEDEE)(ADBDCDD)(ACBCC)(ABB)$$

At each stage you have $n$ people of $n$ types, with all $n^2$ possible consecutive pairs.

Answer 5

Given that there are 5 types of person, each of whom sits to the left (or right) of ONE other person, this relationship can be shown as a square (person by neighbour). Also, the seating is going to be a continuous sequence where the 'left' person of the current pair will be the 'right' person of the next pair.

Each neighbour relationship can be numbered 1 to 25. Provided a relationship has a unique number and points to another valid relationship (exception being made for the last relationship of course), then the system is valid.

M M B C P E B P M E C B B E E M C C E P P C M P B M