This is an exercise from this book.
9. The president of the Math and Computer Club would like to arrange a meeting with six attendees, the president included. There will be
three computer science majors and three math majors at the meeting. How many ways can the six people be seated at a circular table if the president does not want people with the same majors to sit next to one other?
I understood this to mean that the ordering should not be such that there are 2 consecutive elements that are absolutely next to each other. More precisely, if we have a set
$$S = \{c_1, c_2, c_3, m_1, m_2, m_3\}$$
where $c_1$, $c_2$ and $c_3$ are computer science majors and $m_1$, $m_2$ and $m_3$ are math majors. Then, an order such as
$$\{c_1, c_3, m_1, c_2, m_2, m_3\}$$
is an invalid order because there are elements with the same majors next to each other such as
$$\{c_1, c_3\}.$$
On the other hand, an order such as
$$\{c_1, m_1, c_2, m_2, c_3, m_3\}$$
is valid because there are no 2 elements with the same major. In general, it appears that we should count the ways to order the elements such that the computer science majors and math majors are interchanged in the set. Here are my attempt to count the ways:
- For position 1, we have $6$ choices. So we have $6$ initial ways.
- For position 2, we have $6-3$ choices because all elements with the major similar to the first position are eliminated. Thus we now have
$$6(6-3) = 18$$
ways. - For position 3, we have $6-3-1$ ways because the first choice should not be repeated. This accounts for the first major in every set. Thus we now have
$$18(6-3-1) = 36$$
ways. - For position 4, we repeat the process for position 3 to account for the second major in every set. Thus we now have
$$36(6-3-1) = 72$$
ways. - For position 5, we have $6-3-2$ ways. Same reasoning with position 3 and 4. This accounts for the first major in every set. We still have $72$ ways.
- For position 6, same with position 5. This accounts for the second major of every set.
Using the steps above, I think that there are $72$ ways to sit if the president does not want people with the same majors to sit next to one other. However, the answer in the exercise is too far from what I came up with. The answer is:
$$2P(3,3) = 12$$
I completely do not understand how this answer is derived. It seems that I completely misinterpreted the problem. Can anyone explain what I am doing wrong?
Best Answer
Your steps are fine but the issue here is you did not take into account of the fact that the $6$ people are sitted in a circle. Assuming that the chairs are not numbered (or any thing that make them distinguishable), given a particular arrangement, the relative positions of the $6$ people would not change if you were to rotate them. For a given arrangement, there are $6$ of such rotations and so if you were to divide your answer by $6$, you would obtain the correct answer.