Let P1,P2,…,P2021 be 2021 points in the quarter plane {(x,y)∣x≥0,y≥0}. The centroid of these 2021 points lies at the point (1,1). Show that there are two distinct points Pi,Pj such that the distance from Pi to Pj is no more than 2/20.
Solution
The appearance of 2 is a clue that this question will end up with a pigeon-hole principle on squares of a grid with spacing 1/20. We prove a more general result:
Theorem: Let k be a positive integer, let n≥k(k+1)/2 and let h>0. Suppose that a set of points (xj,yj) for j=1,2,3,…,n in the quarter plane is such that any two points are at a distance exceeding h2. Then the centroid (xˉ,yˉ) satisfies: xˉ+yˉ≥32(k−1)h. The answer to the original question follows by contradiction on setting k=62 (or k=63), n=2021 and h=1/20.
Proof of Theorem: For each point (xj,yj) write: mj=⌊hxj⌋+⌊hyj⌋. It follows then that: xj+yj≥hmj. By hypothesis, no two points have a distance less than or equal to h2. Then there can be no more than one point in any h×h square. There can be at most one j with mj=0, at most two with mj=1, at most three with mj=2 and so on, up to at most k with mj=k−1. The remaining points (at least n−k(k+1)/2 of them) have mj≥k. We can deduce that the sums of the x's and y's is governed by the lower bound: j=1∑n(xj+yj)≥j=1∑nhmj≥hi=1∑ki(i−1)+(n−2k(k+1))kh. Recalling that: i=2∑ki(i−1)=2i=2∑k(2i)=2i=2∑k{(3i+1)−(3i)}=2(3k+1) we obtain: h1j=1∑n(xj+yj)≥3(k+1)k(k−1)+(n−2k(k+1))k=(k−32(k−1))(n−2k(k+1))+32(k−1)n≥32(k−1)n. Multiplying by h and dividing by n gives the theorem as claimed.
Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.