International Mathematical Olympiad China National Team Selection Test, 2025

Proof 1: Take $x_i = 3^i$, $y_i = 9^i$ ($i = 1, 2, \dots, 10$). We show these satisfy the conditions. (1) and (2) are obvious. For (3), we use:
Lemma: If real numbers $z_1, \dots, z_m$ satisfy $|z_{i+1}| \ge 2|z_i|$ for $i = 1, 2, \dots, m-1$, then for any $r_1, \dots, r_m \in \{-1, 0, 1\}$ not all zero, $|\sum_{i=1}^m r_i z_i| \ge |z_1|$.
If our construction fails (3), some strip $\{(x, y) | c \le y - kx \le c + \sqrt{k^2+1}\}$ contains at least 3 points. Let these be:
$$A = \left( \sum u_i 3^i, \sum u_i 9^i \right), \quad B = \left( \sum v_i 3^i, \sum v_i 9^i \right), \quad C = \left( \sum w_i 3^i, \sum w_i 9^i \right).$$
Then $|\sum(u_i - v_i)(9^i - k3^i)| \le \sqrt{k^2+1}$ etc.
If $k \le 7$, assume $u_1 = v_1$. Since $9^{i+1} - k3^{i+1} > 2(9^i - k3^i)$ for $i \ge 2$ and $9^2 - k3^2 > \sqrt{k^2+1}$, contradiction!
If $k > 7 \cdot 3^8$, assume $u_{10} = v_{10}$. Since $k3^{i+1} - 9^{i+1} > 2(k3^i - 9^i)$ for $i \le 8$ and $3k - 9 > \sqrt{k^2+1}$, contradiction!
For $7 < k \le 7 \cdot 3^8$, let $7 \cdot 3^d < k \le 7 \cdot 3^{d+1}$ ($0 \le d \le 7$) and assume $u_{d+2} = v_{d+2}$. We have:
$$\begin{align*} 9^{i+1} - k3^{i+1} &> 2(9^i - k3^i) \quad (i \ge d+3); \\ 9^{d+3} - k3^{d+3} &> 2(k3^{d+1} - 9^{d+1}); \\ k3^{i+1} - 9^{i+1} &> 2(k3^i - 9^i) \quad (i \le d); \\ 3k - 9 &> \sqrt{k^2+1}, \end{align*}$$
again a contradiction. Thus the construction works. □

Proof 2: Take $x_i = 3^i$ and $y_i = 9^i$ as in Solution 1. We now verify condition (3). First observe that the ordering of points in $X$ by their $x$-coordinates coincides with their ordering by $y$-coordinates.

