Maths Olympiad Prep

Library / /240 of 462

Combinatorics Difficulty 5.8 AIME, harder Prove it Ireland

Let P1,P2,,P2021P_1, P_2, \dots, P_{2021} be 20212021 points in the quarter plane {(x,y)x0,y0}\{(x, y) \mid x \ge 0, y \ge 0\}.
The centroid of these 20212021 points lies at the point (1,1)(1, 1).
Show that there are two distinct points Pi,PjP_i, P_j such that the distance from PiP_i to PjP_j is no more than 2/20\sqrt{2}/20.

Solution

The appearance of 2\sqrt{2} is a clue that this question will end up with a pigeon-hole principle on squares of a grid with spacing 1/201/20.
We prove a more general result:

Theorem: Let kk be a positive integer, let nk(k+1)/2n \ge k(k+1)/2 and let h>0h > 0. Suppose that a set of points (xj,yj)(x_j, y_j) for j=1,2,3,,nj = 1, 2, 3, \dots, n in the quarter plane is such that any two points are at a distance exceeding h2h\sqrt{2}. Then the centroid (xˉ,yˉ)(\bar{x}, \bar{y}) satisfies:
xˉ+yˉ23(k1)h. \bar{x} + \bar{y} \ge \frac{2}{3}(k-1)h.
The answer to the original question follows by contradiction on setting k=62k = 62 (or k=63k = 63), n=2021n = 2021 and h=1/20h = 1/20.

Proof of Theorem: For each point (xj,yj)(x_j, y_j) write:
mj=xjh+yjh. m_j = \lfloor \frac{x_j}{h} \rfloor + \lfloor \frac{y_j}{h} \rfloor.
It follows then that:
xj+yjhmj. x_j + y_j \ge h m_j.
By hypothesis, no two points have a distance less than or equal to h2h\sqrt{2}. Then there can be no more than one point in any h×hh \times h square. There can be at most one jj with mj=0m_j = 0, at most two with mj=1m_j = 1, at most three with mj=2m_j = 2 and so on, up to at most kk with mj=k1m_j = k-1. The remaining points (at least nk(k+1)/2n - k(k+1)/2 of them) have mjkm_j \ge k.
We can deduce that the sums of the xx's and yy's is governed by the lower bound:
j=1n(xj+yj)j=1nhmjhi=1ki(i1)+(nk(k+1)2)kh. \sum_{j=1}^{n} (x_j + y_j) \ge \sum_{j=1}^{n} h m_j \ge h \sum_{i=1}^{k} i(i-1) + \left(n - \frac{k(k+1)}{2}\right) k h.
Recalling that:
i=2ki(i1)=2i=2k(i2)=2i=2k{(i+13)(i3)}=2(k+13) \sum_{i=2}^{k} i(i-1) = 2 \sum_{i=2}^{k} \binom{i}{2} = 2 \sum_{i=2}^{k} \left\{ \binom{i+1}{3} - \binom{i}{3} \right\} = 2 \binom{k+1}{3}
we obtain:
1hj=1n(xj+yj)(k+1)k(k1)3+(nk(k+1)2)k=(k2(k1)3)(nk(k+1)2)+2(k1)3n2(k1)3n. \begin{align*} \frac{1}{h} \sum_{j=1}^{n} (x_j + y_j) &\ge \frac{(k+1)k(k-1)}{3} + \left(n - \frac{k(k+1)}{2}\right) k \\ &= \left(k - \frac{2(k-1)}{3}\right) \left(n - \frac{k(k+1)}{2}\right) + \frac{2(k-1)}{3} n \\ &\ge \frac{2(k-1)}{3} n. \end{align*}
Multiplying by hh and dividing by nn 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.