Polygon-Permutation

gmat6087 wrote:There are n sides of a polygon(where n>5).Triangles are formed by joining the vertices of the polygon. How many triangles can be constructed with no side common to the polygon?

OA after discussions.

Total possible triangles:
Any combination of 3 vertices can serve to form a triangle.
Number of combinations of 3 that can be formed from n choices = nC3 = n(n-1)(n-2)/3! = n(n-1)(n-2)/6.

Bad case 1: triangles with exactly 2 sides in common with the polygon
Any set of three CONSECUTIVE vertices can serve to form a triangle with exactly 2 sides in common with the polygon.
To illustrate, in octagon ABCDEFGH:
Point A can be connected to points B and C to form triangle ABC (with sides AB and BC in common with the polygon) or to points B and H to form triangle ABH (with sides AB and AH is common with the polygon).
Here are all of the ways to choose 3 consecutive vertices from octagon ABCDEFGH:
ABC, BCD, CDE, DEF, EFG, FGH, GHA, HAB.
The number of ways is equal to the number of sides.
Thus, given a polygon with n sides, the total number of ways = n.

Bad case 2: triangles with exactly 1 side in common with the polygon
Each side can be combined with any NON-ADJACENT vertex to form a triangle with exactly 1 side in common with the polygon.
In octagon ABCDEFGH, AB can be combined with D, E, F, or G to form triangles ABD, ABE, ABF, and ABG.
For each side, the number of non-adjacent vertices = n-4. (Any of the n vertices but the two that form the side itself and the two vertices adjacent to the side.)
Since there are n sides, each with n-4 non-adjacent vertices, the total number of ways = n(n-4).

Good cases: triangles that can be formed with NO side in common with the polygon
The bad cases -- n and n(n-4) -- must be subtracted from n(n-1)(n-2)/6, the total number of triangles that can be formed.
Thus:

n(n-1)(n-2)/6 - n(n-4) - n

= n/6 ( (n-1)(n-2) - 6(n-4) - 6)

= n/6 (n²-3n+2 - (6n-24) - 6)

= n/6 (n²-9n+20)

= (n/6)(n-4)(n-5)

= n(n-4)(n-5)/6.

GMATGuruNY wrote:

gmat6087 wrote:There are n sides of a polygon(where n>5).Triangles are formed by joining the vertices of the polygon. How many triangles can be constructed with no side common to the polygon?

OA after discussions.

Total possible triangles:
Any combination of 3 vertices can serve to form a triangle.
Number of combinations of 3 that can be formed from n choices = nC3 = n(n-1)(n-2)/3! = n(n-1)(n-2)/6.

Bad case 1: triangles with exactly 2 sides in common with the polygon
Any set of three CONSECUTIVE vertices can serve to form a triangle with exactly 2 sides in common with the polygon.
To illustrate, in octagon ABCDEFGH:
Point A can be combined points B and C to form triangle ABC (with sides AB and BC in common with the polygon) or points B and H to form triangle ABH (with sides AB and AH is common with the polygon).
Here are all of the ways to choose 3 consecutive vertices from octagon ABCDEFGH:
ABC, BCD, CDE, DEF, EFG, FGH, GHA, HAB.
The number of ways is equal to the number of sides.
Thus, given a polygon with n sides, the total number of ways = n.

Bad case 2: triangles with exactly 1 side in common with the polygon
Each side can be combined with any NON-ADJACENT vertex to form a triangle with exactly 1 side in common with the polygon.
In octagon ABCDEFGH, AB can be combined with D, E, F, or G to form triangles ABD, ABE, ABF, and ABG.
For each side, the number of non-adjacent vertices = n-4. (Any of the n vertices but the two that form the side itself and the two vertices adjacent to the side.)
Since there are n sides, each with n-4 non-adjacent vertices, the total number of ways = n(n-4).

Good cases: triangles that can be formed with NO side in common with the polygon
The bad cases -- n and n(n-4) -- must be subtracted from n(n-1)(n-2)/6, the total number of triangles that can be formed.
Thus:

n(n-1)(n-2)/6 - n(n-4) - n

= n/6 ( (n-1)(n-2) - 6(n-4) - 6)

= n/6 (n²-3n+2 - (6n-24) - 6)

= n/6 (n²-9n+20)

= (n/6)(n-4)(n-5)

= n(n-4)(n-5)/6.

Thanks a lot for such detailed explanation. You are a life saver.

Regards,
Satya