Recently I asked a question about seating, here it is again:

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?

  • $\begingroup$ 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. $\endgroup$ – Colm Bhandal Jul 24 '15 at 17:41
  • 1
    $\begingroup$ 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!$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Please do! Please explain that answer, the notation, wording everything there is very confusing (+1) $\endgroup$ – Amad27 Jul 24 '15 at 18:56
  • $\begingroup$ Please help here! $\endgroup$ – Amad27 Jul 24 '15 at 21:13
  • $\begingroup$ @Amad27 I answered this on a work break and I'm now on my way home. Hopefully I'll have time tonight to give a good detailed explanation of that answer to your original question. Sorry for the delay. Maybe someone else can post the explanation as an answer too, before I do, in case it takes me a while to get to it. $\endgroup$ – user2566092 Jul 24 '15 at 22:09
  • $\begingroup$ Ok I'll wait thanks! $\endgroup$ – Amad27 Jul 25 '15 at 7:14
  • $\begingroup$ @Amad27 Sorry it took a while, but hopefully now you can understand the up-voted answer to your original question. Let me know if anything is unclear. $\endgroup$ – user2566092 Jul 26 '15 at 13:43

To find the total number of arragements you can do the following.

  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.

| cite | improve this answer | |
  • $\begingroup$ There is one more complication: You have to use each symbol exactly 5 times when you are trying to exclude EM,MV, and VE. $\endgroup$ – user2566092 Jul 24 '15 at 17:52
  • $\begingroup$ 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 ? $\endgroup$ – Colm Bhandal Jul 25 '15 at 11:04

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.