Welcome to NRICH.

 
P R O B L E M S 2
By Pooya Farshim (P2572) on Wednesday, August 9, 2000 - 12:31 am:

Draw all the diameters of an n-sided regular polygon. How many triangles are there?
If there is no general formula, how can I write a programme in Qbasic to count the triangles?

By Anonymous on Thursday, August 10, 2000 - 10:07 pm:

Wouldn't it just be 2n, where n is the number of sides?

By Pooya Farshim (P2572) on Friday, August 11, 2000 - 03:39 am:

No it wouldn't. For n=3 the number of triangles is 1, for n=4 is 8 etc...

By Dan Goodman (Dfmg2) on Friday, August 11, 2000 - 05:19 am:

I'm not sure what you mean by your question, could you be more precise. Do you mean you connect up every vertex with every other vertex? Do you mean you only connect up vertices if they go through the centre? Do you want the number of regions these line divide the shape into, because some of these regions will not be triangles (some will be quads, pents, etc.)? Or do you want the number of triangles, including triangles made up of more than region? From your examples above, I think you mean you join all vertices and you want the number of triangles which can be made of more than one region. Assuming this is what you mean, I get N(3)=1, N(4)=8, N(5)=40 (I think), I haven't done N(6), but I had a quick look and it's at least 104, so it grows very rapidly. I'll wait and check I have the problem right before continuing.

By Pooya Farshim (P2572) on Saturday, August 12, 2000 - 12:26 am:

Dan:

You have the problem right: N(3)=1, N(4)=8, N(5)=40, N(6)>=104. It's a tedious job! I think it's a bit difficult to derive a general formula for N(m). Do you know an algorithm to do this? How can I give an upper and lower bound for N(m)? Is it possible to disprove/prove inequalities like N(m)>=2N(m-1)? And......

Thank you

Pooya

By Dan Goodman (Dfmg2) on Saturday, August 12, 2000 - 12:41 pm:

I think it'll be very difficult to derive a general formula for N(m). There are loads of lower bounds you can easily derive for N(m), for instance if you take any three distinct vertices, and join them up you'll have a triangle, so the number of ways of choosing three distinct vertices will give you a lower bound. I think that this number is nC3=n(n-1)(n-2)/6, so this gives a lower bound of
3C3=1, 4C3=4, 5C3=10. It might turn out that the final formula is (2n-3)nC3, this would give N(3)=1, N(4)=8, N(5)=40, N(6)=160, N(7)=560, etc. Well, it agrees for the first couple, but that doesn't mean anything.

By Dan Goodman (Dfmg2) on Saturday, August 12, 2000 - 02:36 pm:

I found this solution of the problem on the internet, but it doesn't agree with our result for N(5)=40 (apparently N(5)=35), here is what I found:

Quote:

I think that the n-gon is supposed to be convex and that no three
diagonals are concurrent.
Draw some figures to make it more clear.
Each of the considered triangles belongs to one of the following cases :

- Case 1 : All of the vertices of the triangle are vertices of the
n-gon.
Such a triangle is determined by three vertices of the n-gon.
Conversely, a choice of three vertices of the n-gon gives only one
triangle in this case.
Then the number of triangle in this case is C(n,3) (the binomial
coefficient)

- Case 2 : Exactly 2 of the vertices of triangle are vertices of the
n-gon.
Such a triangle is determined by four vertices of the n-gone, the two
common vertices of the triangle and the n-gon, and two others to give
the interior point as third vertex.
Conversely, a choice of 4 vertices of the n-gon gives exactly 4
triangles in this case.
Then the number of triangle in this case is 4×C(n,4).

- Cases 3 :Exactly 2 of the vertices of triangle are vertices of the
n-gon.
Such a triangle is determined by five vertices of the n-gon, the common
vertex of the triangle and the n-gon, and four others to give the 2
interior points.
Conversely, a choice of 5 vertices of the n-gon gives exactly 5
triangles in this case.
Then the number of triangle in this case is 5×C(n,5).

- Case 4 : None of the vertices of triangle is a vertex of the n-gon.
Such a triangle is determined by six vertices of the n-gon.
Conversely, a choice of 6 vertices of the n-gone gives exactly 1
triangles in this case.
Then the number of triangle in this case is C(n,6).

Therefore the total number of triangles is
T = C(n,3) + 4×C(n,4) + 5×C(n,5) + C(n,6)
= n(n-1)(n-2)(n3 + 18n2 -43n +60)/720.



I haven't had time to look at it yet.
By Pooya Farshim (P2572) on Tuesday, August 15, 2000 - 02:13 am:

N(4)=2+2+2+2=8
Squares
N(5)=5+5+25=35
Pentagons
N(6)=12+1+1+2x42+12=110
Hexagons

By Pooya Farshim (P2572) on Tuesday, August 15, 2000 - 02:37 am:

How can I prove that in a regular 2k+1-gon no 3 diagonals are concurrent?

I was trying to write an Algorithm to count the number of triangles in a regular n-gon. First I had to determine the points of intersections of the diagonals. Let M(n) be the number of these points plus the number of vertices (total number of points). Is there a general formula for this?

The first 20 (as my programme counts) are:
M(3)=3, M(4)=5, M(5)=10, M(6)=19, M(7)=42, M(8)=57, M(9)=135, M(10)=171, M(11)=341, M(12)=313, M(13)=728, M(14)=771, M(15)=1380, M(16)=1393, M(17)=2397, M(18)=1855, M(19)=3895, M(20)=3861

The best I could found was:

M(n)~n/24(n3-6n2+11n-6)

How can I do better?

By Neil Morrison (P1462) on Tuesday, August 15, 2000 - 06:34 pm:

Perhaps there is a less annoying formula if you try using each 'type' of triangle only once, ie: suppose we list all the types of triangles, so that the others can be found by rotating (or reflecting?) the polygon. Just a thought.

Neil M

By Pooya Farshim (P2572) on Tuesday, August 15, 2000 - 10:49 pm:

M(n) & N(n) for n=2k+1:

M(n)=n(n+1)(n2-7n+18}/24
N(n)=n(n-1)(n-2)(n3+ 18n2-43n+60)/720, as quoted


What about n=2k? Can we atleast find a formulae for M(n)? I found that there is n(n-6)/2+1 points in a 2k-gon (k>2) where 3 lines meet. Can N(n) be related to the divisors of n?

By Pooya Farshim (P2572) on Wednesday, August 23, 2000 - 09:19 pm:

Any suggestions for the above Problem?

By Dan Goodman (Dfmg2) on Thursday, September 7, 2000 - 05:02 am:

Do you know Euler's formula, it might help you, it says that for a map drawn in a plane, V-E+F=2 where V is the number of vertices, E is the number of edges and F is the number of faces (distinct regions) including the infinitely large one consisting of the region outside the shape. You want to know V, so if you could work out E and F (which might be easier) you know V.

I haven't really had time to think about this problem, presumably your formula for M(n) doesn't work if n is even?

By Pooya Farshim (P2572) on Thursday, September 7, 2000 - 11:23 pm:

Thanks Dan. Good point. I'll think about it.