Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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: Isn't that the same as saying: When A sits next to B and C, then specialty(A) $\neq$ specialty(B) AND specialty(A) $\neq$ specialty(C). Or less formally: Nobody sits next to somebody with the same speciality. –  moose Aug 22 at 18:38
2  
What is $n$ in your question? –  moose Aug 22 at 18:38
    
Ironically, at the time of this comment, this question has 25 upvotes and Nate's answer has 24 upvotes. –  Ahaan Rungta Aug 23 at 0:41
3  
@moose: no, it says that for any two people A,B sitting anywhere at the table: spec(A) = spec(B) $\rightarrow$ spec(A+) $\neq$ spec(B+), where X+ is the person sitting to the left of X. –  Steve Jessop Aug 23 at 1:40
1  
@AhaanRungta Just out of curiosity, what do you think "ironically" means? –  bof Aug 23 at 21:26

5 Answers 5

up vote 38 down vote accepted

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.

share|improve this answer
5  
wow, you typed THAT in 10 minutes?! thx so much! –  heyhuehei Aug 22 at 0:36
9  
No problem! I'm a very fast typer (110 WPM), so it only took about 8 minutes, and 2 to read it over. –  Nate Lieberman Aug 22 at 0:37
11  
You should be proud of the poured thoughts, not the number of words :D –  justhalf Aug 22 at 6:39

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.

share|improve this answer
1  
Great insight. It's always fun to solve problems by reducing them to known graph-theoretic results. :-) –  templatetypedef Aug 23 at 18:08

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.

share|improve this answer
2  
I think A->(ABB)A... would be clearer, since then the first expansion follows an identical schema as the subsequent expansions. –  Taemyr Aug 22 at 8:26

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$

share|improve this answer

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.

enter image description here

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

share|improve this answer
    
How do you know that 1 points to 2 and so on? I am sure that it does so here, but it's not clear to me how you could be sure starting out that this would work. –  jwg Aug 22 at 20:34
    
The row is the 'current person' and the column is the current person's left neighbour. So a 1 in the 'MM' cell implies an 'M' is sitting next to a 'M'. A 2 in the 'MB' cell implies a 'B' next an 'M'. Given that 1 is followed by 2 (in the integer sequence), the 'M' (left person) in the 1st relationship becomes the 'M' (right person) in the second relationship; this ensures continuity. –  dilbert Aug 22 at 22:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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