15 Replies - 1567 Views - Last Post: 24 November 2010 - 12:25 PM
#1
Inscribed Triangles
Posted 22 November 2010 - 12:51 PM
I have a problem where I have to find the number of triangles
that can be inscribed in a polygon with n sides if none of the
triangles are to share any side with the polygon.
So no two adjacent points in the polygon can be chosen for the
triangle. so I came up with:
( n / 2 choose 3 ) * 2
is this correct?
if not, what is the formula for doing this?
Replies To: Inscribed Triangles
#2
Re: Inscribed Triangles
Posted 22 November 2010 - 06:03 PM
#3
Re: Inscribed Triangles
Posted 22 November 2010 - 06:06 PM
I assume the mean all even sides and angles.
#4
Re: Inscribed Triangles
Posted 24 November 2010 - 09:59 AM
1)
the word 'inscribed' implies that the polygon's sides surround (and do not intersect) any of the triangles created inside. This would cause issue if the polygon is NOT convex... because triangles would intersect with sides (while note sharing sides) and technically not be 'inscribed' by some definitions. But this isn't ALL definitions, and usually these kinds of questions (especially if you're in game development or some other 3d computer stuff) presumes convex polygonal shapes. So I'm going to ignore this little issue (otherwise the problem is unsolvable due to a lack of information).
2)
((n/2) choose 3) * 2
is not the correct formula. Proof, a polygon of 8 sides can have 15 unique triangles that do not share any sides with the polygon itself. But this formula would give you 8...
8 / 2 choose 3 * 2
4 choose 3 * 2
4 * 2
8
3)
As for the answer... I don't actually know. I analyzed it a bit, but can't find it at the moment. I'm also at work, so it's not like I can really dedicate the time to it.
Though it is a fun little puzzle.
Thing is it's not the easiest thing to solve, and I don't know what class you're in, but I'm betting that it's discussed somewhere in the chapter or something. Or requires some type of related background... I don't have this material so I can't base it on any of it, where as I have to fly by the seat of my pants in combinatorics (something I haven't played w/ in a long time). Take a look through your chapter, maybe illicite some more related data (like what are you specifically studying right now). I'll probably try to answer it later when I have time to do so... as I said it's a fun question.
(note I actually have it half resolved as a recursive summation using a deformed version of the recursive formula for solving binomial coefficients... BUT I haven't figured any proof/explanation for it and I'm not certain it's correct. Also displaying it here would be rather complicated. I would like to prove it and convert it to algebraic form first.)
This post has been edited by lordofduct: 24 November 2010 - 10:34 AM
#5
Re: Inscribed Triangles
Posted 24 November 2010 - 11:24 AM
#6
Re: Inscribed Triangles
Posted 24 November 2010 - 11:25 AM
#7
Re: Inscribed Triangles
Posted 24 November 2010 - 11:29 AM
#8
Re: Inscribed Triangles
Posted 24 November 2010 - 11:34 AM
it would probably be something like finding a formula for how many ways
3 things can be chosen from 8 when no two are adjacent. right?
but how would I do that?
#9
Re: Inscribed Triangles
Posted 24 November 2010 - 11:47 AM
2. Calculate the number of triangles that can share a side
3. Subtract #2 from #1
The first step should be easy. The second step, you can do by drawing any polygon (obviously convex) and counting these triangles in some systematic fashion. For example, pick a side, and count how many triangles can share this side. Then do the same thing for the next side. Make sure that you count unique triangles.
#10
Re: Inscribed Triangles
Posted 24 November 2010 - 11:57 AM
and I chose one side ( two adjacent points ):
_____ / \ / \ | | | | \ / \_____/
and went around the octagon for each side,
it would be:
8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
8^8 right?
so for a polygon where you can't have two adjacent points,
it would be:
( n choose 3 ) - n^n?
or would it be
8 * 8 * 8 * 8 * 8 * 8
8^6
because the other 2 points are already taken
so ( n choose 3 ) - n^(n - 2)?
This post has been edited by -shadow-: 24 November 2010 - 11:59 AM
#11
Re: Inscribed Triangles
Posted 24 November 2010 - 12:09 PM
Start with a single side. This side has 2 points. How many other points can you connect it to, to create a triangle? The other (n-2) points. So that's (n-2) triangles right there, that share this side. Now go to another side. How many triangles does it have? Count it, then *add* them to the previous number. However, note that when you will count the sides for the next side, you may count the same triangle, multiple times. Count only the unique triangles.
Subtract the number from (n choose 3) and you'll get your answer.
This post has been edited by Nikitin: 24 November 2010 - 12:10 PM
#12
Re: Inscribed Triangles
Posted 24 November 2010 - 12:16 PM
Nikitin, on 24 November 2010 - 10:24 AM, said:
DURRRRRRPPPPPP
I was so going the long way around!
This whole week has been one long brain fart for me.
This post has been edited by lordofduct: 24 November 2010 - 12:18 PM
#13
Re: Inscribed Triangles
Posted 24 November 2010 - 12:17 PM
( n choose 3 ) - ( n^( n - 2 ) - 8 )
#14
Re: Inscribed Triangles
Posted 24 November 2010 - 12:19 PM
#15
Re: Inscribed Triangles
Posted 24 November 2010 - 12:21 PM
Nikitin, on 24 November 2010 - 02:19 PM, said:
oh sorry I got screwed up thinking about the octagon
it should be "( n choose 3 ) - ( n^( n - 2 ) - n )"
[edit] actually... hold on (8 choose 3 ) - ( 8 * ( 8 - 2 ) )
comes up with the right answer...
( n choose 3 ) - ( n * ( n - 2 ) ), is that right?
This post has been edited by -shadow-: 24 November 2010 - 12:25 PM