Results 1 to 10 of 10

Math Help - Intersection Points in a Circle

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    11

    Unhappy Intersection Points in a Circle

    A chord is drawn between every two point on the perimeter of a circle. There are n points on the perimeter. Every two chords intersect at a point either on the perimeter or inside the circle.

    (a) Determine the number of chords drawn

    -- (n choose 2)

    (b) What is the maximum number of intersection points inside the circle?

    -- For this one I keep ending up in an infinite loop and drawing increasingly harder circles. Can someone point me in the correct direction?

    I have (n*(n-1)) + (n-3)n - n + (n-4)n - n....

    I don't know how to show when to stop.

    (c) What is the maximum number of chords which can go through any single intersection point inside the circle?

    --I don't even know where to begin here.



    Any help would be greatly appreciated!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by zachsch View Post
    A chord is drawn between every two point on the perimeter of a circle. There are n points on the perimeter. Every two chords intersect at a point either on the perimeter or inside the circle.

    (a) Determine the number of chords drawn

    -- (n choose 2)

    (b) What is the maximum number of intersection points inside the circle?

    -- For this one I keep ending up in an infinite loop and drawing increasingly harder circles. Can someone point me in the correct direction?

    I have (n*(n-1)) + (n-3)n - n + (n-4)n - n....

    I don't know how to show when to stop.

    (c) What is the maximum number of chords which can go through any single intersection point inside the circle?

    --I don't even know where to begin here.



    Any help would be greatly appreciated!!!

    You got a right.

    b ) is a bit tricky. You have to use a counting trick. Consider any two points A,B along the circle. Then the chord AB splits the circle into a minor arc and a major arc (that is a bigger arc and a smaller arc.) The only chords that intersect AB inside the circle are coords that are formed by one point on the major arc and one point on the minor arc. If there are k points on the minor arc, there are k(n-2-k) chords that can be formed that will intersect AB inside the circle.

    This implies that the total number of intersections inside the circle are at most:

    \sum _{k=0} ^{n-2} k (n-2-k)  = \sum _{k=0} ^{n-2} k (n-2) - \sum _{k=0} ^{n-2} k^2  = \frac{(n-2)^2 (n-1)}{2} - \frac { (n-2)(n-1)(2n-3)}{6} you can simplify it further.


    c) this is easy; you just need to make the following observation, if two chords share the same two endpoints it is the same chord. If two chords share one endpoint, they have to intersect on the circle and can not possibly intersect in the same point INSIDE the circle. Since you can not reuse one point to make multiple chords that will go through the same intersection point inside the circle, this means that at most \lfloor n/2 \rfloor chords can intersect in the same point inside the circle.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    11
    Thank you so much!

    Can you just clarify where you got "k(n-2-k)" from in part b? I'm pretty much good until then.


    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    Posts
    95
    Think about it carefully, you have points A, B. Then on the minor arc there are k points between A and B. That means there are n -2 -k points on the major arc. Now you can pair each of the points on the minor arc with each of the points on the major arc, yeilding k (n-2-k) possible chords
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    11
    Ah ha. Thank youu!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,919
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by gmatt View Post
    This implies that the total number of intersections inside the circle are at most:
    \sum _{k=0} ^{n-2} k (n-2-k)  = \sum _{k=0} ^{n-2} k (n-2) - \sum _{k=0} ^{n-2} k^2  = \frac{(n-2)^2 (n-1)}{2} - \frac { (n-2)(n-1)(2n-3)}{6} you can simplify it further.
    gmatt.
    Does your formula work for n=5 or n=6?
    I think not. It gives 4 for n=5. The correct answer is 5.
    The case for n=6 is easy to draw also.
    Now maybe I have missread the question?
    Attached Thumbnails Attached Thumbnails Intersection Points in a Circle-untitled.gif  
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by Plato View Post
    gmatt.
    Does your formula work for n=5 or n=6?
    I think not. It gives 4 for n=5. The correct answer is 5.
    The case for n=6 is easy to draw also.
    Now maybe I have missread the question?

    well spoted!

    I have to think about this some more.

    ahh ok, I am missing a important part, I'll add it in a bit.
    Last edited by gmatt; December 7th 2009 at 05:33 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2009
    Posts
    11
    Should the number include the points where the chords intersect the perimeter?

    So for n=3, you have 6 intersection points?

    "Every two chords intersect at a point either on the perimeter or inside the circle."
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2009
    Posts
    95
    Sorry about the confusion.

    The actual formula that you want is

    <br />
\sum_ {i=0} ^{(n-2)} \sum _{k=0} ^{(n-2 - i)} k (n-2-k -i)<br />

    This one is more difficult to simplify, but not impossible. You can try simplifying it using known summation formulas.

    All you need is the following formulas to simplify

    \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}

    \sum_{i=1}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4} = \left[\sum_{i=1}^n i\right]^2
    Last edited by gmatt; December 7th 2009 at 08:25 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2009
    Posts
    95
    oh, wow. I just plugged in that fancy formula I got into wolfram alpha

    .....


    the answer is :

     \sum_ {i=0} ^{(n-2)} \sum _{k=0} ^{(n-2 - i)} k (n-2-k -i) = \frac{1}{24}(n-3)(n-2)(n-1)n = \binom{n}{4}

    hahah!

    that makes perfect sense, you want to choose 4 vertices, of n vertices to get the maximum possible amount of intersections inside the circle. (Comes back to the idea that if you have 2 chords sharing one vertex they can not intersect inside.)

    well that was a fun excercise, I came up with an identity for \binom {n}{4} that is non-trivial.

    This should teach you to try counting simply before messing with sums
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Points of intersection, circle and parabola
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: July 10th 2010, 05:12 AM
  2. Replies: 4
    Last Post: May 2nd 2010, 04:34 PM
  3. Intersection points
    Posted in the Geometry Forum
    Replies: 2
    Last Post: March 25th 2010, 05:56 PM
  4. Replies: 7
    Last Post: March 15th 2010, 05:10 PM
  5. circle intersection, find points
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: December 12th 2008, 11:57 AM

Search Tags


/mathhelpforum @mathhelpforum