Arrangement in a circle

Twelve politicians are seated at a round table. A committee of five is to be chosen. If each politician, for one reason or another, dislikes their immediate neighbours and refuses to serve on a committee with them, in how many ways can a complete group of five politicians be chosen?

I don’t quite get the solution for this question. We need to use $n(U) = n(A) + n(A^C)$. So say there is $A,B,C,D,E,F,G,H,I,J,K,L$ seated on a round table. Split it up into two cases:

Case $1$: $A$ is chosen: $n(A)$

Since $A$ is sitting next to $B$ and $L$, $B$ and $L$ cannot be chosen in the group of five. So we need to choose $4$ people from $C,D,E,F,G,H,I,J,K$. Up to here I get. The next bit is where I don’t understand: What they did was, since we are choosing $4$ people, and not choosing $5$ people, with the condition that “each politician, for one reason or another, dislikes their immediate neighbours and refuses to serve on a committee with them” Lay out the $5$ ‘not chosen’ people as $N N N N N$ Then there are $^6C_4$ ways of putting the $4$ ‘chosen’ people between the gaps created by the $5$ $N$’s.

I dont understand this. First i’ve never seen this question type before and this method is unfamiliar to me, and I just don’t understand this. Usually when you use the method of putting things between gaps, it is $^6P_4$ not $^6C_4$, and I don’t understand how that method covers for this case.

Case $2$: $A$ is not chosen $n(A^C)$

We are choosing $5$ people from $B,C,D,E,F,G,H,I,J,K,L$. Here, we have $6$ ‘not chosen’ and $5$ ‘chosen’ $N N N N N N $ For this case we have $^7C_5$ ways of placing the ‘chosen’ people between the gaps from similar logic as above. So the final answer is $^6C_4 + ^7C_5 = 36$ ways.

Now I’ve tried other methods before I looked at the answers. I tried to subtract different cases from $^{12}C_5$ but that didn’t work, I tried a lot of things which didn’t work. I appreciate the fact that you need to use the idea $n(U) = n(A) + n(A^C)$ but its frustrating as I don't understand the method, explanation much appreciated.

Solution 1:

Probably the simplest way to do this is to think about what the non-chosen people can look like. There is at least one non-chosen person between each pair of chosen people, so the non-chosen people come in five "blocks", and the total size of the five blocks is $7$. So the blocks are either one block of $3$ and four of $1$, or two blocks of $2$ and three of $1$.

In the first case, there is only one way to arrange one $3$ and four $1$s in cyclic order, and so all that matters is where in the circle the block of $3$ starts. Thus there are $12$ options here.

In the second case, the blocks could be arranged cyclically as $2,2,1,1,1$ or $2,1,2,1,1$. (Other arrangements are just rotations of these two.) Each of these can be rotated to any of $12$ positions, so there are $36$ possibilities in total.

Solution 2:

You can look at it like this.

In the first case you have 9 people

$$ C \space D \space E \space F \space G \space H \space I \space J \space K $$

You need to label each of these 9 people with a $Y$ or a $N$ to mark whether they are chosen ($Y$) or not chosen ($N$). But you have to satisfy the following constraints.

1. There are $5$ $N$'s and $4$ $Y$'s.

2. No two of the $Y$'s are consecutive.

So in other words we need to count the number of sequences of length $9$ consisting of $5$ $N$'s and $4$ $Y$'s and with no consecutive $Y$'s. Such a sequence can be built in two steps.

1. Lay out five $N$'s: $N$ $N$ $N$ $N$ $N$

2. Add $4$ $Y$'s to the sequence. Since no two $Y$'s can be consecutive, this amounts to choosing four of the six gaps between the $N$'s (including endpoints). So this is $6C4$ or ${6\choose 4}$.

Note that $6P4$ will over count since this counts the number of ways of selecting $4$ gaps in which order matters. But in your situation the order of how you choose the gaps between the $N$'s doesn't matter. For example:

1. I choose the first four gaps in this order: $1$ $N$ $2$ $N$ $3$ $N$ $4$ $N$ $N$

2. I choose the first four gaps in a different order: $3$ $N$ $2$ $N$ $4$ $N$ $1$ $N$ $N$

In both cases I have chosen the same four people for the committee: $C$, $E$, $G$, and $I$. So I don't want to view these as different ways of making the committee. This is why we use $6C4$ and not $6P4$.

To see a situation where order does matter, you could imagine that in addition to choosing these four people, we were also going to give them some individual roles. For example the first person will take notes, the second person will organize food for the meeting, the third person will pick a playlist, and the fourth person will send progress updates to the media. In this case, changing the order of the gaps makes an actual difference to how the committee is formed, and so you would use $6P4$. But in your problem no special roles are assigned to the committee members so order doesn't matter.

The same logic applies in the second case.