For any two points A(x1,y1) and B(x2,y2) in the coordinate plane, define d(A,B)=∣x1−x2∣+∣y1−y2∣. Let P1,P2,…,P2023 be 2023 pairwise different points in the coordinate plane. Denote λ=min1≤i<j≤2023d(Pi,Pj)max1≤i<j≤2023d(Pi,Pj). (1) Prove that λ≥44. (2) Give an example of P1,P2,…,P2023 such that λ=44.
Solution
Proof Method 1: (1) For k=1,2,…,2023, let the coordinates of Pk be (xk,yk), and denote uk=xk+yk, vk=xk−yk. Let D=max1≤i<j≤2023d(Pi,Pj). Then, for any 1≤i,j≤2023, ∣ui−uj∣=∣(xi−xj)+(yi−yj)∣≤∣xi−xj∣+∣yi−yj∣=d(Pi,Pj)≤D. Thus, the u1,u2,…,u2023 fall within some interval [a,a+D]. Similarly for v1,v2,…,vn. For k,l=1,2,…,44, consider the region Hk,l={(2u+v,2u−v)∣a+44k−1D≤u≤a+44kD,b+44l−1D≤v≤b+44lD}. If Pi,Pj∈Hk,l, let U=ui−uj,V=vi−vj, then −44D≤U,V≤44D, we have d(Pi,Pj)=∣xi−xj∣+∣yi−yj∣=2ui+vi−2uj+vj+2ui−vi−2uj−vj=2U+V+2U−V∈{±2U+V±2U−V}={U,−U,V,−V}. Hence, min1≤i<j≤2023d(Pi,Pj)≤d(Pi,Pj)≤44D, thus λ≥44.
(2) Construction Consider the point set M={(x,y)∈Z2∣x,y have the same parity, ∣x+y∣≤44,∣x−y∣≤44}. This set contains 452=2025 points. Selecting any 2023 points, the distance d(Pi,Pj)=∣xi−xj∣+∣yi−yj∣ is even and greater than 0, i.e., d(Pi,Pj)≥2. On the other hand, d(Pi,Pj)=∣xi−xj∣+∣yi−yj∣≤88. Thus, λ=min1≤i<j≤2023d(Pi,Pj)max1≤i<j≤2023d(Pi,Pj)≤44, and by (1) λ=44.
Proof Method Two: Here is another proof that λ≥44. Assume the coordinates of the 2023 points are Pk(xk,yk), k=1,2,…,2023, and without loss of generality, assume x1≤x2≤⋯≤x2023. By the Erdős-Szekeres theorem, among y1,y2,…,y2023, there exists either an increasing or decreasing subsequence of length ⌈2023⌉=45. Assume we have yi1≤yi2≤⋯≤yi45, with indices i1<i2<⋯<i45. Then, d(Pi45,Pi1)=(xi45−xi1)+(yi45−yi1)=k=1∑44(xik+1−xik)+(yik+1−yik)=k=1∑44d(Pik+1,Pik). If we have a decreasing subsequence yi1≥yi2≥⋯≥yi45, then d(Pi45,Pi1)=(xi45−xi1)−(yi45−yi1)=k=1∑44(xik+1−xik)−(yik+1−yik)=k=1∑44d(Pik+1,Pik). In both cases, we have d(Pi45,Pi1)=∑k=144d(Pik+1,Pik). Therefore, λ=min1≤i<j≤2023d(Pi,Pj)max1≤i<j≤2023d(Pi,Pj)≥mink=1,2,...,44d(Pik+1,Pik)d(Pi45,Pi1)≥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.