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?