Math question, need help

cdietschrun

cdietschrun

CAGiversary!
Feedback
17 (100%)
I have a class, Discrete Structures (math) 2. No tutors are allowed to tutor it at my university (yes, seriously). Can anyone give me help with this problem?

20 People are seated around a table. How many ways to choose 3 of them if no 2 of them are neighbors?

The only thing I can see is 20 choose 3 is obviously in there somewhere, and you need to subtract something. Any help? Any combinatoric/permutation experts?
 
20 * 19 * 18

There are 20 different ways to select one person out of 20. You subtract one each subsequent time since you can't pick someone twice.
 
[quote name='dafoomie']20 * 19 * 18

There are 20 different ways to select one person out of 20. You subtract one each subsequent time since you can't pick someone twice.[/QUOTE]
This isn't right because you can't pick neighbors.
 
[quote name='dafoomie']20 * 19 * 18

There are 20 different ways to select one person out of 20. You subtract one each subsequent time since you can't pick someone twice.[/quote]

Wouldn't it go 20 *17 * 14?

20 for each person there.
17 for each person minus the person picked and their 2 neighbors.
14 for the person selected second and their neighbors.

EDIT: Actually I think its more complicated then that. Lets say you pick the first person, and then you pick the person two people down from them, you are only eliminating 5 people opposed to 6. And I have no idea how to account for that.
 
You're right...start with 20 choose 3, to get the total number of ways you can grab three people out of a pool of 20. From there, just subtract the number of times where all three are sitting in a row, and then subtract each instance where just two people are neighbors.

At least, it's how I'd do it.
 
[quote name='Mattte']Wouldn't it go 20 *17 * 14?

20 for each person there.
17 for each person minus the person picked and their 2 neighbors.
14 for the person selected second and their neighbors.

EDIT: Actually I think its more complicated then that. Lets say you pick the first person, and then you pick the person two people down from them, you are only eliminating 5 people opposed to 6. And I have no idea how to account for that.[/QUOTE]
Thats right, the OP worded it a little awkwardly and I didn't understand what he meant by that.

Its not as simple as subtracting the pick and 2 neighbors, its possible to have a pick with a neighbor already eliminated.
 
Here's how I thought about it. Not sure if the answer is correct or not.

Obviously the first person to sit down can choose from 20 seats. The second person can then choose from any of the 17 remaining chairs. The tricky part is that, of the 17 choices for the second person, not all leave the same number of remaining chairs for the 3rd person. If you look at the 17 cases, 2 leave 15 available chairs (i.e., when the first two are next-to-nearest neighbors), and the other 15 leave 14 available chairs. Putting it all together, we have 20 x (2 x 15 + 15 x 14) = 20 x 16 x 15 = 4800.

Does that sound right?
 
[quote name='dafoomie']Thats right, the OP worded it a little awkwardly and I didn't understand what he meant by that.

Its not as simple as subtracting the pick and 2 neighbors, its possible to have a pick with a neighbor already eliminated.[/quote]

The problem is, A) That's exactly how the book words my question.
B) I don't have an answer to this question.

My first reasoning is that there is 20 nCr 3 total ways to pick 3 people from 20. That's 1140 ways. That includes 3 people sitting next to each other, or 2 of the 3 sitting next to each other. So I would assume you would need to subtract certain choices from 1140. Other than that, I'm not sure what else to do.

And for whatever reason, only this class and Discrete I is not allowed tutoring.
 
[quote name='Spintronic']Here's how I thought about it. Not sure if the answer is correct or not.

Obviously the first person to sit down can choose from 20 seats. The second person can then choose from any of the 17 remaining chairs. The tricky part is that, of the 17 choices for the second person, not all leave the same number of remaining chairs for the 3rd person. If you look at the 17 cases, 2 leave 15 available chairs (i.e., when the first two are next-to-nearest neighbors), and the other 15 leave 14 available chairs. Putting it all together, we have 20 x (2 x 15 + 15 x 14) = 20 x 16 x 15 = 4800.

Does that sound right?[/quote]

I think it may be 20 * 17 * (2 * 15 + 15 * 14)

I'm fairly positive 20 * 17 is the first part, since that should never change.
 
I'm sticking with my way of thinking...

20 nCr 3 = 1140...
20 possible ways for to pick 3 such that they're all in a row...
20*16 possible ways to pick 3 such that two are neighbors and the last one isn't...
1140-20-320=800 different groups of 3 such that no two are neighbors.

Of course, if the order of picking matters (picking Jim, Bob, Hank is a different "way" than picking Hank, Jim, Bob), that means there's 6 different ways to get each group, resulting in 4800 ways to get three people.
 
[quote name='Mattte']I think it may be 20 * 17 * (2 * 15 + 15 * 14)

I'm fairly positive 20 * 17 is the first part, since that should never change.[/quote]


But the answer has to be less than 20 x 19 x 18, right? What you have above is larger.
 
[quote name='cdietschrun']The problem is, A) That's exactly how the book words my question.
B) I don't have an answer to this question.

My first reasoning is that there is 20 nCr 3 total ways to pick 3 people from 20. That's 1140 ways. That includes 3 people sitting next to each other, or 2 of the 3 sitting next to each other. So I would assume you would need to subtract certain choices from 1140. Other than that, I'm not sure what else to do.

And for whatever reason, only this class and Discrete I is not allowed tutoring.[/QUOTE]

Going from this, if 20 nCr 3 is 1140, and we just subtract every case where 2 are neighbors, that's 1140 - (20 * 18) = 780.

Edit: I see Salamando counted 3 neighbors and 2 neighbors separately...I tried doing it together but I think he's right because that would subtract too many, so never mind my answer. It's 800.
 
[quote name='Salamando3000']I'm sticking with my way of thinking...

20 nCr 3 = 1140...
20 possible ways for to pick 3 such that they're all in a row...
20*16 possible ways to pick 3 such that two are neighbors and the last one isn't...
1140-20-320=800 different groups of 3 such that no two are neighbors.

Of course, if the order of picking matters (picking Jim, Bob, Hank is a different "way" than picking Hank, Jim, Bob), that means there's 6 different ways to get each group, resulting in 4800 ways to get three people.[/quote]

I am very much in agreement of 1140-20. I want to hear your reasoning behind 20*16 choices for 2 people choices that we are eliminating. Otherwise, I think 800 is right.
 
[quote name='cdietschrun']I am very much in agreement of 1140-20. I want to hear your reasoning behind 20*16 choices for 2 people choices that we are eliminating. Otherwise, I think 800 is right.[/quote]

Simple. There are 20 different ways to choose 2 people such that they're neighbors. For each of those ways, we still need to place 1 more, and there are only 16 places they can be (2 are already chosen, and 2 would place them in a way causing three in a row, which we already counted). Hence, 16*20.
 
You must log in or register to reply here.
bread's done
Back
Top