2023 Chinese IMO National Team Selection Test

Proof. For the edge $BC$, a partial order ${\prec }_A$ can be defined on the set $P=P_1,\cdots ,P_n$ as follows: $$P_i{\prec }_A{P}_j⟺\begin{array}{rl}[t]& P_i\text{ is an interior point of the }△P_{j}BC\\ & \text{the ray }{P}_j{P}_i\text{ intersects with the segment }BC.\end{array}$$ Similarly, a partial order ${\prec }_B$ can be defined on $P$ using the edge $CA$. If two distinct points $P_i,P_j$ are incomparable under ${\prec }_A$, then the line $P_i{P}_j$ does not intersect with the segment $BC$. Since the line $P_i{P}_j$ intersects with the boundary of $△ABC$ at two points, it follows that $P_i,P_j$ are comparable under ${\prec }_B$. Thus, the anti-chains in the order ${\prec }_A$ are chains in the order ${\prec }_B$. By using the Dilworth theorem, under the partial order ${\prec }_A$, there either exists a chain of length at least $\sqrt{n}$, or there exists an anti-chain of length at least $\sqrt{n}$. Combining with the above-mentioned property that an anti-chain in the order ${\prec }_A$ is a chain in the order ${\prec }_B$, we know that there either exists a chain of length at least $\sqrt{n}$ under the partial order ${\prec }_A$, or there exists a chain of length at least $\sqrt{n}$ under the partial order ${\prec }_B$. Without loss of generality, suppose there exists a chain of length at least $\sqrt{n}$ under the partial order ${\prec }_A$, denoted as $P_1{\prec }_A\cdots {\prec }_A{P}_t$, where $t\ge \sqrt{n}$. Connect the segments $$B{P}_i,C{P}_i(1\le i\le t),P_1{P}_2,\cdots ,P_{t-1}{P}_t,P_{t}A,$$ which partition $△ABC$ into $2t+1$ triangles $$(\ast )△BC{P}_1,△B{P}_i{P}_{i+1},△C{P}_i{P}_{i+1}(1\le i\le t-1),△B{P}_{t}A,△C{P}_{t}A.$$ Let the number of points from set $P$ in the interiors of $△BC{P}_1,△B{P}_1{P}_2,\cdots ,△B{P}_{t}A$ be $k_0,k_1,\cdots ,k_t$, respectively. For each such triangle $△$, denoted as $△BQR$, suppose the interior points from set $P$ in $△$ are $U_j(1\le j\le k)$, where $\angle QB{U}_j(1\le j\le k)$ are arranged in increasing order. Connect the segments $B{U}_j(1\le j\le k)$ and $Q{U}_1,U_1{U}_2,\cdots ,U_{k}R$, yielding $k+1$ small triangles that all include $B$, and divide the polygon $Q{U}_1\cdots U_{k}R$ into a union of $k$ small triangles arbitrarily (as it is well-known that any polygon can be triangulated). This way, $△$ is partitioned into the union of $2k+1$ small triangles, $k+1$ of which include $B$ as a vertex. Similarly, suppose the number of points from set $P$ in the interiors of $△C{P}_1{P}_2,\cdots ,△C{P}_{t}A$ are ${\ell }_1,\cdots ,{\ell }_t$, respectively. For each such triangle ${△}^{\prime }$, with $\ell$ points from set $P$ in its interior, ${△}^{\prime }$ can be partitioned into a union of $2\ell +1$ small triangles, $\ell +1$ of which include $C$ as a vertex. This way, we have constructed a triangulation of $△ABC$, where at least $$T=\sum _{i=0}^t(k_i+1)+\sum _{i=1}^t({\ell }_i+1)$$ of the small triangles include a point from $\{B,C\}$ as a vertex. Noting that $k_0+k_1+\cdots +k_t+{\ell }_1+\cdots +{\ell }_t=n-t$, we get $T=(n-t)+(2t+1)=n+t+1\ge \sqrt{n}+1$, which proves the conclusion of the theorem. $\square$