$2015$ points are given in a plane such that from any five points we can choose two points with distance less than $1$ unit. Prove that $504$ of the given points lie on a unit disc.
Problem
Source: JBMO Shortlist 2015 C2
Tags: combinatorics, combinatorial geometry, points, distance
25.04.2019 20:15
Denote $P=\{A_1,A_2,\dots,A_{2015}\}$ the set of the $2015$ given points. Renumbering the points, let $S=\{A_1, A_2,\dots,A_k\}\subset P$ a set with the maximal cardinal, with the property $Q$: $A_iA_j\ge1, \forall 1\le i<j\le k$. Using the initial condition, results $k\le4$. Case 1: $\quad 2\le k\le4$. $\forall p\in\mathbb{N}, k+1\le p\le 2015$, results: the set $S\cup \{A_p\}$ does not have the property $Q$, hence in the set $S$ exists a point $A_i, 1\le i\le k$ such that $A_iA_p<1$. Denote $P_1=\{A_m\in P| A_1A_m<1\}$ (consider $A_1\in P_1$) and similarly $P_2,\dots, P_k$. Results: $P_1\cup P_2 \dots\cup P_k=P$. $\max_{1\le i\le k}{\{|P_i|}\}\ge \left\lceil\dfrac{2015}{k}\right\rceil\ge \left\lceil\dfrac{2015}{4}\right\rceil=504$. WLOG, we can consider $|P_1|\ge 504$. Hence, the disc with the center in $A_1$ and radius $1$ contains at least $504$ points. Case 2: $k=0\Longleftrightarrow A_iA_j<1,\forall 1\le i<j\le2015$. Results: all the $2015$ points of $P$ are situated in the disc with the center $A_1$ and the radius $1$.
20.03.2020 04:24
Choose 4 points.We ste left with 2011 points so we can choose 2011 sets of five points which consists 4 points we chose.2011 = 4×502 + 3 There is a point (name it point A)that has 503 other points that are at most 1 distanced from it.We draw a circle(disc) with center A radius 1,so we have a disc radius 1 which consists 504 points Sorry for bad English,hope you understand
30.06.2021 01:30
macka wrote: Choose 4 points.We ste left with 2011 points so we can choose 2011 sets of five points which consists 4 points we chose.2011 = 4×502 + 3 There is a point (name it point A)that has 503 other points that are at most 1 distanced from it.We draw a circle(disc) with center A radius 1,so we have a disc radius 1 which consists 504 points Sorry for bad English,hope you understand I think your answer is incomplete, What if one can pick two points out of 4 points you chose first that the distance between them is less than 1? But it is not that hard to solve from where you dropped. If we can't pick 4 points that each pairwise distance is greater than one, it means that original question is true not only for five picked points, but four picked points too. Than we try to choose 3 points that the distance between each pair of them is greater than one then we can choose the forth point out of 2012 left points. By Pigeon principle There is a point (name it point A)that has 503 (actually even more but 503 is enough for this part) other points that are at most 1 distanced from it.We draw a circle(disc) with center A radius 1,so we have a disc radius 1 which consists 504 points. If we cant pick 3 points that the distance between all of them is greater than one, then the condition is true for 3 points and if we can pick 2 points that the distance is greater than one, we can finish the question by Pigeonhole Principle again, and if we can't then distance between each two point is less than one than we can pick any point(name it point B) and all points are at most 1 distanced from it. We draw a circle(disc) with center B radius 1,so we have a disc radius 1 which consists 2015 points. ps. Sorry for my bad English too.