22nd Chinese Girls' Mathematical Olympiad

Proof Method 1: (1) For $k=1,2,\dots ,2023$, let the coordinates of $P_k$ be $(x_k,y_k)$, and denote $u_k=x_k+y_k$, $v_k=x_k-y_k$. Let $D={\max }_{1\le i<j\le 2023}d(P_i,P_j)$. Then, for any $1\le i,j\le 2023$, $$|u_i-u_j|=|(x_i-x_j)+(y_i-y_j)|\le |x_i-x_j|+|y_i-y_j|=d(P_i,P_j)\le D.$$ Thus, the $u_1,u_2,\dots ,u_{2023}$ fall within some interval $[a,a+D]$. Similarly for $v_1,v_2,\dots ,v_n$. For $k,l=1,2,\dots ,44$, consider the region $$H_{k,l}=\left\{\left(\frac{u+v}{2},\frac{u-v}{2}\right)\mid a+\frac{k-1}{44}D\le u\le a+\frac{k}{44}D,b+\frac{l-1}{44}D\le v\le b+\frac{l}{44}D\right\}.$$ If $P_i,P_j\in H_{k,l}$, let $U=u_i-u_j,V=v_i-v_j$, then $-\frac{D}{44}\le U,V\le \frac{D}{44}$, we have $$\begin{array}{rl}d(P_i,P_j)& =|x_i-x_j|+|y_i-y_j|=\left|\frac{u_i+v_i}{2}-\frac{u_j+v_j}{2}\right|+\left|\frac{u_i-v_i}{2}-\frac{u_j-v_j}{2}\right|\\ & =\left|\frac{U+V}{2}\right|+\left|\frac{U-V}{2}\right|\in \left\{\pm \frac{U+V}{2}\pm \frac{U-V}{2}\right\}=\{U,-U,V,-V\}.\end{array}$$ Hence, ${\min }_{1\le i<j\le 2023}d(P_i,P_j)\le d(P_i,P_j)\le \frac{D}{44}$, thus $\lambda \ge 44$.

(2) Construction Consider the point set $$M=\{(x,y)\in {\mathbb{Z}}^2\mid x,y\text{ have the same parity, }|x+y|\le 44,|x-y|\le 44\}.$$ This set contains $45^2=2025$ points. Selecting any 2023 points, the distance $d(P_i,P_j)=|x_i-x_j|+|y_i-y_j|$ is even and greater than 0, i.e., $d(P_i,P_j)\ge 2$. On the other hand, $$d(P_i,P_j)=|x_i-x_j|+|y_i-y_j|\le 88.$$ Thus, $$\lambda =\frac{{\max }_{1\le i<j\le 2023}d(P_i,P_j)}{{\min }_{1\le i<j\le 2023}d(P_i,P_j)}\le 44,$$ and by (1) $\lambda =44$.

Proof Method Two: Here is another proof that $\lambda \ge 44$. Assume the coordinates of the 2023 points are $P_k(x_k,y_k)$, $k=1,2,\dots ,2023$, and without loss of generality, assume $x_1\le x_2\le \cdots \le x_{2023}$. By the Erdős-Szekeres theorem, among $y_1,y_2,\dots ,y_{2023}$, there exists either an increasing or decreasing subsequence of length $\lceil \sqrt{2023}\rceil =45$. Assume we have $y_{i_1}\le y_{i_2}\le \cdots \le y_{i_{45}}$, with indices $i_1<i_2<\cdots <i_{45}$. Then, $$d(P_{i_{45}},P_{i_1})=(x_{i_{45}}-x_{i_1})+(y_{i_{45}}-y_{i_1})=\sum _{k=1}^{44}(x_{i_{k+1}}-x_{i_k})+(y_{i_{k+1}}-y_{i_k})=\sum _{k=1}^{44}d(P_{i_{k+1}},P_{i_k}).$$ If we have a decreasing subsequence $y_{i_1}\ge y_{i_2}\ge \cdots \ge y_{i_{45}}$, then $$d(P_{i_{45}},P_{i_1})=(x_{i_{45}}-x_{i_1})-(y_{i_{45}}-y_{i_1})=\sum _{k=1}^{44}(x_{i_{k+1}}-x_{i_k})-(y_{i_{k+1}}-y_{i_k})=\sum _{k=1}^{44}d(P_{i_{k+1}},P_{i_k}).$$ In both cases, we have $d(P_{i_{45}},P_{i_1})={\sum }_{k=1}^{44}d(P_{i_{k+1}},P_{i_k})$. Therefore, $$\lambda =\frac{{\max }_{1\le i<j\le 2023}d(P_i,P_j)}{{\min }_{1\le i<j\le 2023}d(P_i,P_j)}\ge \frac{d(P_{i_{45}},P_{i_1})}{{\min }_{k=1,2,...,44}d(P_{i_{k+1}},P_{i_k})}\ge 44.$$