Yet another tricky question on permutations and combinations

[sankalpmittal]

Homework Statement

In a polygon , no three diagonals are concurrent. If the total number of points of intersection of diagonals interior to the polygon be 70 , then find the number of diagonals of the polygon.
(You must get a numerical value..)

Homework Equations

Number of diagonals of polygon = ⁿC₂-n

The Attempt at a Solution

I tried doing experiment on this question :

Quadrilateral : 2 diagonals : 1 point of intersection
Pentagon : 5 diagonals : 5 points of intersection
Hexagon : 9 diagonals : 13 points of intersection
.
.
.
.

I expected that this will be forming some sort of series , but this did not happen. Also , I tried putting ⁿC₂ = 70 and tried every sort of this thing.

Please help !

Thanks in advance...

 

[I like Serena]

Homework Statement

In a polygon , no three diagonals are concurrent. If the total number of points of intersection of diagonals interior to the polygon be 70 , then find the number of diagonals of the polygon.
(You must get a numerical value..)

Homework Equations

Number of diagonals of polygon = ⁿC₂-n

The Attempt at a Solution

I tried doing experiment on this question :

Quadrilateral : 2 diagonals : 1 point of intersection
Pentagon : 5 diagonals : 5 points of intersection
Hexagon : 9 diagonals : 13 points of intersection
.
.
.
.

I expected that this will be forming some sort of series , but this did not happen. Also , I tried putting ⁿC₂ = 70 and tried every sort of this thing.

Please help !

Thanks in advance...

Hi sankalp! :)

Erm... a hexagon has 15 points of intersection.
Can you continue for at least a heptagon and an octagon?

I guess you'll need a method to count systematically...
How about starting with the leftmost diagonal and counting the intersecting diagonals.
Then the second diagonal and counting the intersecting diagonals.
And so on.
In the end you will have counted each intersection twice if n is odd.
So you'd have to divide by 2.

And actually, there is a simple formula that covers the sequence...

 

[sankalpmittal]

Hi sankalp! :)

Erm... a hexagon has 15 points of intersection.
Can you continue for at least a heptagon and an octagon?

I guess you'll need a method to count systematically...
How about starting with the leftmost diagonal and counting the intersecting diagonals.
Then the second diagonal and counting the intersecting diagonals.
And so on.
In the end you will have counted each intersection twice if n is odd.
So you'd have to divide by 2.

And actually, there is a simple formula that covers the sequence...

Hiiii ILS !

Thanks for your reply !

You helped me , derive a formula !

Quadrilateral : 1 point of intersection = ⁴C₄ points of intersection
Pentagon : 5 points of intersection = ⁵C₄ points of intersection
Hexagon : 15 points of intersection = ⁶C₄ points of intersection
Heptagon : 35 points of intersection = ⁷C₄ points of intersection

Continuing this way :

Polygon will have ⁿC₄ points of intersection...

Thus ⁿC₄ = 70
So n=8

Thus number of diagonals = ⁸C₂-8 = 20

Yep ! I got correct answer.

I am methodically correct , right ?

 

[I like Serena]

Yep ! I got correct answer.

Good! ;)

I am methodically correct , right ?

Hmm, I guess you found the formula by trial and error.
That works in practice.
But you have no guarantee it's actually correct.

For a proper mathematical solution, you'd need to derive or proof the formula itself.

 

[sankalpmittal]

Good! ;)



Hmm, I guess you found the formula by trial and error.
That works in practice.
But you have no guarantee it's actually correct.

For a proper mathematical solution, you'd need to derive or proof the formula itself.

I think I derived the formula experimentally...

May be the question setter was not expecting the students to solve the question the way I did. Is there any other way ? Can you throw me off a hint for that ?

Also , what formula were you mentioning in your first post in this thread that covers all the series ?

I can see the formula I derived on these references , but a condition is imposed on that formula ...

http://www.math.rutgers.edu/~erowland/polygons-project.html
http://blogs.sch.gr/zenonlig/files/2012/04/euromath_ivan_bg_kj.pdf

Thanks again...

 

[I like Serena]

Never mind.

For a problem in an exam you won't have the time to properly derive or prove it.
And if necessary, for this specific problem it suffices to simply (systematically) count the intersections in an octagon, or even just estimate it.
After all, after the heptagon it should be obvious.

I derived $(^n_4)$ myself (for polygons that do not have 3 concurrent diagonals).

Looking at those links, there are a lot of exceptions!
But they do not apply to your current problem, since it is stated that no 3 diagonals are concurrent, while the polygons in the articles are regular.

 

[ehild]

Two intersecting diagonals have 4 terminals. In order to have intersection inside a convex polygon, the endpoints of the diagonals must be at different vertices. You can choose 4 different vertices from an n-sided polygon in $(^n_4)$ ways.
Enumerate the vertices of the polygon, and choose 4 different from them. Let they be P<Q<R<S. You can construct two pairs of line segments: (PQ, RS) and (PR, QS). If the endpoint of the segments are a1, a2 and b1, b2, (so as a1<a2 and b1<b2) b1 and b2 has to be at opposite sides of the segment (a1,a2) so as the segment (b1,b2) intersects (a1,a2) inside the polygon. That means b1<a2. So you have only a single pair of intersecting diagonals for every 4 points, (PR) and (QS), that is one intersection.
It was said that the intersections do not coincide. So you have $(^n_4)$ intersections.

See picture. You choose the vertices 1,3,5,7. The diagonals (1,5) and (3,7) intersect each other inside the polygon, the other pair of diagonals do not.ehild

 

[sankalpmittal]

Two intersecting diagonals have 4 terminals. In order to have intersection inside a convex polygon, the endpoints of the diagonals must be at different vertices. You can choose 4 different vertices from an n-sided polygon in $(^n_4)$ ways.
Enumerate the vertices of the polygon, and choose 4 different from them. Let they be P<Q<R<S. You can construct two pairs of line segments: (PQ, RS) and (PR, QS). If the endpoint of the segments are a1, a2 and b1, b2, (so as a1<a2 and b1<b2) b1 and b2 has to be at opposite sides of the segment (a1,a2) so as the segment (b1,b2) intersects (a1,a2) inside the polygon. That means b1<a2. So you have only a single pair of intersecting diagonals for every 4 points, (PR) and (QS), that is one intersection.
It was said that the intersections do not coincide. So you have $(^n_4)$ intersections.

See picture. You choose the vertices 1,3,5,7. The diagonals (1,5) and (3,7) intersect each other inside the polygon, the other pair of diagonals do not.


ehild

Thanks ILS and ehild , for such insights ! And apologies for late reply. I come online but rarely...