Waste less time on Facebook — follow Brilliant.
×

11-sided polygon

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!

Note by Mark Mottian
3 years, 9 months ago

No vote yet
5 votes

Comments

Sort by:

Top Newest

The 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. Hero P. · 3 years, 9 months ago

Log in to reply

@Hero P. 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! Pranav Arora · 3 years, 9 months ago

Log in to reply

@Hero P. WOW! Thank you for such a spectacular solution. My conscious is at rest now. :) Mark Mottian · 3 years, 9 months ago

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\] Meet Udeshi · 3 years, 9 months ago

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\) Ankit Chatterjee · 3 years, 9 months ago

Log in to reply

@Ankit Chatterjee 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). Mark Mottian · 3 years, 9 months ago

Log in to reply

@Mark Mottian 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. Ankit Chatterjee · 3 years, 9 months ago

Log in to reply

@Ankit Chatterjee That makes more sense! Thanks for all your help! :) Mark Mottian · 3 years, 9 months ago

Log in to reply

Mark, I moved your question into a separate discussion. Calvin Lin Staff · 3 years, 9 months ago

Log in to reply

@Calvin Lin Thanks Calvin! By the way, you have a really philosophical status. :) Mark Mottian · 3 years, 9 months ago

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 Meet Udeshi · 3 years, 9 months ago

Log in to reply

@Meet Udeshi 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? Mark Mottian · 3 years, 9 months ago

Log in to reply

@Mark Mottian 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}} \) Piyushkumar Palan · 3 years, 8 months ago

Log in to reply

@Piyushkumar Palan A very unique approach to this problem. Keep up this good work! Mark Mottian · 3 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...