Let $P_i(x_i,y_i)\ (i=1,2,\cdots,2023)$ be $2023$ distinct points on a plane equipped with rectangular coordinate system. For $i\neq j$, define $d(P_i,P_j) = |x_i - x_j| + |y_i - y_j|$. Define $$\lambda = \frac{\max_{i\neq j}d(P_i,P_j)}{\min_{i\neq j}d(P_i,P_j)}$$. Prove that $\lambda \geq 44$ and provide an example in which the equality holds.
Problem
Source: Chinese Girls Mathematical Olympiad 2023
Tags: combinatorics, geometry, combinatorical geometry
cadaeibf
13.08.2023 14:25
Assume wlog the smallest distance is $1$. It is easy to achieve the bound by putting $45^2=2025\geq 2023$ points in a $45\times 45$ diamond (i.e. a square with sides at $45$ degrees with respect to the coordinate axes). In this configuration, the biggest distance is exactly $44$, so the value can be achieved. Now to prove it is optimal, consider the smallest diamond enclosing the points (which can be on its boundary), and say it has diameter $L$. Since it's the smallest possible diamond, there must be at least two points on opposite sides of the squares, which therefore have distance $L$. We now wish to prove that if $L<44$ (i.e. the maximal distance between two points is $L<44$), then we couldn't fit all the points in the diamond. Indeed, partition the diamond into $44\times 44$ equal diamonds, each of diameter $L/44<1$. By pigeonhole principle, since $2023>44^2$, there exist two points inside (or on the boundary of) the same diamond. But this is a contradiction, since the two points must be distant at least $1$ but the diamond they're inside has diameter less than $1$. Therefore, the minimum ratio is indeed $44$, and this prove in general that with $N$ points the minimal ratio is $\left\lceil \sqrt N\right\rceil -1$
KurokoShirai
13.08.2023 17:22
Seems that to prove the minimality one can use the famous theorem that the product of the lengths of LIS and LDS of some finite real sequence is no less than the length of the sequence itself. Here LIS refers to the longest increasing subsequence, and LDS refers the longest decreasing subsequence.
Banglarmanush
29.08.2023 15:23
x1,..,x2023 can have any value. Pj(xj,yj) is for Pj. d(Pi,Pj) is always positive and the value of d(Pi,Pj) can be (+ve)+(+ve),(0)+(+ve) and (0)+(0)[all possibilites]. d(Pi,Pj) can have any value. So we lambda has a possibility of >=44.
Banglarmanush
31.08.2023 15:15
For the example, D(Pi,Pj)=22+22 for the max For the min,let it be 1 So, The equality holds,44/1
gghx
01.09.2023 03:20
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem#:~:text=In%20mathematics%2C%20the%20Erd%C5%91s%E2%80%93Szekeres,decreasing%20subsequence%20of%20length%20s.
hellnish
09.11.2023 16:01
Erdos-szekeres theorem？
Itoz
09.11.2023 16:30
This problem is too easy for a final question with Erdos-Szekeres theorem.
WLOG, let $x_1\leq x_2 \leq \cdots \leq x_{2023}$.
By Erdos-Szekeres, the sequence $y_1, \cdots , y_{2023}$ contains an subsequence of $\lfloor \sqrt{2023-1} \rfloor = 44$ terms at least , which is monotonic increasing or monotonic decreasing.
WLOG, let $y_1\leq y_2 \leq \cdots \leq y_{45}$ or $y_1\geq y_2 \geq \cdots \geq y_{45}$.
Then $\max_{i\neq j}d(P_i,P_j)\geq d(P_1,P_{45})=\sum_{i=1}^{44}d(P_i,P_{i+1})\geq 44\min_{i\neq j}d(P_i,P_j)$, hence proved.
Let $A(-22,0),B(22,0),C(0,22),D(0,-22)$, then consider the square $ABCD$.
Now we put $2023$ points on the lattice point of this square (contains the edges).
Easily we can know that in this case, $\lambda = 44$.