Rational Solver
0 votes
$20$ persons are sitting around a table. How many ways can we choose $3$ persons, no two of whom are neighbours?
in Discrete Mathematics by Expert | 12 views

1 Answer

0 votes
Best answer

Have you tried this question? If not then do not see the answer, instead, first, try this beautiful problem and understand why $20\times (20-3)\times (20-3-3)$ can't be the correct answer? This is not the correct answer as choosing the third person will depend on the sitting position of the second person. This indicates that we have to divide our answer into two parts depending on the seating position of the second person. 

Let us assume $P_1$ , $P_2$, and $P_3$ are chosen tree person. Note that for the first person $P_1$ we can choose any one of them and so for $P_1$ we have total $20$ choices. Now there are two way we can choose our second person $P_2$. 

  1. $P_2$ sits just $1$ seat away from $P_1$. In this case we will have only $2$ options. 
  2. $P_2$ sits more than $1$ seat way from $P_1$. In this case we can choose $P_2$ in $20-5=15$ ways. 

Now depending on the seating position of $P_2$  we can choose our third-person $P_3$:

  1. If $P_2$ sits just $1$ seat away from $P_1$ then  $P_1$ and $P_2$ has a common neighbours. Therefore, $P_3$ can't be $P_1$, $P_2$ and their neighbours. So for $P_3$ we have $20-2-3=15$ choices. 
  2. If $P_2$ sits more than $1$ seat way from $P_1$. In this case $P_3$ can' be $P_1$ or $P_2$ or their immediate neighbours. So we can choose $P_3$ in $20-2-2\times 2=14$ ways.

By applying the rule of sum and product, we get the total number of choices athat re  

$$(20\times 2\times 15) + (20\times 15\times 14)$$

Is the above answer is correct? No. because we are overcounting as our counts depend choice on people three-person on the order of choosing of the three person. That is we are counting the permutation without repetition. Therefore, a number of choices are $$\frac{(20\times 2\times 15) + (20\times 15\times 14)}{3}=800.$$

by Expert
edited by
Welcome to Rational Solver, where you can ask questions and receive answers from other members of the community.
64 questions
22 answers
1,801 users