Maths Olympiad Prep

Library / Chinese Girls' Mathematical Olympiad /7 of 7

Chinese Girls' Mathematical Olympiad

Geometry Difficulty 8.0 Shortlist Prove it China

For any two points A(x1,y1)A(x_1, y_1) and B(x2,y2)B(x_2, y_2) in the coordinate plane, define
d(A,B)=∣x1−x2∣+∣y1−y2∣. d(A, B) = |x_1 - x_2| + |y_1 - y_2|.
Let P1,P2,…,P2023P_1, P_2, \dots, P_{2023} be 2023 pairwise different points in the coordinate plane. Denote
λ=max⁡1≤i<j≤2023d(Pi,Pj)min⁡1≤i<j≤2023d(Pi,Pj). \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)}.
(1) Prove that λ≥44\lambda \ge 44.
(2) Give an example of P1,P2,…,P2023P_1, P_2, \dots, P_{2023} such that λ=44\lambda = 44.

Solution

Proof Method 1:
(1) For k=1,2,…,2023k = 1, 2, \dots, 2023, let the coordinates of PkP_k be (xk,yk)(x_k, y_k), and denote uk=xk+yku_k = x_k + y_k, vk=xk−ykv_k = x_k - y_k. Let D=max⁡1≤i<j≤2023d(Pi,Pj)D = \max_{1 \le i < j \le 2023} d(P_i, P_j). Then, for any 1≤i,j≤20231 \le i, j \le 2023,
∣ui−uj∣=∣(xi−xj)+(yi−yj)∣≤∣xi−xj∣+∣yi−yj∣=d(Pi,Pj)≤D. |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 u1,u2,…,u2023u_1, u_2, \dots, u_{2023} fall within some interval [a,a+D][a, a+D]. Similarly for v1,v2,…,vnv_1, v_2, \dots, v_n. For k,l=1,2,…,44k, l = 1, 2, \dots, 44, consider the region
Hk,l={(u+v2,u−v2)∣a+k−144D≤u≤a+k44D, b+l−144D≤v≤b+l44D}. 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 Pi,Pj∈Hk,lP_i, P_j \in H_{k,l}, let U=ui−uj,V=vi−vjU = u_i - u_j, V = v_i - v_j, then −D44≤U,V≤D44-\frac{D}{44} \le U, V \le \frac{D}{44}, we have
d(Pi,Pj)=∣xi−xj∣+∣yi−yj∣=∣ui+vi2−uj+vj2∣+∣ui−vi2−uj−vj2∣=∣U+V2∣+∣U−V2∣∈{±U+V2±U−V2}={U,−U,V,−V}. \begin{aligned} 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{aligned}
Hence, min⁡1≤i<j≤2023d(Pi,Pj)≤d(Pi,Pj)≤D44\min_{1 \le i < j \le 2023} d(P_i, P_j) \le d(P_i, P_j) \le \frac{D}{44}, thus λ≥44\lambda \ge 44.

(2) Construction
Consider the point set
M={(x,y)∈Z2∣x,y have the same parity, ∣x+y∣≤44,∣x−y∣≤44}. 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 452=202545^2 = 2025 points. Selecting any 2023 points, the distance d(Pi,Pj)=∣xi−xj∣+∣yi−yj∣d(P_i, P_j) = |x_i - x_j| + |y_i - y_j| is even and greater than 0, i.e., d(Pi,Pj)≥2d(P_i, P_j) \ge 2. On the other hand,
d(Pi,Pj)=∣xi−xj∣+∣yi−yj∣≤88. d(P_i, P_j) = |x_i - x_j| + |y_i - y_j| \le 88.
Thus,
λ=max⁡1≤i<j≤2023d(Pi,Pj)min⁡1≤i<j≤2023d(Pi,Pj)≤44, \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) λ=44\lambda = 44.

Proof Method Two:
Here is another proof that λ≥44\lambda \ge 44. Assume the coordinates of the 2023 points are Pk(xk,yk)P_k(x_k, y_k), k=1,2,…,2023k = 1, 2, \dots, 2023, and without loss of generality, assume x1≤x2≤⋯≤x2023x_1 \le x_2 \le \dots \le x_{2023}. By the Erdős-Szekeres theorem, among y1,y2,…,y2023y_1, y_2, \dots, y_{2023}, there exists either an increasing or decreasing subsequence of length ⌈2023⌉=45\lceil\sqrt{2023}\rceil = 45. Assume we have yi1≤yi2≤⋯≤yi45y_{i_1} \le y_{i_2} \le \dots \le y_{i_{45}}, with indices i1<i2<⋯<i45i_1 < i_2 < \dots < i_{45}. Then,
d(Pi45,Pi1)=(xi45−xi1)+(yi45−yi1)=∑k=144(xik+1−xik)+(yik+1−yik)=∑k=144d(Pik+1,Pik). 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 yi1≥yi2≥⋯≥yi45y_{i_1} \ge y_{i_2} \ge \dots \ge y_{i_{45}}, then
d(Pi45,Pi1)=(xi45−xi1)−(yi45−yi1)=∑k=144(xik+1−xik)−(yik+1−yik)=∑k=144d(Pik+1,Pik). 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(Pi45,Pi1)=∑k=144d(Pik+1,Pik)d(P_{i_{45}}, P_{i_1}) = \sum_{k=1}^{44} d(P_{i_{k+1}}, P_{i_k}). Therefore,
λ=max⁡1≤i<j≤2023d(Pi,Pj)min⁡1≤i<j≤2023d(Pi,Pj)≥d(Pi45,Pi1)min⁡k=1,2,...,44d(Pik+1,Pik)≥44. \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.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.