Assume for contradiction that there exist three distinct points $P_1, P_2, P_3 \in X$ lying between two parallel lines $l_1$ and $l_2$ at distance 1 apart. For $j = 1, 2, 3$, let:
$$P_j = (x_j, y_j) = \left( \sum_{i=1}^{10} a_i^{(j)} 3^i, \sum_{i=1}^{10} a_i^{(j)} 9^i \right), \qquad (1)$$
where $a_i^{(j)} \in \{0, 1\}$ for $i = 1, \dots, 10$ and $j = 1, 2, 3$. Without loss of generality, assume $x_1 > x_2 > x_3$.
For each $j = 1, 2, 3$, let $i_j$ be the largest index $i$ with $a_i^{(j)} = 1$. Then $i_1 \ge i_2 \ge i_3$. We may assume $(P_1, P_2, P_3)$ is a minimal counterexample with respect to $(i_1, i_2, i_3)$. Let:
$$L_x = \sum_{k=1}^{i_1} 3^k, \quad L_y = \sum_{k=1}^{i_1} 9^k.$$
If $i_1 = i_2$, then the points:
$$(L_x - x_3, L_y - y_3), \quad (L_x - x_2, L_y - y_2), \quad (L_x - x_1, L_y - y_1)$$
also lie in $X$ and satisfy the same strip condition (being symmetric reflections of $P_1, P_2, P_3$ about $(\frac{L_x}{2}, \frac{L_y}{2})$). This contradicts the minimality of $(i_1, i_2, i_3)$. Hence $i_1 > i_2 \ge i_3$, and in particular $i_1 \ge 2$.
Let $P'_j = (x'_j, y'_j)$ be the projection of $P_j$ onto $l_1$. Since $l_1$ and $l_2$ are distance 1 apart, we have $|x_j - x'_j| \le 1$ and $|y_j - y'_j| \le 1$. Therefore:
$$\frac{y'_1 - y'_2}{x'_1 - x'_2} = \frac{y'_2 - y'_3}{x'_2 - x'_3}.$$
Lemma 1: $\frac{y'_1 - y'_2}{x'_1 - x'_2} \ge \frac{\frac{9}{8} \cdot 9^{i_1} - \frac{17}{8}}{\frac{3}{2} \cdot 3^{i_1} - \frac{1}{2}}$.
Proof: From (1) we have:
$$\frac{y_1 - y_2}{x'_1 - x'_2} \ge \frac{y_1 - y_2 - 2}{x_1 - x_2 + 2} = \frac{9^{i_1} + \sum_{k=1}^{i_1-1} (a_k^{(1)} - a_k^{(2)}) 9^k - 1}{3^{i_1} + \sum_{k=1}^{i_1-1} (a_k^{(1)} - a_k^{(2)}) 3^k + 1}.$$
Since $i_1 \ge 2$ and $\frac{9^{k-1}}{3^{k+1}} > \frac{9^{k-1}}{3^{k-1}} > \dots > 3$ for $k \ge 1$, and $a_k^{(1)} - a_k^{(2)} \in \{-1, 0, 1\}$, by the "Fraction Inequality" we get:
$$\frac{y'_1 - y'_2}{x'_1 - x'_2} \ge \frac{\sum_{k=1}^{i_1} 9^k - 1}{\sum_{k=1}^{i_1} 3^k + 1} = \frac{\frac{9}{8} \cdot 9^{i_1} - \frac{17}{8}}{\frac{3}{2} \cdot 3^{i_1} - \frac{1}{2}}.$$
Lemma 2: $\frac{y'_2 - y'_3}{x'_2 - x'_3} \le \frac{\frac{7}{8} \cdot 9^{i_1-1} + \frac{17}{8}}{\frac{1}{2} \cdot 3^{i_1-1} + \frac{1}{2}}$.
Proof: From (1) we have:
$$\frac{y_2' - y_3'}{x_2' - x_3'} \le \frac{y_2 - y_3 + 2}{x_2 - x_3 - 2} = \frac{\sum_{k=1}^{i_2} (a_k^{(2)} - a_k^{(3)}) 9^k + 1}{\sum_{k=1}^{i_2} (a_k^{(2)} - a_k^{(3)}) 3^k - 1}.$$
Let $s$ be the largest index with $a_s^{(2)} \neq a_s^{(3)}$. Since $x_2 > x_3$ and $i_1 > i_2$, we have $1 \le s \le i_1 - 1$. Noting that $\frac{9^{s+1}}{3^{s-1}} > \frac{9^{s-1}}{3^{s-1}} > \cdots > 3$ and $a_k^{(2)} - a_k^{(3)} \in \{-1, 0, 1\}$, by the Fraction Inequality:
$$\frac{y_2' - y_3'}{x_2' - x_3'} \le \frac{9^s - \sum_{k=1}^{s-1} 9^k + 1}{3^s - \sum_{k=1}^{s-1} 3^k - 1} = \frac{\frac{7}{8} \cdot 9^s + \frac{17}{8}}{\frac{1}{2} \cdot 3^s + \frac{1}{2}} \le \frac{\frac{7}{8} \cdot 9^{i_1-1} + \frac{17}{8}}{\frac{1}{2} \cdot 3^{i_1-1} + \frac{1}{2}}.$$
Returning to the main proof, for $i_1 \ge 2$ we have:
$$\frac{\frac{9}{8} \cdot 9^{i_1} - \frac{17}{8}}{\frac{3}{2} \cdot 3^{i_1} - \frac{1}{2}} > \frac{\frac{7}{8} \cdot 9^{i_1-1} + \frac{17}{8}}{\frac{1}{2} \cdot 3^{i_1-1} + \frac{1}{2}}.$$
(Note the dominant terms satisfy $\frac{9}{8}\frac{9^{i_1}}{3^3 3^{i_1}} = \frac{3}{4}3^{i_1} > \frac{7}{4}3^{i_1-1} = \frac{7}{8}\frac{9^{i_1-1}}{3^3 3^{i_1-1}}$, and the case $i_1 = 2$ can be verified directly.) This contradicts the equality derived from Lemmas 1 and 2. □

