Probability

This topic has expert replies
Junior | Next Rank: 30 Posts
Posts: 16
Joined: Sun May 30, 2010 2:34 am

Probability

by fsutanto » Fri Sep 24, 2010 5:50 am
Can anyone help explain the question below? This question is taken from Princeton's 1,012 GMAT practice questions on probability drill.

11. If a polygon has n > 4 sides, what is the probability in terms of n, that a triangle made up of vertices of the polygon shares at least one side with the polygon?

(a) n/4
(b) n! / [3!*(n-3)!]
(c) n!-3 / [3+(n+3)]
(d) 3!(n-3) / [(n-2)*(n-3)]
(e) 3!n! / (n+1)!

The answer according to the book is (d). The best way of doing this is to PLUG IN answer choices, but the explanation isn't exactly clear cut on how to achieve this. Can anyone help explain the approach? Thanks.

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2621
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Fri Sep 24, 2010 11:40 am
fsutanto wrote:Can anyone help explain the question below? This question is taken from Princeton's 1,012 GMAT practice questions on probability drill.

11. If a polygon has n > 4 sides, what is the probability in terms of n, that a triangle made up of vertices of the polygon shares at least one side with the polygon?

(a) n/4
(b) n! / [3!*(n-3)!]
(c) n!-3 / [3+(n+3)]
(d) 3!(n-3) / [(n-2)*(n-3)]
(e) 3!n! / (n+1)!

The answer according to the book is (d). The best way of doing this is to PLUG IN answer choices, but the explanation isn't exactly clear cut on how to achieve this. Can anyone help explain the approach? Thanks.
If that's how they wrote D, they don't have the right answer anywhere; the answer should be [(3!)(n-3)]/[(n-1)(n-2)].

You can certainly find the right answer here by plugging in different values of n, since for small values of n, we can determine what the answer should be. For example, if you have a square (so n=4), any triangle you make will absolutely need to use one edge (actually two edges) of the square, so the probability should be 1 if we plug in n=4. That would let you rule out every answer besides A and D (assuming D was written correctly). Now, you can see that A cannot be correct, since it will be greater than 1 in value if n is greater than 4, and probabilities can never be greater than 1.

You can, of course, solve the problem directly as well, though I don't think it's at all easy. First, if you have n points, to make a triangle we need to choose 3 of them, and order is not important; this can be done in nC3 = (n)(n-1)(n-2)/3! ways. That's the denominator of our probability. Now, there are a few ways to count the number of triangles we can make using at least one edge. We can, for example, consider two cases:

* if we make a triangle using two edges, we need to use two adjacent edges, so we can make n triangles (the number of vertices must be equal to the number of pairs of adjacent edges, since there's one vertex between each pair of adjacent edges).

* if we make a triangle using exactly one edge, we can choose that edge in n ways. Now we've chosen two points to use for our triangle; we then need to choose the third point. We can't use any of the 2 points we've already chosen, and nor can we use any of the 2 points adjacent to these, since then we'd be using two edges, not one. So we have n-4 ways to choose the third point, and n(n-4) triangles we can make using exactly one edge.

So we can make n + n(n-4) = n^2 - 3n = n(n-3) triangles using either one or two edges, and our probability is:

n(n-3)/[ (n)(n-1)(n-2)/3! ] = (3!)(n-3)/[(n-1)(n-2)]

That's probably too cumbersome a calculation to be realistic on the GMAT, however.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com

Master | Next Rank: 500 Posts
Posts: 385
Joined: Sun Jul 12, 2009 10:16 pm
Thanked: 29 times
Followed by:2 members
GMAT Score:710

by debmalya_dutta » Fri Sep 24, 2010 12:51 pm
So we can make n + n(n-4) = n^2 - 3n = n(n-3) triangles using either one or two edges, and our probability is:
Hi Ian,
can you please point out the flaw in my calculation for the numerator.
Atleast 1 side of the polygon can be selected in n ways for n sided polygon...This gives you the 2 vertices of the ploygon... You need to then find the 3 vertex.... The 3rd vertex can be selected in n-2 ways ..Isnt it ? N sided polygon has n vertices ...
So the total number of ways a triangle can be formed = n(n-2) ways... I am surely overlooking something..Can you please point out the flaw..

Thanks in advance
@Deb

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2621
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Fri Sep 24, 2010 3:10 pm
debmalya_dutta wrote:
So we can make n + n(n-4) = n^2 - 3n = n(n-3) triangles using either one or two edges, and our probability is:
Hi Ian,
can you please point out the flaw in my calculation for the numerator.
Atleast 1 side of the polygon can be selected in n ways for n sided polygon...This gives you the 2 vertices of the ploygon... You need to then find the 3 vertex.... The 3rd vertex can be selected in n-2 ways ..Isnt it ? N sided polygon has n vertices ...
So the total number of ways a triangle can be formed = n(n-2) ways... I am surely overlooking something..Can you please point out the flaw..

Thanks in advance
It's a very easy mistake to make in this problem - you're actually double-counting every triangle which uses two edges from the polygon. If you have a polygon ABCDE..., and you start from edge AB, there are indeed n-2 vertices you could join that to in order to make a triangle. One of those triangles is ABC, which uses two edges from the polygon. Then, when you move on to edge BC, if you again think there are n-2 triangles you can make, then you're counting triangle ABC again, and you only want to count it once. So you can take the approach you're using, but you need to adjust it slightly: you'll be double-counting each of the n triangles which use two edges from the polygon, so if you subtract n, you'll get the right answer; n(n-2) - n = n^2 - 3n.

Because it's so easy to double-count here, it's a very difficult problem to do directly, and that double-counting issue was the reason I divided the solution into two cases above.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com

Master | Next Rank: 500 Posts
Posts: 385
Joined: Sun Jul 12, 2009 10:16 pm
Thanked: 29 times
Followed by:2 members
GMAT Score:710

by debmalya_dutta » Fri Sep 24, 2010 3:31 pm
thanks
@Deb

Junior | Next Rank: 30 Posts
Posts: 16
Joined: Sun May 30, 2010 2:34 am

by fsutanto » Sat Sep 25, 2010 12:34 am
I guess I overlooked the PLUG IN option just by the complexity of the answer choices... by selecting 4 sides as a start, you can eliminate 3/5 of wrong answer choices right from the beginning. Lesson learnt, thanks Ian!