3
$\begingroup$

There are $n$ persons sitting around a circular table. Then, in how many different ways 3 persons can be selected if none of them are neighbours.


My approach:-

Let us pretend that we have already picked 3 out of n persons. Now we have to place them with remaining n-3 persons in such a way that none of them are sitting together.

This can be easily done by gap method. There are 4 gaps between 3 persons in a line, xoxoxox , but there are 3 gaps between 3 persons in a circle.

So there are $(n-3)$ gaps for $(n-3)$ persons in a circle. We have to place those chosen $3$ persons in these $(n-3)$ spots. This can be done in $n-3 \choose 3$ ways which is $\frac{1}{6}(n-3)(n-4)(n-5)$. Which should be the answer because we can again pick those three and they fulfil our conditions.

But, The actual answer is $\frac{1}{6}n(n-4)(n-5)$.

The question is How?

$\endgroup$
  • $\begingroup$ The "actual answer" gives $1$ for $n=3$, it seems quite hard to pick three out of three people with none of them being neighbours though... $\endgroup$ – Arthur Dec 16 '14 at 14:35
  • $\begingroup$ idk but it is given in the answer key in the end of the book $\endgroup$ – Dheeraj Kumar Dec 16 '14 at 14:37
  • $\begingroup$ I guess they forgot an assumption like $n >3$. $\endgroup$ – Arthur Dec 16 '14 at 14:37
  • $\begingroup$ well.. it is obvious, because we have to find the no of ways "3 persons can be selected" $\endgroup$ – Dheeraj Kumar Dec 16 '14 at 14:38
  • 3
    $\begingroup$ It seems like you are fixing three persons (in some mysterious way) and then rearranging their seats so that they are not neighbors. This is not what the problem is asking: the position of each person is fixed. $\endgroup$ – Pedro M. Dec 16 '14 at 14:50
2
$\begingroup$

Other people have explained how to get the correct answer, so I will just focus on why your answer is wrong: there is no one-to-one correspondence between the ways to choose three gaps between $n-3$ people and the ways to choose three non-neighbor people out of $n$. Let's call the people in your gaps problem $A_1, \dots, A_{n-3}$, and the people in the original problem $B_1, \dots, B_n$. If you put three additional persons between $A$s, how would you choose which $B$s correspond to them? For example, you can always identify $A_1$ with $B_1$, but then you will only get the ways to choose three $B$s other than $B_1$. So you see that the answer to the gaps problem is smaller than the answer to the original problem.

By the way, since every person (for example, $B_1$) is selected in exactly $\frac 3n$ of all the ways to choose three non-neighboring $B$s, what you should get your way is $1-\frac 3n$ of the correct answer. And this is exactly what you get: $\frac 16(n-3)(n-4)(n-5) = (1-\frac 3n)\cdot \frac 16n(n-4)(n-5)$.

$\endgroup$
3
$\begingroup$

There are $\binom{n}{3}$ ways of choosing $3$ people. But there are $n$ ways of choosing the three people sitting next to each other, and $n(n-4)$ ways of choosing them with 2 sitting together and one alone. Hence, there are in total $$\binom{n}{3}-n-n(n-4)=\frac{1}{6}n(n-4)(n-5)$$ ways of choosing three people such that no two of them are neighbours.

$\endgroup$
  • $\begingroup$ Spenser - Might you be willing to explain the fault in OP's logic? I appreciate this answer but would like to see where the mistake is in the other since it is not yet apparent. $\endgroup$ – 123 Dec 16 '14 at 14:40
1
$\begingroup$

First pick one out which can be done on $n$ ways.

Then picking out two others comes to the same as writing $n-3$ as a sum of $3$ positive integers. Equivalent is writing $n-6$ as a sum of $3$ nonnegative integers and there are $\binom{n-4}{2}=\frac{1}{2}\left(n-5\right)\left(n-4\right)$ ways to do that.

So we seem to end up with $\frac{1}{2}n\left(n-5\right)\left(n-4\right)$ ways. However, each way is counted $3$ times. This because each way offers $3$ possible seats for the person that is picked out first.

Dividing by $3$ repairs that: $$\frac{1}{6}n\left(n-5\right)\left(n-4\right)$$

$\endgroup$
0
$\begingroup$

In your answer you pick $n-3$ seats and count the number of ways to pick three people from these $n-3$ seats. This is completely different from the question! Example: $n = 7$, seats numbered clockwise. You pick seats $1,2,4,6$ and leave $3,5,7$ as gaps. Then you count the configuration $1,2,4$ even though it has neighbours and you don't count $1,3,6$ which has no neighbours.

To find the correct solution, I refer to the other answers here.

$\endgroup$
  • $\begingroup$ I actually tried to place the selected persons in the gaps between those n-3 persons $\endgroup$ – Dheeraj Kumar Dec 16 '14 at 14:54
  • $\begingroup$ You are talking about $n-3$ gaps in your answer. Those are the $n-3$ seats I'm referring to. $\endgroup$ – Arthur Dec 16 '14 at 14:57
  • $\begingroup$ suppose if there are three persons we have to seat two other persons so that they are not together we can do this by placing them in the four gaps between three already seated persons. ie o_o_o $\endgroup$ – Dheeraj Kumar Dec 16 '14 at 14:59
  • $\begingroup$ Check my example again. $n = 7$ and we have __o_o_o. But there are ways to put the three people on only _ spots and still have them be neighbours. $\endgroup$ – Arthur Dec 16 '14 at 15:03
0
$\begingroup$

You have $n$ ways to choose person 1. For example if $n=13$, pick one person: 0000001000000. Then there are two choices sitting one away from him, as in either 0000201000000 or 0000001020000. After picking one of those, there are five spaces you cannot pick so finally you are left with $n-5$ choices for the third person: 3330201033333. But if you choose the second person sitting two seats away from the first person, you have $n-5$ choices for the second person 2222001002222 and then you have $n-6$ choices for the third person: 3302001033333. That covers both the cases. In equations: $$ \begin{align} n\times[2\times(n-5)+(n-5)\times(n-6)]&=n\times(n-5)\times(n-6+2)\\ &=n\times(n-4)\times(n-5) \end{align} $$ Then divide by six for the duplicates.

$\endgroup$
  • $\begingroup$ your answer is correct, but how is my answer wrong. $\endgroup$ – Dheeraj Kumar Dec 16 '14 at 14:43
  • $\begingroup$ @DheerajKumar Sorry I looked at your answer and spotted the error then tried to work it out myself. I got to the above then forgot what exactly it was I thought was wrong! I am sorry. $\endgroup$ – Suzu Hirose Dec 16 '14 at 14:51
  • $\begingroup$ i have figure out what the problem was with my solution I was not considering that the order in which the persons are sitting is already fixed. $\endgroup$ – Dheeraj Kumar Dec 16 '14 at 14:57

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.