Results 1 to 4 of 4

Math Help - Points in the Plane and the Pigeonhole Principal

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    130

    Points in the Plane and the Pigeonhole Principal

    Hey everyone.

    I have 24 points in the plane. If I pick 3 of them, 2 of them are distance less than 1 apart. I need to show that i can draw a circle of radius 1 so that 13 points are in the circle.

    I have tried several ways:
    First I drew two points distance greater than 1 apart. I draw a circle of radius 1 centered at each of these points. Then I place the remaining 22, 11 in each circle. I try to show that there must be some intersection with the 2 circles and that there is some point in the intersection. Then a circle of unit radius centered at the intersection point would definitely contain 13 points. But I can't show this.

    Second I thought in the language of graph theory. Let the 24 points be vertices of a graph. If 2 vertices are distance less than 1 apart then draw an edge between them. If I can show that the graph always contains the complete graph on 13 vertices then I am finished. But I have no idea how to count the minimum number of edges in a graph satisfying the problem's conditions. 24 choose 3 is an upper bound. If I could calculate the minimum number of edges perhaps I could use the pigeonhole principal to show that the graph must contain the complete graph on 13 vertices.

    Third: let G be a graph as above. If we can show that some vertex has degree 13 then we have shown a stronger condition: that 13 points fit in a circle of radius 1/2. This probably isn't true but I thought about proving it because it seems more straightforward.

    Any new ideas or ideas on how to finish any of these attacks?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by robeuler View Post
    Hey everyone.

    I have 24 points in the plane. If I pick 3 of them, 2 of them are distance less than 1 apart. I need to show that i can draw a circle of radius 1 so that 13 points are in the circle.

    I have tried several ways:
    First I drew two points distance greater than 1 apart. I draw a circle of radius 1 centered at each of these points. Then I place the remaining 22, 11 in each circle. I try to show that there must be some intersection with the 2 circles and that there is some point in the intersection. Then a circle of unit radius centered at the intersection point would definitely contain 13 points. But I can't show this.

    Second I thought in the language of graph theory. Let the 24 points be vertices of a graph. If 2 vertices are distance less than 1 apart then draw an edge between them. If I can show that the graph always contains the complete graph on 13 vertices then I am finished. But I have no idea how to count the minimum number of edges in a graph satisfying the problem's conditions. 24 choose 3 is an upper bound. If I could calculate the minimum number of edges perhaps I could use the pigeonhole principal to show that the graph must contain the complete graph on 13 vertices.

    Third: let G be a graph as above. If we can show that some vertex has degree 13 then we have shown a stronger condition: that 13 points fit in a circle of radius 1/2. This probably isn't true but I thought about proving it because it seems more straightforward.

    Any new ideas or ideas on how to finish any of these attacks?

    Consider this - I draw two circles of radius 0.25m with their center say 100m apart. Now put 12 points in each. This construction meets your requirement. But I will never be able to draw a circle of radius 1 with 13 points in it. So is your question correct? Or I'm just messing up?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2008
    Posts
    130
    Quote Originally Posted by aman_cc View Post
    Consider this - I draw two circles of radius 0.25m with their center say 100m apart. Now put 12 points in each. This construction meets your requirement. But I will never be able to draw a circle of radius 1 with 13 points in it. So is your question correct? Or I'm just messing up?
    Whoops! I meant to write 25 points total! Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by robeuler View Post
    Whoops! I meant to write 25 points total! Thanks!
    Ok. Then take P0 and draw a circle of radius 1 with center P0. Call it C1.

    Case1: Circle C1 has 13 points - we are done
    Case2: Circle C1 has<13 point. So we have at least 13 point outside the circle C1. say P1, P2,....P13. Now, distance(P1,Pi) < 1 for all i in {2,...,13}. Else I can select P0,P1,Pi with no two < 1. So if I draw a circle of radius 1 around P1 I will be done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Product of non principal ideals is principal.
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: June 12th 2011, 02:17 PM
  2. [SOLVED] points in a plane
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 6th 2011, 07:55 AM
  3. Plane through 3 given Points
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 3rd 2010, 01:24 AM
  4. Replies: 0
    Last Post: November 19th 2008, 07:04 AM
  5. Points in the plane.
    Posted in the Geometry Forum
    Replies: 5
    Last Post: August 16th 2008, 01:24 PM

Search Tags


/mathhelpforum @mathhelpforum