# Points in the Plane and the Pigeonhole Principal

• Nov 18th 2009, 09:02 AM
robeuler
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?
• Nov 18th 2009, 09:25 AM
aman_cc
Quote:

Originally Posted by robeuler
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?
• Nov 18th 2009, 09:46 AM
robeuler
Quote:

Originally Posted by aman_cc
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!
• Nov 18th 2009, 09:55 AM
aman_cc
Quote:

Originally Posted by robeuler
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.