Team Selection Test Selection Test

(By Adam Hesterberg). Without loss of generality we may consider points $(x, y)$ with $x > y > 0$. For any $c$, let $d = \frac{c}{2} \log(x^2 + y^2 + 2)$. Choose $c$ large enough that
$$c > \frac{\sqrt{2}}{\log(2)} \quad \text{and} \quad d \ge \max\{9 \cdot 20 \cdot 21, 21 + 21 \log(x)\}.$$
We claim that $(x, y)$ lies within distance $2d = c \log(x^2+y^2+2)$ of a lattice point $(m, n)$ with relatively prime coordinates.

If $y < 1$, then $(x, y)$ is at distance at most $\sqrt{2} < c \log(2) < 2d$ from the point $(\lfloor x \rfloor, 1)$, which has relatively prime coordinates. Otherwise, consider the points $(a, b) \in \mathbb{Z}^2$ with $\lfloor x \rfloor \le a < \lfloor x + d \rfloor$ and $\lfloor y \rfloor \le b < \lfloor y + d \rfloor$, all of which are within distance $2d$ of $(x, y)$. The number of such pairs with a common factor of $k$ is at most $(d/k + 1)^2$, so the number of pairs with a common factor between 2 and $d$ is at most
$$\sum_{k=2}^{\lfloor d \rfloor} \left( \frac{d}{k} + 1 \right)^2 = d^2 \sum_{k=2}^{\lfloor d \rfloor} \frac{1}{k^2} + 2d \sum_{k=2}^{\lfloor d \rfloor} \frac{1}{k} + \lfloor d \rfloor.$$
We have now the estimates
$$\sum_{k=2}^{\lfloor d \rfloor} \frac{1}{k^2} \le \frac{1}{4} + \sum_{k=3}^{\lfloor d \rfloor} \frac{1}{k(k-1)} = \frac{1}{4} + \sum_{k=3}^{\lfloor d \rfloor} \left( \frac{1}{k-1} - \frac{1}{k} \right) \le \frac{1}{4} + \frac{1}{2} - \frac{1}{\lfloor d \rfloor} \le \frac{3}{4} \quad (17)$$
and
$$\sum_{k=2}^{\lfloor d \rfloor} \frac{1}{k} \le 4 + \sum_{k=10}^{\lfloor d \rfloor} \frac{1}{k} \le 4 + \frac{d}{10}. \quad (18)$$
Applying the estimates (17) and (18), we find that the number of pairs with a common factor between 2 and $d$ is at most
$$d^2 \sum_{k=2}^{\lfloor d \rfloor} \frac{1}{k^2} + 2d \sum_{k=2}^{\lfloor d \rfloor} \frac{1}{k} + \lfloor d \rfloor \le \frac{3}{4}d^2 + \frac{2d^2}{10} + 8d + d = \frac{19}{20}d^2 + 9d \le \frac{20}{21}d^2,$$
where the final inequality holds because we chose $d \ge 9 \cdot 20 \cdot 21$.

Therefore, at least $\frac{d^2}{21}$ of the pairs have no common factor between 2 and $d$. By the pigeonhole principle there exists $a$ with $\lfloor x \rfloor \le a < \lfloor x + d \rfloor$ such that at least $\frac{d}{21}$ of the lattice points $(a, b)$ with $\lfloor y \rfloor \le b < \lfloor y + d \rfloor$ have no common factor at most $d$. Hence either some $(a, b)$ is the desired point with relatively prime coordinates, or each such $b$ has a prime factor greater than $d$ in common with $a$. These prime factors must be distinct, since the different values of $b$ differ by at most $d$. Hence $a$ is divisible by their product, which is at least $d^{\frac{d}{21}}$. But this shows that
$$dx > x + d > a \ge d^{\frac{d}{21}} \ge d^{1+\log(x)} > dx,$$
where the first inequality holds because $x > y > 1$, the third because $d$ was chosen so that $d \ge 21 + 21 \log(x)$, and the last because $d > e$, meaning $d^{\log(x)} > e^{\log(x)} = e$. This is a contradiction. Thus, there must have been some point $(a, b)$ with relatively prime coordinates.