2025 International Mathematical Olympiad China National Team Selection Test

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),B=\left(\sum v_i{3}^i,\sum v_i{9}^i\right),C=\left(\sum w_i{3}^i,\sum w_i{9}^i\right).$$ Then $|\sum (u_i-v_i)(9^i-k{3}^i)|\le \sqrt{k^2+1}$ etc. If $k\le 7$, assume $u_1=v_1$. Since $9^{i+1}-k{3}^{i+1}>2(9^i-k{3}^i)$ for $i\ge 2$ and $9^2-k{3}^2>\sqrt{k^2+1}$, contradiction! If $k>7\cdot 3^8$, assume $u_{10}=v_{10}$. Since $k{3}^{i+1}-9^{i+1}>2(k{3}^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{array}{rl}{9}^{i+1}-k{3}^{i+1}& >2(9^i-k{3}^i)(i\ge d+3);\\ 9^{d+3}-k{3}^{d+3}& >2(k{3}^{d+1}-9^{d+1});\\ k{3}^{i+1}-9^{i+1}& >2(k{3}^i-9^i)(i\le d);\\ 3k-9& >\sqrt{k^2+1},\end{array}$$ 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),(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,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),(L_x-x_2,L_y-y_2),(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^{\prime }=(x_j^{\prime },y_j^{\prime })$ 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^{\prime }|\le 1$ and $|y_j-y_j^{\prime }|\le 1$. Therefore: $$\frac{y_1^{\prime }-y_2^{\prime }}{x_1^{\prime }-x_2^{\prime }}=\frac{y_2^{\prime }-y_3^{\prime }}{x_2^{\prime }-x_3^{\prime }}.$$ Lemma 1: $\frac{y_1^{\prime }-y_2^{\prime }}{x_1^{\prime }-x_2^{\prime }}\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^{\prime }-x_2^{\prime }}\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}}>\cdots >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^{\prime }-y_2^{\prime }}{x_1^{\prime }-x_2^{\prime }}\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^{\prime }-y_3^{\prime }}{x_2^{\prime }-x_3^{\prime }}\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^{\prime }-y_3^{\prime }}{x_2^{\prime }-x_3^{\prime }}\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)}\ne 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^{\prime }-y_3^{\prime }}{x_2^{\prime }-x_3^{\prime }}\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 $△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}\ne 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 $△P_{I_1}{P}_{I_2}{P}_{I_3}$ and $△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 $△P_{J_1}{P}_{J_2}{P}_{J_3}$ is congruent to $△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$