Olympiad Maths Prep

Library / /7 of 7

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)=x1x2+y1y2. 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
λ=max1i<j2023d(Pi,Pj)min1i<j2023d(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=xkykv_k = x_k - y_k. Let D=max1i<j2023d(Pi,Pj)D = \max_{1 \le i < j \le 2023} d(P_i, P_j). Then, for any 1i,j20231 \le i, j \le 2023,
uiuj=(xixj)+(yiyj)xixj+yiyj=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,uv2)a+k144Dua+k44D, b+l144Dvb+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,PjHk,lP_i, P_j \in H_{k,l}, let U=uiuj,V=vivjU = u_i - u_j, V = v_i - v_j, then D44U,VD44-\frac{D}{44} \le U, V \le \frac{D}{44}, we have
d(Pi,Pj)=xixj+yiyj=ui+vi2uj+vj2+uivi2ujvj2=U+V2+UV2{±U+V2±UV2}={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, min1i<j2023d(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)Z2x,y have the same parity, x+y44,xy44}. 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)=xixj+yiyjd(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)=xixj+yiyj88. d(P_i, P_j) = |x_i - x_j| + |y_i - y_j| \le 88.
Thus,
λ=max1i<j2023d(Pi,Pj)min1i<j2023d(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 x1x2x2023x_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 yi1yi2yi45y_{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)=(xi45xi1)+(yi45yi1)=k=144(xik+1xik)+(yik+1yik)=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 yi1yi2yi45y_{i_1} \ge y_{i_2} \ge \dots \ge y_{i_{45}}, then
d(Pi45,Pi1)=(xi45xi1)(yi45yi1)=k=144(xik+1xik)(yik+1yik)=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,
λ=max1i<j2023d(Pi,Pj)min1i<j2023d(Pi,Pj)d(Pi45,Pi1)mink=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.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.