Let $O$ be a point (in the plane) and $T$ be an infinite set of points such that $|P_1P_2| \le 2012$ for every two distinct points $P_1,P_2\in T$. Let $S(T)$ be the set of points $Q$ in the plane satisfying $|QP| \le 2013$ for at least one point $P\in T$. Now let $L$ be the set of lines containing exactly one point of $S(T)$. Call a line $\ell_0$ passing through $O$ bad if there does not exist a line $\ell\in L$ parallel to (or coinciding with) $\ell_0$. (a) Prove that $L$ is nonempty. (b) Prove that one can assign a line $\ell(i)$ to each positive integer $i$ so that for every bad line $\ell_0$ passing through $O$, there exists a positive integer $n$ with $\ell(n) = \ell_0$. Proposed by David Yang
Problem
Source: ELMO Shortlist 2013: Problem G14, by David Yang
Tags: function, geometry, perimeter, geometry unsolved
24.07.2013 16:48
a) Choose an arbitrary point $T_0$ in $T$ and define the function $d(X)$ for $X \in S(T)$ to be the distance from $X$ to $T_0$. Notice $S(T)$ is bounded, in particular by a circle of radius $2012 + 2013 = 4025$ centered at $T_0$, and is closed - for any convergent sequence of points in $S(T)$ whose limit has distance strictly more than $2013$ from all points in $T$ we can find some point far enough along in the sequence that it too has distance strictly more than $2013$ from all points in $T$, contradicting its membership in $S(T)$. Then $S(T)$ is a compact set, so the continuous function $d$ on $S(T)$ attains a maximum at some point $S_0$; it's easy to see that the line through $S_0$ perpendicular to $T_0S_0$ will do the trick. b) If a line $\ell_0$ through $O$ is bad, when we sweep lines parallel to $\ell_0$ across the plane each one that intersects $S(T)$ intersects it multiple times; of course this means it intersects the convex envelope of $S(T)$ multiple times. This corresponds to a line segment in the convex envelope (from the definition of convexity) of positive length; it's therefore equivalent to show there are only countably many (positive length) line segments in the convex envelope of $S(T)$. Suppose, for the sake of contradiction, there were an uncountably infinite number of (positive length) line segments. Lemma : The sum of an uncountably infinite set $S$ of strictly positive numbers is infinite. Proof: Argue by contradiction and assume it were finite and equal to some $M$. For each $n \in \mathbb{N}$ the set $\{x \in S | x > 1/n \}$ is finite (in particular, has size at most $Mn$) and the union of these sets is $S$. Yet the countable union of finite sets is countable, contradicting the uncountability of $S$. It follows that the convex envelope of $S(T)$ must have infinite perimeter, but finite area (from the boundedness of $S(T)$). But consider the set $S'(T)$ of points which are within some $\epsilon > 0$ of some point in $S(T)$; clearly this figure has bounded area as well, and by convexity \[[S'(T)] - [S(T)] \ge P\epsilon\] where $P$ is the perimeter of the convex envelope of $S(T)$. This contradicts the fact that $S(T)$ has infinite perimeter, from which it follows that the of bad lines is countable.
08.04.2019 15:47
Quote: for any convergent sequence of points in $S(T)$ whose limit has distance strictly more than $2013$ from all points in $T$ we can find some point far enough along in the sequence that it too has distance strictly more than $2013$ from all points in $T$, contradicting its membership in $S(T)$. This statement is actually wrong, together with the problem itself. Since $T$ is not given to be a compact set, a convergent sequence in $S(T)$ may attain a limit point who has distance $>2013$ for any point in $T$ while the infimum of these distances being $2013$. An example may be constructed by taking $T=\{(x,y) \mid x^2+y^2<4\}$, which yields $S(T)= \{(x,y) \mid x^2+y^2<2015^2\}$, not a compact set. It should also be noted that the above construction actually illustrates a counterexample for a), in the sense that any line non-intersecting or tangent to the circle $x^2+y^2=2015^2$ passes through none of the points in $S(T)$, while any line intersecting it passes through exactly two points. In this case, $L$ is empty, so a) is wrong, let alone b). A reasonable modification would be to assume further that $T$ is compact. Under such condition, taking the mimimum distance of the sequence in $S(T)$ would get, as hyperbolictangent did, that $S(T)$ is compact and finish the problem in the same way.