Results 1 to 2 of 2

Math Help - Graph Theory & Combinatorics

  1. #1
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Graph Theory & Combinatorics

    The question is as follows:
    ------------------------------
    What is the maximum number of points of intersection between the diagonals of a convex octagon
    (8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two
    points in its interior lies wholly in the interior of the polygon. Only points of intersection between diagonals
    that lie in the interior of the octagon are to be considered for this problem.

    The answer, given, is 70.

    I cannot find the logic. Help me please!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49

    Re: Graph Theory & Combinatorics


    Each 2-diagonal (joining vertices two steps distant along the perimeter of the octagon) must intersect with 2 others of its kind, plus two 3-diagonals and one 4-diagonal, all emanating from the vertex between on the perimeter.

    There are 8 such 2-diagonals, so multiply the previous numbers by 8, except for the intersections of 2-diagonals with their own kind: that number only by 4.

    Each 3-diagonal must intersect with two 2-diagonals (but these are already counted), plus four 3-diagonals and both 4-diagonals, all emanating from the two vertices between on the perimeter.

    There are 8 such 3-diagonals, so multiply accordingly.

    That leaves intersections with 4-diagonals that are not already counted, which is those with their own kind. Each must intersect all 3 others.
    Last edited by tom@ballooncalculus; May 21st 2012 at 03:56 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: March 30th 2012, 02:27 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. Replies: 2
    Last Post: March 2nd 2011, 05:39 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Combinatorics and number theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 27th 2008, 05:27 AM

Search Tags


/mathhelpforum @mathhelpforum