Prove that there is a circle containing exactly $2018$ points

141 Views Asked by At

Problem

Given a set $\mathtt{E}$ containing $2017^{2019}$ points on the plane. Prove that there is a circle containing exactly $2018$ points from the set $\mathtt{E}$ (these points are on the open disk).

[Maths Olympiad (Morocco $2018$)]

My Approach
It's enough to find a line dividing the plane into two parts, the first one contains $2018$ points of $\mathtt{E}$, and the other contains the rest of the points of $\mathtt{E}$. As we can take a circle tangent to this line and with a radius big enough. I wasn't able to prove this, but it seems true, and it seems that we can somehow use pigeonhole principle to prove it.

1

There are 1 best solutions below

2
On BEST ANSWER

Your idea is good, and you just need to find the simplest rigorous way forward. One way is as follows: Take any ray $L$ with $2018$ points on its left. (I leave you to figure out how to rigorously prove the existence of such $L$.) Let $P$ be a point on $L$. Let $C(k)$ be the circle on the left of $L$ that is tangent to $L$ at $P$. Clearly $C(k+1)$ encircles at least as many points in $E$ as $C(k)$. But $E$ is finite, so $C(k)$ can only increase finitely many times as $k$ increases. Thus $C(m)$ for some $m$ encircles all the points in $E$.