BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Combinations

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 304
Joined: Wed Jan 27, 2010 8:35 am
Location: International Space Station
Thanked: 11 times
Followed by:3 members

Combinations

by Aman verma » Sun Dec 25, 2011 1:06 am
Q: If n distinct things are arranged in a circle, find the number of ways of selecting three of these things so that no two of them are next to each other.

a) n(n-2)(n-3)

b) (1/6)n(n-4)(n-5)

c) (1/3)(n^2 + 3n - 5)

d) n-1

e) n-3

nb: Request students to post questions on Statistics eg. Mean, Mode, Median & range. If somebody has such questions with diagrams, histograms or bar diagrams please be generous to post such questions. Please post as many questions as possible!
800. Arjun's-Bird-Eye
Top
Source: — Problem Solving |
Master | Next Rank: 500 Posts
Posts: 385
Joined: Fri Sep 23, 2011 9:02 pm
Thanked: 62 times
Followed by:6 members

by user123321 » Sun Dec 25, 2011 6:37 am
Aman verma wrote:Q: If n distinct things are arranged in a circle, find the number of ways of selecting three of these things so that no two of them are next to each other.

a) n(n-2)(n-3)

b) (1/6)n(n-4)(n-5)

c) (1/3)(n^2 + 3n - 5)

d) n-1

e) n-3

nb: Request students to post questions on Statistics eg. Mean, Mode, Median & range. If somebody has such questions with diagrams, histograms or bar diagrams please be generous to post such questions. Please post as many questions as possible!
I think it is B

I got it through substitution.
I took an hexagon and got only two ways of selecting with given conditions.
and by substituting in choices only B gives me 2

user123321
Just started my preparation :D
Want to do it right the first time.
Top
Legendary Member
Posts: 966
Joined: Sat Jan 02, 2010 8:06 am
Thanked: 230 times
Followed by:21 members

by shankar.ashwin » Sun Dec 25, 2011 6:55 am
You need at least 6 things arranged in a circle to pick 3, (satisfying the condition where no two of them stand together)

Common sense would say there are 0 ways to select 3,4 and 5 things, (satisfying the condition)

But substituting n = 3,4 and 5 in the answer choices we do not get 0.

For a generic problem such as this, the answer choices should satisfy ALL conditions.

Not sure if the question is rightly framed, maybe I am wrong. Whats the source?
Top
Master | Next Rank: 500 Posts
Posts: 385
Joined: Fri Sep 23, 2011 9:02 pm
Thanked: 62 times
Followed by:6 members

by user123321 » Sun Dec 25, 2011 8:26 am
shankar.ashwin wrote:You need at least 6 things arranged in a circle to pick 3, (satisfying the condition where no two of them stand together)

Common sense would say there are 0 ways to select 3,4 and 5 things, (satisfying the condition)

But substituting n = 3,4 and 5 in the answer choices we do not get 0.

For a generic problem such as this, the answer choices should satisfy ALL conditions.

Not sure if the question is rightly framed, maybe I am wrong. Whats the source?
you got the point..That's what I am speaking about..I am seeing lot of questions with missing conditions like these. I think here the question should add n>3 or 4 or whatever is required.
hopefully in actual gmat questions will not be framed like this.

user132321
Just started my preparation :D
Want to do it right the first time.
Top
User avatar
Legendary Member
Posts: 588
Joined: Sun Oct 16, 2011 9:42 am
Location: New Delhi, India
Thanked: 130 times
Followed by:9 members
GMAT Score:720

by rijul007 » Sun Dec 25, 2011 9:13 am
Aman verma wrote:Q: If n distinct things are arranged in a circle, find the number of ways of selecting three of these things so that no two of them are next to each other.

a) n(n-2)(n-3)

b) (1/6)n(n-4)(n-5)

c) (1/3)(n^2 + 3n - 5)

d) n-1

e) n-3

nb: Request students to post questions on Statistics eg. Mean, Mode, Median & range. If somebody has such questions with diagrams, histograms or bar diagrams please be generous to post such questions. Please post as many questions as possible!
Let me assume that ques mentions n>4


Now the ideal way to do this ques in the real GMAT is just as user123321 did,ie by pugging in numbers..


heres is another much lengthier approach using combinatrics



n distinct things are arranged around in a circle


Image



Let us first select elemnt 1 out of n things

