[-shadow-]

Hey,
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?

[mostyfriedman]

are there any constraints on the shape of the polygon

[-shadow-]

no it just says "a polygon with n sides"
I assume the mean all even sides and angles.

[lordofduct]

All right, I don't know the actual answer, I'm just assessing the problem and trying to make an educated guess.


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

[Nikitin]

Erh... just calculate the number of total inscribed triangles and subtract the number of triangles that can share a side. Pretty simple.

[-shadow-]

Nikitin, on 24 November 2010 - 01:24 PM, said:

Erh... just calculate the number of total inscribed triangles and subtract the number of triangles that can share a side. Pretty simple.

Thats what my teacher said, but I'm not quite sure how to do that

[Nikitin]

Have you studied combinatorics, like counting combinations and permutations?

[-shadow-]

yes, in grueling detail. but I'm not sure about that particular problem.
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?

[Nikitin]

1. Calculate the number of total inscribed triangles
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.

[-shadow-]

so if we had say an octagon:
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

[Nikitin]

Whoa, hold on there, gringo. 8^8 is a heck of a lot of triangles. (n choose 3) - n^n will give you a negative number.

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

[lordofduct]

Nikitin, on 24 November 2010 - 10:24 AM, said:

Erh... just calculate the number of total inscribed triangles and subtract the number of triangles that can share a side. Pretty simple.

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

[-shadow-]

so
( n choose 3 ) - ( n^( n - 2 ) - 8 )

[Nikitin]

Almost. Two things, why you're putting things to the power, and why is there an 8?

[-shadow-]

Nikitin, on 24 November 2010 - 02:19 PM, said:

Almost. Two things, why you're putting things to the power, and why is there an 8?

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