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!

#Geometry #Combinatorics #MathProblem #Math

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

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

Comments

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. - 7 years, 6 months ago

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

Mark Mottian - 7 years, 6 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!

Pranav Arora - 7 years, 6 months ago

Mark, I moved your question into a separate discussion.

Calvin Lin Staff - 7 years, 6 months ago

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

Mark Mottian - 7 years, 6 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$

Ankit Chatterjee - 7 years, 6 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).

Mark Mottian - 7 years, 6 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.

Ankit Chatterjee - 7 years, 6 months ago

@Ankit Chatterjee – That makes more sense! Thanks for all your help! :)

Mark Mottian - 7 years, 6 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$

Meet Udeshi - 7 years, 6 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

Meet Udeshi - 7 years, 6 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?

Mark Mottian - 7 years, 6 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}}$

Piyushkumar Palan - 7 years, 6 months ago

@Piyushkumar Palan – A very unique approach to this problem. Keep up this good work!

Mark Mottian - 7 years, 6 months ago

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