Given any $1000$ points in the plane, show that there is a circle which contains exactly $500$ of the points in its interior, and none on its circumference.
How do I approach this problem? I feel it has something to do with the pigeonhole principle but I am not able to find the right argument for it.
On
This is just a thought: Proceed by induction. If there are two distinct points, one can find a circle that contains only one of the two points.
Now, suppose there are $2n$ points, and one has a circle that contains exactly $n$ of the points in its interior (and none on the circumference). Add two more points arbitrarily on the plane. If exactly one of the added points is in the circle, you're done.
If both added points are in the circle (or if one is inside and the other is on the circumference), contract the circle until exactly one point leaves the circle. (ETA: Note that this point may not be one of the added points.) Of course, more than one point may leave the circle at the same time, but since none of the points were on the circumference in the original circle, you should be able to translate the circle so that only one point leaves first.
If neither of the added points is in the circle (or if one is outside and the other is on the circumference), expand the circle until exactly one point enters the circle. (ETA: Note here also that this may not be one of the added points.) Again, more than one point may enter at the same time, but you should once more be able to translate the circle so that only one point enters first.
Finally, if both points are on the circumference, translate the circle so that one comes inside and the other goes outside.
On
Assume that the following fact holds:
Lemma. Given $n$ distinct points in the plane, $P_1,\ldots,P_n$, there exists a point $Q$ in the plane such that the distances $QP_1,\ldots,QP_n$ are all distinct.
Then we may assume without loss of generality that $QP_1<QP_2<\ldots<QP_{1000}$, and the circle with centre $Q$ and radius $\frac{QP_{500}+QP_{501}}{2}$ has exactly $500$ points inside it and none on its boundary.
So we just need to prove the lemma. The subset of the plane made by the union of the perpendicular bisectors of $P_i P_j$ for any $i,j\in\{1,\ldots,n\}$ has measure zero, so there is a point $Q$ in its complement fulfilling the lemma.
On
Here is another approach. First, you can draw a line $L$ that splits the plane in two halves, each containing $500$ points. To do this, choose a direction such that no line with this direction contains more that one of the $1000$ points. Then draw a line with this direction which does not contain any of the points. If one the half planes contains more than $500$ points, you can move the line towards it until it passes exactly one point; repeat until the points are equally distributed in both side of the line. Call this line $L$.
Next, you can choose a circle containing all $500$ points on one side of the line. To see this, draw a line segment $S$ perpendicular to $L$, and look at circles tangent to $L$ with center on $S$. Any point of the half-plane belongs to one of these circles; simply choose one that is big enough to contain all $500$ by putting its center far enough from $L$.
Lemma. There is a point in the plane such that no circle with this point as its center can pass through more than one of the given points.
Proof. Draw perpendicular bisectors of the lines between every pair of points. Draw an arbitrary line $\ell$ that has not yet been drawn. Each of the perpendicular bisectors intersect $\ell$ in at most one point, and since $\ell$ has infinitely many points in it, there will be at least one point on $\ell$ that is not on any of the perpendicular bisectors. That point will have the required property. $\Box$
Now, having proved the lemma, imagine the radius of the circle with the chosen center growing slowly from $0$ towards infinity. The number of points inside the circle will increase by one in discrete events. Stop growing the circle after 500 points are inside it.