• Support PF! Buy your school textbooks, materials and every day products Here!

Selecting 3 persons sitting round a table

  • Thread starter Saitama
  • Start date
  • #1
3,812
92

Homework Statement


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)##.


Homework Equations





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. :confused:

Any help is appreciated. Thanks! :)
 

Answers and Replies

  • #2
34,366
10,437
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.

I don't really know how to tackle this problem.
You could consider the problem with 1 person and with 2 persons, first.
 
  • #3
3,812
92
6C1*(3C2-2)=6 - if you take into account that 3 choices of the first person will lead to the same set...
Can you please elaborate this? :confused:

mfb said:
You could consider the problem with 1 person and with 2 persons, first.
The number of cases are zero for n=1 to 5.
 
  • #4
34,366
10,437
Can you please elaborate this? :confused:
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.

The number of cases are zero for n=1 to 5.
I mean the number of possibilities to select 1 (or 2) out of some general number n.
 
  • #5
3,812
92
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 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
34,366
10,437
It is correct for 1 person, but not for 2. Don't forget that the 2 cannot sit next to each other.
 
  • #7
3,812
92
It is correct for 1 person, but not for 2. Don't forget that the 2 cannot sit next to each other.
Is it nC2-n?
 
  • #8
34,366
10,437
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
3,812
92
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.
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? :confused:
 
  • #10
Dick
Science Advisor
Homework Helper
26,258
618
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? :confused:
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:
  • #11
34,366
10,437
Now I need to subtract those when two out of three persons are sitting next to each other
That is possible.
but how am I supposed to this?
Similar to the problem to choose 2 persons who do not sit next to each other.
 
  • #12
3,812
92
Similar to the problem to choose 2 persons who do not sit next to each other.
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.
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
34,366
10,437
When the third person sits near the second person, the cases are n*(n-3)*2
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.
and when the third person is not sitting near the third person
:confused:
 
  • #14
3,812
92
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.
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. -_-

mfb said:
:confused:
Sorry, I meant second there. :rolleyes:
 
  • #15
34,366
10,437
I am confused by those incremental changes to previous statements. Can you use Dick's approach and write everything in one post, please?
 
  • #16
verty
Homework Helper
2,164
198
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
Dick
Science Advisor
Homework Helper
26,258
618
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?
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:
  • #18
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,463
5,410
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.
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
verty
Homework Helper
2,164
198
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.
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
3,812
92
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. :rolleyes:

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! :smile:
 
  • #21
34,366
10,437
Thanks.

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.
Why just 1?
I am not sure if I understand what your cases are.
 
  • #22
3,812
92
Why just 1?
I am not sure if I understand what your cases are.
Okay, I will try to explain my thinking through images. Consider 6 people sitting round the table.

We need to count those cases when two out of three persons sit together. The first person can sit at any of the six places.

For the case 1st in my previous post, when the second person is one seat away (consider that first person is at A), he can sit on the seats circled by blue. As the third person should sit near the second but not near the first, he can sit on the seat circled by orange.
1z54y82.png

This gives me a total of 12 arrangements. If I plug n=6 in n*2*1, it is equal to 12. I don't see how this is wrong. :confused:

Also, I feel that I need to divide the result by 2 because A+(CD) is same as A+(ED).

Did I explain it correctly this time? :redface:
 
Last edited:
  • #23
verty
Homework Helper
2,164
198
Did I explain it correctly this time? :redface:
Placing that second person is annoying because the third person may or may not have a seat. With a bigger table, the third person can always be seated, so I would consider a table with 7 or more seats instead. And remember we don't know how many seats there are, so don't put actual numbers in the formula where n's should appear.
 
  • #24
3,812
92
Placing that second person is annoying because the third person may or may not have a seat. With a bigger table, the third person can always be seated, so I would consider a table with 7 or more seats instead. And remember we don't know how many seats there are, so don't put actual numbers in the formula where n's should appear.
For now I am considering only those cases when the second person is one seat away from the first. So I think its better to put some values of n and see if my thinking is correct. :)
 
  • #25
Dick
Science Advisor
Homework Helper
26,258
618
Did I explain it correctly this time? :redface:
Yes, 6*2*1=12 ways. But if the three people selected are A, E and C then the 12 counts selections of them in different orders as different. You don't really care what order. You need to divide by something.
 

Related Threads on Selecting 3 persons sitting round a table

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
7
Views
2K
Replies
17
Views
3K
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
5
Views
1K
Replies
2
Views
17K
Top