1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Yet another tricky question on permutations and combinations

  1. Dec 31, 2012 #1
    1. The problem statement, all variables and given/known data

    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..)

    2. Relevant equations

    Number of diagonals of polygon = nC2-n

    3. 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 nC2 = 70 and tried every sort of this thing.

    Please help !!

    Thanks in advance... :smile:
  2. jcsd
  3. Dec 31, 2012 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi sankalp! :)

    Erm... a hexagon has 15 points of intersection. :surprised
    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...
  4. Dec 31, 2012 #3
    Hiiii ILS !!

    Thanks for your reply !! :smile:

    You helped me , derive a formula !!

    Quadrilateral : 1 point of intersection = 4C4 points of intersection
    Pentagon : 5 points of intersection = 5C4 points of intersection
    Hexagon : 15 points of intersection = 6C4 points of intersection
    Heptagon : 35 points of intersection = 7C4 points of intersection

    Continuing this way :

    Polygon will have nC4 points of intersection....

    Thus nC4 = 70
    So n=8

    Thus number of diagonals = 8C2-8 = 20

    Yep !! I got correct answer.

    I am methodically correct , right ?
  5. Dec 31, 2012 #4

    I like Serena

    User Avatar
    Homework Helper

    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.
  6. Jan 1, 2013 #5
    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 [Broken]

    Thanks again...
    Last edited by a moderator: May 6, 2017
  7. Jan 1, 2013 #6

    I like Serena

    User Avatar
    Homework Helper

    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.
  8. Jan 1, 2013 #7


    User Avatar
    Homework Helper

    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 [itex](^n_4)[/itex] 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 [itex](^n_4)[/itex] 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.


    Attached Files:

  9. Jan 6, 2013 #8
    Thanks ILS and ehild , for such insights ! And apologies for late reply. I come online but rarely... :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook