An 11-sided polygon has its vertices on a circle. How many triangles can be formed using three vertices of the polygon but sharing no side in common with the side of the polygon?

Can somebody please provide a solution!! This problem is driving me crazy!

No vote yet

5 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestThe correct answer is 77.

First, find the total number of triangles on \( n \) vertices; this is simply \( \binom{n}{3} \). Next, exclude all triangles that share at least one side with the \( n \)-gon. We count these by indexing on the \( n \) non-permissible edges. For each such edge, there are \( n-2 \) ways to choose the third vertex. But this double counts those triangles that share two edges with the \( n \)-gon, of which there are simply \( n \) of them. So the total number of desired triangles is \( \binom{n}{3} - n(n-2) + n = \frac{1}{6}n(n-4)(n-5). \) For \( n = 11 \), we get 77.

Note that for \( n > 3 \), there are no triangles that share 3 edges with the given \( n \)-gon.

For \( n \le 5 \), it is easy to see that no such triangles exist, and for \( n = 6 \), we get the correct value of 2.

Log in to reply

Hi Hero!

Can you please explain "We count these by indexing on the \(n\) non-permissible edges. For each such edge, there are \(n-2\) ways to choose the third vertex."?

Thanks!

Log in to reply

WOW! Thank you for such a spectacular solution. My conscious is at rest now. :)

Log in to reply

All the current solutions using inclusion-exclusion are good. I had another one in mind so I thought I would post.

We need to choose 3 points from the \(n\) points of the polygon for the triangle. That divides the rest of the points into 3 groups containing \(x_1, x_2, x_3\) number of points respectively.

So we have \[x_1 + x_2 +x_3 = n-3\]

If we ensure that there is atleast one point in each group then we ensure that we have not selected adjacent points. Thus we need to find the number of positive integral solutions to the equation

\( x_1 + x_2 + x_3 =n-3\) which is \( ^{n-4}C_2\)

The answer will be that multiplied by \(n/3\) because there are \(n\) ways to choose the starting point, and there are three repeated cases in which we will get the same triangle from a different set of \((x_1,x_2,x_3)\)

So finally we get \[n(n-4)(n-5)/6\]

Log in to reply

you may use the Principle of inclusion and exclusion as: A=no of triangles formed by choosing any three vertices=\({n \choose 3}\) B=no of triangles formed such that it has one side of the polygon in common=\(no of sides*(n-4)\)or \(n*(n-4)\) The reason for n-4 is that you have to take any particular side and omit any triangles that have two sides of the polygon in common i.e. you exclude the two adjacent vertices of the side chosen.we are left with n-4 vertices.this at is repeated for all the n sides C=no of triangles formed having two sides of the polygon in common(check that these sides must definitely be adjacent)=\(n\) Hence your answer will be A-(B+C) Here it is \({11 \choose 3} - (11*(11-4)) - (11) = 165-77-11 = 77\)

Log in to reply

Hi Ankit. I think this is a really good approach to this problem, although, why doesn't it work for a 6-sided polygon (as an explicit example). It's apparent that a 6-sided polygon will produce two triangles that satisfy the condition outlined in the problem statement. If I substitute 6 for 'n' in your general formula above, it produces an answer of -7 (which is impossible).

Log in to reply

Mark, I am extremely sorry for a mistake,I took the set C to be \({n \choose 2}\) but it must be \(n\) instead since we choose any two adjacent sides of the polygon to form a triangle thus forming the set C.sorry for the previous answer..I am editing it.Thanks.

Log in to reply

Log in to reply

Mark, I moved your question into a separate discussion.

Log in to reply

Thanks Calvin! By the way, you have a really philosophical status. :)

Log in to reply

You need to choose 3 points from those 11 to form the triangle, such that no two points are adjacent. If two points are adjacent then one side of the triangle will be common with one side of the polygon, which we don't want.

That should be enough of a hint to start attempting

Log in to reply

Hi Meet Udeshi! I took what you suggested as a guideline, however, I am still stuck. I tried small cases but I still could not identify a solution. Do you perhaps have a solution? Can you generalise for an n-sided figure?

Log in to reply

Let \( n \) vertices be numbered \( 1, 2, 3, ..., n. \)

Firstly, imagine their linear arrangement. We neet 3 non-consecutive vertices.

By gap method, its same as placing \( 3 \) objects, among gaps of \( n-3 \) objects placed in row. There are \( n - 3 + 1 = n - 2 \) gaps. (we need to include extremes.)

So it gives \( {n-2} \choose{3} \)

But this includes selections containing vertices \( 1 \) and \( n \). Such selection is permissible in row, but actually in polygon, 1 and n are connected. So we need to discard \( (n-4) \) cases.

( \( (n-4) \) because selections of \( 1 \) and \( n \) with \( 2 \) and \( (n-1) \) were already not ounted in gap method)

Hence answer \( {n-2} \choose {3} \) \( - (n-4) = \boxed{ \frac{n(n-4)(n-5)}{6}} \)

Log in to reply

Log in to reply