There are $2015$ points on a plane and no two distances between them are equal. We call the closest $22$ points to a point its $neighbours$. If $k$ points share the same neighbour, what is the maximum value of $k$?
Problem
Source: Turkey TST 2015
Tags: Turkey, TST, 2015, combinatorics
01.04.2015 14:30
The answer is $110$. First fix the point of consideration $X$ and look at all the points (set $A$) that has it as a neighbour. Now do the following: First pick a point $B$ in set $A$ that is furthest away from it. Now we "remove" a region of arc $120^\circ$ (inclusive of the sides that define the arc) such that the picked point is at the centre of it ($AB$ bisects) it. Then in the remaining unremoved region pick a point that is furthest away, and then "remove" a region of arc $120^\circ$ again. Do this until every region is exhausted. Now let the points picked be $B_1,B_2,...,B_k$, in clockwise order. From before we know that $B_1$ removes $120^\circ$ (Call this region $C_1$). Then the $120^\circ$ removed due to $B_2$ must coincide with the region removed of $B_1$, but since $B_2$ is outside of region removed of $B_1$, $B_2$ removes $>60^\circ$ of region (Call this region that is removed $C_2$, $C_2$ does not overlap regions already removed). Continuing this process we see that by $k=5$ all regions will be exhausted. Now note that within each region $C_i$ there are at most $22$ points (as the point $B_i$ is furthest from $X$ in this region, and hence for any point $Y$ in this region, $B_iY<B_iX$). Thus $X$ has at most $110$ neighbours. To construct for $110$, fix a point $X$, and consider rays through it that are $108^\circ$ apart. On this rays mark a point such that each point on the $5$ rays are equidistant to $X$, and then for each marked point place $22$ points that is close to it. For remaining points place them very far from $X$, then $X$ will have $110$ neighbours.