Selecting 3 persons sitting round a table

1. May 18, 2013

Saitama

1. The problem statement, all variables and given/known data
There are n persons sitting round a table. Prove that the number of different ways in which 3 persons can be selected so that no two are neighbours is $\frac{1}{6}n(n-4)(n-5)$.

2. Relevant equations

3. The attempt at a solution
I don't really know how to tackle this problem. I started with considering a simpler case first. Let the number of persons be 6.

We select one person from 6. Then according to given condition, we cannot select the two persons sitting just next to our selected person. So the other two must be selected from the remaining three. We have to subtract the cases when two nearby persons are selected when we selected two persons from the remaining three. Hence, number of cases=6C1*3C2-2=16, but this wrong because if we substitute 6 in the given formula (which we have to prove), it gives 2.

Any help is appreciated. Thanks! :)

2. May 18, 2013

Staff: Mentor

With 6 persons (ABCDEF), and if the order does not matter, you just have two options: ACE and BDF.

6C1*(3C2-2)=6 - if you take into account that 3 choices of the first person will lead to the same set, you get the correct result of 6/3=2. That is a complicated way to calculate it, however.

You could consider the problem with 1 person and with 2 persons, first.

3. May 18, 2013

Saitama

The number of cases are zero for n=1 to 5.

4. May 18, 2013

Staff: Mentor

Real sets: ACE, BDF, in total 2 sets.
What you select: A+(CE), B+(DF), ..., F+(BD) in total 6 sets. You count each solution three times.

I mean the number of possibilities to select 1 (or 2) out of some general number n.

5. May 18, 2013

Saitama

I am still trying to understand this, meanwhile I will try the other questions you asked me.

To select one person, number of cases equals nC1.

For two persons, it is nC2. Are these correct?

6. May 18, 2013

Staff: Mentor

It is correct for 1 person, but not for 2. Don't forget that the 2 cannot sit next to each other.

7. May 18, 2013

Saitama

Is it nC2-n?

8. May 18, 2013

Staff: Mentor

That is right.
I think would choose a different approach (begin with the case "select 1 person" and develop "select 2 persons" based on that), otherwise it could be tricky (but possible) to extend this to 3 persons.

9. May 18, 2013

Saitama

I am still not sure how would I do it for three persons.

When three persons are selected without restriction, cases are nC3.
Subtracting those cases when three persons sitting next to each other are selected i.e. n
Now I need to subtract those when two out of three persons are sitting next to each other but how am I supposed to this?

10. May 18, 2013

Dick

Count seating possibilities for each person in turn. The first person can sit anywhere, so that's n possibilities. That leaves (n-3) possibilities for the second person. But now the case for the third person is a little complicated. It depends on whether the second person is one seat away from the first person or not. So break the (n-3) into those two cases.

Last edited: May 18, 2013
11. May 18, 2013

Staff: Mentor

That is possible.
Similar to the problem to choose 2 persons who do not sit next to each other.

12. May 18, 2013

Saitama

I am still a bit lost. Here's what I think. When the third person sits near the second person, the cases are n*(n-3)*2 and when the third person is not sitting near the third person, the cases are n*(n-3)*(n-5). Looks correct?

13. May 18, 2013

Staff: Mentor

You do not always have two places next to the second person which are not next to the first one. Try to place two at the same time, and add the third.

14. May 18, 2013

Saitama

I don't think I understand your second statement.

When the second person does not sit on the two nearest seats of the first person and the third person sits near the second person, i.e n*(n-5)*2 and when the third person does not sit near the second person, it is n*(n-5)*(n-8). I think this is still wrong. Sorry if I am acting like a dumb. -_-

Sorry, I meant second there.

15. May 18, 2013

Staff: Mentor

I am confused by those incremental changes to previous statements. Can you use Dick's approach and write everything in one post, please?

16. May 18, 2013

verty

I have come up with a way to simplify this problem by removing the complexity of the seats being nonadjacent. If one seat can be treated as a group of 3 seats, the middle seat being occupied, the problem can be related to one in which the selections are allowed to be adjacent.

This approach can scale to selecting 4 or more seats in a awkward but obvious way.

17. May 18, 2013

Dick

You just aren't counting very carefully. What's you reasoning on that? I would say if the second person is sitting close it's n*2*(n-5). Count that out. Explain why I think so.

Last edited: May 18, 2013
18. May 19, 2013

haruspex

Maybe I misunderstand your suggestion, but it sounds like that would ensure a gap of two between two occupied seats. How about considering the seating of one person as taking out two adjacent seats (the occupied one being always the one to the left, say)?
After seating one arbitrarily, it now looks like a row of n-2 seats. It's pretty easy from there.

19. May 19, 2013

verty

So your first step is to select a group of 2, and your final step is to account for rotational symmetry? This is more elegant than what I did.

I thought about selecting from a row instead of a circle. In this case, one overcounts when both ends of the row are occupied. So the formula here will be a difference of two quantities. But it turns out those quantities are surprisingly simple.

I think we should let Pranav-Arora solve the problem now in the way that Dick suggests.

20. May 20, 2013

Saitama

Sorry everyone for the late reply. I couldn't reply the last time I was online as it was getting late night and yesterday I had a test so I couldn't access PF.

I will again try the Dick's suggestion of breaking (n-3) into two cases.

Case 1st: When the second person is one seat away from the first one, there are two possibilities. The third person cannot sit between the first and second person as I have already counted that case, so it leaves only one possibility for third person. So the cases are: n*2*1.

Case 2nd: When the second person is not one seat away i.e the second person sits on the remaining n-5 seats, the third person can sit on any of the two seats next to the second person i.e 2 possibilities. Total cases: n*(n-5)*2

Is this correct? I hope I explained my point correctly. Sorry for the poor English. =_=

PS: Congrats mfb!