now for the second we have n-3 things left


out of these n-3 elements i chose element 3 for second place
now (n-5) elements are left for 3rd selection



Image


when 2nd selection = 4
no of elements for 3rd selection = n-6

and so on


from the trend we can say that no of ways of selecting two things when the first is element 1 would be = (n-5) + (n-6) + (n-7) + (n-8) + .... + 1
=> (n-5)(2+(n-6))/2 => (n-5)(n-4)/2

this was when we fixed the first element

so the total no of selection when first element also varies would be n(n-5)(n-4)/2

but we still have a problem of repetition here
the selection {1,5,7} would be the same as {7,1,5}

to avoid this we divide it by 3

so the no of ways of selecting three elements such that no two are together would be n(n-4)(n-5)/6


Option B
Top
User avatar
GMAT Instructor
Posts: 349
Joined: Wed Sep 28, 2011 3:38 pm
Location: Austin, TX
Thanked: 236 times
Followed by:54 members
GMAT Score:770

by GmatMathPro » Sun Dec 25, 2011 11:00 am
A couple of ways for n>5:

First, note that every time we pick something, we rule out three additional things for future picks (the thing itself and the thing's neighbors) UNLESS the thing we pick shares a neighbor with a thing we previously picked in which case we only rule out two additional things.

So, n ways to pick the first thing, which leaves us n-3 choices for the second thing. There are two things that share neighbors with the first thing, so if we pick those, we have n-5 choices for the third thing. If pick one of the n-5 things that doesn't share a neighbor with the first thing, then we will have n-6 choices for the third thing: n(2(n-5)+(n-5)(n-6))=n((n-5)(2+n-6))=n(n-5)(n-4). Divide this by 3! to eliminate the repeats to get n(n-5)(n-4)/6.

OR

Calculate the total number of ways to choose three things and then subtract the number of ways that have adjacent things.

Total number of ways to choose 3 things: nC3 = n(n-1)(n-2)/6

Number of ways to choose two adjacent things with one thing separate: n ways to choose two adjacent things, and n-4 ways to choose the third thing, so n(n-4) total ways.

Number of ways to choose three adjacent things: n ways

n(n-1)(n-2)/6 - n(n-4) - n
[n(n^2-3n+2)-6(n^2-4n)-6n]/6 (combine terms over a common denominator)

[n^3-3n^2+2n-6n^2+24n-6n]/6

[n^3-9n^2+20n]/6

n(n^2-9n+20)/6

n(n-5)(n-4)/6
Pete Ackley
GMAT Math Pro
Free Online Tutoring Trial
Top
Master | Next Rank: 500 Posts
Posts: 304
Joined: Wed Jan 27, 2010 8:35 am
Location: International Space Station
Thanked: 11 times
Followed by:3 members

by Aman verma » Mon Dec 26, 2011 7:46 am
Thanks! Everybody.

Solution: We can select first object out of n objects in nC1 ways. Now the number of ways of choosing two objects such that they are always together is (n-4)ways since we assume two objects as a single object.Further, we can select three objects viz. the one object which has already been selected and two objects of one either side of the first object.
Therefore the number of ways of choosing two objects such that they are not together is
= (n-3)C2-(n-4) = (n-4)(n-5)/2

Since these two objects can be arranged in 2! ways, the number of ways of choosing three objects(in order of first,second and third) is 2n(n-4)(n-5)/2 = n(n-4)(n-5)
But since the order in which the objects are taken is immaterial, the number of ways of choosing the objects is n(n-4)(n-5)/6. QED. This is a combinatorics question!
800. Arjun's-Bird-Eye
Top
User avatar
Legendary Member
Posts: 626
Joined: Fri Dec 23, 2011 2:50 am
Location: Ahmedabad
Thanked: 31 times
Followed by:10 members

by ronnie1985 » Mon Dec 26, 2011 8:24 pm
Selecting 1 person from n in a circle = nC1 = n ways
Now we have 2 more persons to select. Let us fix 2 persons together, thus we have n-3 persons in a circle. Choosing the 2 fixed persons can be done in 2!*(n-4)C1 = n-4 ways
Choosing 2 persons such that they are not together =(n-3)C2-(n-4)= (n-4)(n-5)/2
Follow your passion, Success as perceived by others shall follow you
Top
Post new topic Post Reply
• Page 1 of 1