China-TST-2025A

(1) Let the coordinates of $Q_i$ be $(x_i,y_i)$. Without loss of generality, assume $x_1<x_2<x_3$. Since both the conditions and conclusion are symmetric under reflection about the $x$-axis and $y$-axis, we can further assume $y_1<y_3<y_2$. After appropriate translation, we may set $x_1=y_1=0$, so $0<x_2<x_3$ and $0<y_3<y_2$. Since $\{Q_1,Q_2,Q_3\}$ is sparse, $$A=(x_3-x_2)(y_2-y_3)\ge 1,B=x_2{y}_2\ge 1,C=x_3{y}_3\ge 1.$$ The area of triangle $Q_1{Q}_2{Q}_3$ is $S=\frac{1}{2}(x_3{y}_2-x_2{y}_3)$, and we have $$\begin{array}{rl}(2S{)}^2& =(x_3{y}_2-x_2{y}_3{)}^2=(x_3{y}_2+x_2{y}_3{)}^2-4x_3{y}_2{x}_2{y}_3\\ & =(A+B+C{)}^2-4BC=A^2+2A(B+C)+(B-C{)}^2\\ & \ge 5,\end{array}$$ which proves $S\ge \frac{\sqrt{5}}{2}$.

(2) Define the $L^1$ distance between two points $A(a_1,a_2),B(b_1,b_2)$ as $d_1(A,B)=|a_1-b_1|+|a_2-b_2|$. It's easy to verify that the $L^1$ distance satisfies the triangle inequality $$d_1(A,B)+d_1(B,C)\ge d_1(A,C),$$ with equality when $A,B,C$ are colinear in order. It's known that if convex polygon $Q$ is contained in convex polygon $R$, then the perimeter of $Q$ doesn't exceed that of $R$. Using similar proof methods and the triangle inequality for $L^1$ distance, we can show that under these conditions, the $L^1$ perimeter of $Q$ (sum of $L^1$ lengths of its sides) doesn't exceed that of $R$. Let $R$ be the given square with side length $a$, and $P=\{P_1,\dots ,P_n\}$ be a sparse subset of $R$. By the definition of sparse sets, for any $i\ne j$, $$|x_i-x_j|+|y_i-y_j|\ge 2\sqrt{|x_i-x_j|\cdot |y_i-y_j|}\ge 2,$$ i.e., $d_1(P_i,P_j)\ge 2$. For a triangle $△P_i{P}_j{P}_k$ with vertices in $P$, if $P_i$ lies inside the rectangle with $P_j{P}_k$ as diagonal and sides parallel to the coordinate axes, we call $△P_i{P}_j{P}_k$ a bad triangle, $\angle P_j{P}_i{P}_k$ its bad angle, and $P_j{P}_k$ its bad edge. Each bad triangle has exactly one bad angle and one bad edge. Let $\ell (△P_i{P}_j{P}_k)=d_1(P_j,P_k)$ be the length of the bad edge, which equals $d_1(P_j,P_i)+d_1(P_i,P_k)$. If no angle of $△P_i{P}_j{P}_k$ is bad, we call it a good triangle. Part (1) shows that good triangles have area at least $\frac{\sqrt{5}}{2}$.

Let the convex hull of $P$ be an $m$-gon $Q=Q_1{Q}_2\cdots Q_m$. We first state a lemma: Lemma: There exists a triangulation $\mathcal{T}$ of $Q$ consisting of $2n-m-2$ triangles with vertices in $P$, such that the number of bad triangles in $\mathcal{T}$ doesn't exceed $2a$. We'll use this lemma to prove the main result. Take a triangulation $\mathcal{T}$ satisfying the lemma. Since the $L^1$ perimeter of $Q$ doesn't exceed that of $R$, $$4a\ge \sum _{i=1}^m{d}_1(Q_i,Q_{i+1})\ge 2m,$$ so $m\le 2a$. As $\mathcal{T}$ has at most $2a$ bad triangles, the number $N$ of good triangles satisfies $$N\ge (2n-m-2)-2a\ge 2n-4a-2.$$ Since the total area of good triangles doesn't exceed the area of $R$ and each good triangle has area at least $\frac{\sqrt{5}}{2}$, $$a^2\ge \frac{\sqrt{5}}{2}N\ge \frac{\sqrt{5}}{2}(2n-4a-2),$$ which implies $n\le \frac{a^2}{\sqrt{5}}+2a+1$.

Next, we prove the lemma. Consider a triangulation $\mathcal{T}$ of $Q$ that minimizes both the number of bad triangles and, subject to that condition, minimizes the sum of all bad angles.

For any internal bad triangle $ABC$ in $\mathcal{T}$ with bad edge $BC$, there exists another triangle $BCD$ sharing the edge $BC$. Let ${\mathcal{T}}^{\prime }$ be the triangulation obtained by replacing triangles $△ABC$ and $△BCD$ with $△ABD$ and $△ACD$. As shown in the figure, point $D$ may lie in regions $Y_1$ through $Y_5$. For each possible position of $D$, we can carefully analyze how the number of bad triangles and the sum of bad angles change when transforming $\mathcal{T}$ to ${\mathcal{T}}^{\prime }$, as described in the following table:

Region containing D	Change in number of bad triangles and sum of bad angles
$Y_1$	Two bad become two good
$Y_2$	One good and one bad become two good
$Y_3$	Two bad remain two bad, but sum of bad angles strictly decreases
$Y_4$	One good and one bad remain, but sum of bad angles strictly decreases

By the minimality of $\mathcal{T}$, we conclude that $D\in Y_5$. In this case, $△BCD$ is also a bad triangle. If $D$ is in the bottom-left $Y_5$ region of the figure, then $CD$ is the bad edge of $△BCD$, giving $\ell (△BCD)=d_1(D,B)+d_1(B,C)\ge \ell (△ABC)+2$. If $D$ is in the top-right $Y_5$ region, then $BD$ is the bad edge of $△BCD$, giving $\ell (△BCD)=d_1(B,C)+d_1(C,D)\ge \ell (△ABC)+2$. In summary, for any internal bad triangle ${\Delta }_0$, the triangle ${\Delta }_1$ on the other side of its bad edge is also bad, with $\ell ({\Delta }_1)>\ell ({\Delta }_0)$. If ${\Delta }_1$ is also internal, then the triangle ${\Delta }_2$ on the other side of its bad edge is bad, and so on, forming a unique chain of bad triangles: $${\Delta }_0⇝{\Delta }_1⇝\cdots ⇝{\Delta }_k,$$ ending with a boundary bad triangle ${\Delta }_k$. Denote this chain by $C({\Delta }_0)$. For a boundary bad triangle ${\Delta }_0$, $C({\Delta }_0)$ contains only ${\Delta }_0$ itself.