# How to solve “ways of seating around a circular table”

The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with chairs numbered from $1$ ￼ to ￼$15$ in clockwise order. Committee rules state that a Martian must occupy chair ￼1 and an Earthling must occupy chair 15￼ . Furthermore, no Earthling can sit immediately to the left of a Martian, no Martian can sit immediately to the left of a Venusian, and no Venusian can sit immediately to the left of an Earthling. The number of possible seating arrangements for the committee is $N(5!)^3$￼ . Find $N$ ￼ .

All I am asking is how to solve these types of problems, I have seen a complicated answer on the linked thread I don't understand one bit, but I am interested.

I know for example in this one there are $5!$ ways to arrange (distinct) people in one race (selected).

But then what do I do? This is the type of general question I am asking.

Not Possible: $EM, MV, VE$.

But $5!$ already implies that you have groups one race together so:

It is only: $EEEEE$ no $MEEEE$ for example.

In general what is a tactic?

• Your statement: Not Possible: $EM, MV, VE$ is a good start. You have turned a lengthy and cumbersome textual problem description into a compact symbolic representation. This is the key to many maths problems. – Colm Bhandal Jul 24 '15 at 17:41
• The intuition behind the $(5!)^3$ is as follows. Suppose you have a valid seating arrangement. Then you can always swap all the martians, and you still remain with a valid arragement. You can also swap all the earthlings, and all the Venusians. So any combination of swaps keeps you in the space of valid arrangements. Hence the factor of $(5!)^3 = 5! \times 5! \times 5!$. – Colm Bhandal Jul 24 '15 at 17:44

The $(5!)^3$ is taking into account the ordering of the 5 people for each particular race, regardless of what their particular assigned chairs are. So this problem is asking for the number of ways to simply write down the race of each member in each chair such that each race is used 5 times, and the rules are followed. It becomes easier when the first and last chairs are specified, because this makes it a linear arrangement problem instead of a circular one. This problem is a bit tricky because you have to use each race exactly 5 times. There are other problems, such as "use however many of each race you want, but no $k$ people of the same race can sit in a row", for say, $k=2$ or $k=3$, or even closer to your problem, counting the number of ways to seat people if you're allowed to use any number of each race but the "immediate left" rule has to be followed. Those can be attacked by recursion on the total number of seats. I believe the answer given to you in your previous question is probably the best way to go for this tricky problem, and if you'd like, I can try to explain that answer a little further. But you asked a more general question, seems like "What if we have to seat $n$ people either in a row or in a circle such that..." and I'm giving a partial answer, namely for certain such problems you can define a possibly multi-variate recursion each time you add one more seat, that you can then simplify and either work through by hand or solve analytically, especially for linear arrangements of seats.

Based on the constraints for your original problem, any valid assignment has to happen in concatenated blocks of the form $M^xV^yE^z$, where $x,y,z$ are all positive integers, (and M,V,E are symbols representing the races in the seats, and e.g. $M^x$ means you have $x$ occurrences of M in a row), because of the rules of seating as well as the specified first and last seat assignments. You can have any of $k=1,2,3,4,5$ total such blocks. Let's say you have $k$ blocks ($1 \leq k \leq 5$). Then let $x_i,y_i,z_i$ be the assigned values for the $i$th block ($1 \leq i \leq k$). Then the only remaining freedoms in the assignment are the ways you can set the $x_i$ to satisfy $\sum_{i=1}^k x_i = 5$, and similarly for $y_i$ and $z_i$, keeping in mind that all variables have to be positive integers. You can use "stars and bars" technique (you can find online) to find the number of distinct solutions for the $x_i$, and this will be the same as the number of solutions for the $y_i$, and also for the $z_i$. So let $C_k$ be the number of solutions for the $x_i$ when you have $k$ blocks. Then the total number of solutions for the $x_i,y_i,z_i$ is $C_k^3$ when you have $k$ blocks. Thus your desired value of $N$ in the original question is $\sum_{k=1}^5 C_k^3$. Since $k$ is only between $1$ and $5$, and $k=1$ and $k=5$ are trivial, you only have 3 non-trivial cases to work out with stars and bars, and then you're done.

• Please do! Please explain that answer, the notation, wording everything there is very confusing (+1) – Amad27 Jul 24 '15 at 18:56
1. Find all the strings of length $15$ starting with $M$, ending with $E$, and containing neither $EM$, $MV$ or $VE$.
2. Multiply the above number by $(5!)^3$ to account for any "internal" rearrangements of the earthlins, martians and venusians.
But then the first number is clearly $N$. So you just need to solve the first step. The problem is converted to a problem on strings. You now don't need to worry about internal arrangements of the races. You just care about what race is sitting in what position.
• Agreed- that is the difficult part of the problem. How do we count all strings starting with $M$, ending with $E$ and containing $5$ of each $E$, $V$ and $M$ in total, that also avoid the three disallowed combinations $EM$, $MV$ and $VE$. Do you have any ideas of how you would go about doing this? How about if there were only two of each race? Could you solve that simpler case ? – Colm Bhandal Jul 25 '15 at 11:04