0
$\begingroup$

There are 20 people around a circular table.We have to choose $3$ of them such that at least $2$ of them are sitting together.In how many ways can this be done?

Number of ways of choosing 3 people sitting adjacent to each other is 20.Number of ways of picking 2 people adjacent to each other is also 20.For each of those latter positions,there are 16 other people to choose from.

Therefore, $\text{Ans:} 20+20\cdot16=340$

In what other ways can this answer be derived?Can we use complementary counting somehow?Is there a better way to visualize what we are trying to compute?

$\endgroup$
2
$\begingroup$

We count the complement. This is less efficient than your way for $3$, but becomes useful for larger numbers.

We first count something else: The number of ways to choose a Committee Chair, and then choose $2$ people to join the Chair, with none of the three people sitting next to each other.

The Chair can be chosen in $20$ ways.

Then we cannot use the two people next to the Chair. That leaves $17$. Write down $15=17-2$ stars, like this: $$\ast\quad \ast\quad\ast\quad\ast\quad\ast\quad\ast\quad \ast\quad\ast\quad\ast\quad\ast\quad\ast\quad \ast\quad\ast\quad\ast\quad\ast$$ This determines $16$ "gaps" (the $14$ ordinary gaps that one can see, plus the $2$ "endgaps"). We will choose $2$ of these gaps to put our chosen people into. This can be done in $\binom{16}{2}$ ways. That gives a total of $(20)\binom{16}{2}$ choices of Committee with Chair, that satisfy the separation condition.

Now let's count the chairless committees that satisfy the separation condition. Each chairless committee has been counted $3$ times, so the required number is $$\frac{(20)\binom{16}{2}}{3}.$$

Remark: This idea works if we have $n$ people, and we want to choose $r$ of them so that no two are adjacent. When we remove the Chair and the two adjacents, we need to write down $(n-3)-(r-1)$ stars, which gives $n-r-1$ "gaps." We choose $r-1$ of them. The same reasoning leads to $$\frac{(n)\binom{n-r-1}{r-1}}{r}.$$

$\endgroup$
2
$\begingroup$

enter image description here

We can generate these by choosing the people in position $1$ (pink), position $2$ (blue) and position $k \in \{3,4,\ldots,19\}$ (one of the orange circles), then rotating cyclically. Since there are no automorphisms under this group action, we find $20 \times 17=340$ choices.

$\endgroup$

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.