Proof 3: Let $d(P, \ell)$ denote the distance from point $P$ to line $\ell$.
If a strip of width 1 contains three points $A, B, C$, then one point (the middle one in the projection onto the boundary lines) has distance $\le 1$ to the line through the other two points. That is, the height from $A$ to $BC$ is $\le 1$ in $\triangle ABC$. Since $|AB| + |AC| \ge |BC|$, at least one of $AB$ or $AC$ has length $\ge \frac{1}{2}|BC|$, making the corresponding height $\le 2$.
We call an ordered triple $(A, B, C)$ a bad triple if $d(A, BC) \le 2$ and $d(B, CA) \le 2$. (If at least two points coincide or all three are colinear, any ordering is bad.)
Let $L = 10^{10}$ and consider the grid:
$$\Omega = \{(x, y) \in \mathbb{Z}^2 : |x| \le L, |y| \le L\}.$$
Randomly and independently select 10 vectors $\alpha_i = (x_i, y_i) \in \Omega$. For each subset $I \subseteq \{1, \dots, 10\}$, define the point $P_I = \sum_{i \in I} \alpha_i$.
We want to show that with positive probability, no three points in $\{P_I\}$ form a bad triple, thus satisfying the requirement.
For any three distinct subsets $I_1, I_2, I_3$, consider the probability that $(P_{I_1}, P_{I_2}, P_{I_3})$ is bad (equivalent to $(P_{I_2}, P_{I_1}, P_{I_3})$ being bad).
Since $I_1 \ne I_2$, there exists some index $k$ in exactly one of them. Without loss of generality, assume $k \in I_1$ and $k \notin I_2$. Consider two cases:
Case 1: $k \notin I_3$ ($k \in I_1$ only). We bound $\mathbb{P}(d(P_{I_1}, P_{I_2}, P_{I_3}) \le 2)$. First fix $\alpha_i$ for $i \ne k$ randomly. The probability that $P_{I_2} = P_{I_3}$ is $\le \frac{1}{|\Omega|}$ (since any differing coordinate would require specific values). If $P_{I_2} \neq P_{I_3}$, then $d(P_{I_1}, P_{I_2}P_{I_3}) \le 2$ requires $\alpha_k$ to lie in a strip $D$ of width 4 after translation.
If $D$ has slope $\le 1$, each vertical line in $\Omega$ contains at most $\lceil 4\sqrt{2} \rceil = 6$ points of $D$. If slope $> 1$, each horizontal line contains at most 6 points. Thus:
$$\mathbb{P}(d(P_{I_1}, P_{I_2}P_{I_3}) \le 2) \le \frac{1}{|\Omega|} + \frac{6(2L+1)}{|\Omega|} \le \frac{3}{L}.$$
Case 2: $k \in I_3$ ($k \in I_1 \cap I_3$). Consider complements $J_r = I_r^c$. The triangles $\triangle P_{I_1}P_{I_2}P_{I_3}$ and $\triangle P_{J_1}P_{J_2}P_{J_3}$ are congruent (central symmetric). Thus:
$$\mathbb{P}(d(P_{I_2}, P_{I_1}P_{I_3}) \le 2) = \mathbb{P}(d(P_{J_2}, P_{J_1}P_{J_3}) \le 2) \le \frac{3}{L}.$$
For any three distinct subsets, the probability of forming a bad triple is $\le \frac{3}{L}$.
If none of $I_1, I_2, I_3$ contains the element $k$, then $J_1 = I_1 \cup \{k\}$, $J_2 = I_2 \cup \{k\}$, $J_3 = I_3 \cup \{k\}$ satisfy that $\triangle P_{J_1}P_{J_2}P_{J_3}$ is congruent to $\triangle P_{I_1}P_{I_2}P_{I_3}$. Therefore, the cases of bad triples are equivalent. We say that $(I_1, I_2, I_3)$ and $(J_1, J_2, J_3)$ are equivalent position triples.
From this perspective, the number of mutually non-equivalent position triples does not exceed $7^{10}$. Considering that the first two elements can be swapped, there are at most $\frac{7^{10}}{2}$ such triples.
Therefore, the probability that among the $2^{10}$ points $\{P_I\}$ there exists a bad triple is
$$\le \frac{7^{10}}{2} \times \frac{3}{L} = 1.5 \times \frac{7^{10}}{10^{10}} < 1.$$
Thus, there exists some configuration of the $2^{10}$ points $\{P_I\}$ containing no bad triples, which satisfies the requirement. $\square$