# 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
4 years, 7 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

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.

- 4 years, 7 months ago

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!

- 4 years, 7 months ago

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

- 4 years, 7 months ago

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$

- 4 years, 7 months ago

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$$

- 4 years, 7 months ago

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).

- 4 years, 7 months ago

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.

- 4 years, 7 months ago

That makes more sense! Thanks for all your help! :)

- 4 years, 7 months ago

Mark, I moved your question into a separate discussion.

Staff - 4 years, 7 months ago

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

- 4 years, 7 months ago

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

- 4 years, 7 months ago

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?

- 4 years, 7 months ago

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}}$$

- 4 years, 7 months ago

A very unique approach to this problem. Keep up this good work!

- 4 years, 7 months ago