Maths Olympiad Prep

Library / /8 of 13

Combinatorics Difficulty 6.6 National olympiad Find the answer

Do there exist two bounded sequences a1,a2,a_{1}, a_{2}, \ldots and b1,b2,b_{1}, b_{2}, \ldots such that for each positive integers nn and m>nm > n at least one of the two inequalities aman>1n,bmbn>1n|a_{m} - a_{n}| > \frac{1}{\sqrt{n}}, |b_{m} - b_{n}| > \frac{1}{\sqrt{n}} holds?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Suppose such sequences (an)(a_{n}) and (bn)(b_{n}) exist. For each pair (x,y)(x, y) of real numbers we consider the corresponding point (x,y)(x, y) in the coordinate plane. Let PnP_{n} for each nn denote the point (an,bn)(a_{n}, b_{n}). The condition in the problem requires that the square {(x,y):xan1n,ybn1n}\{(x, y): |x - a_{n}| \leq \frac{1}{\sqrt{n}}, |y - b_{n}| \leq \frac{1}{\sqrt{n}}\} does not contain PmP_{m} for mnm \neq n. For each point AnA_{n} we construct its private square {(x,y):xan12n,ybn12n}\{(x, y): |x - a_{n}| \leq \frac{1}{2\sqrt{n}}, |y - b_{n}| \leq \frac{1}{2\sqrt{n}}\}. The condition implies that private squares of points AnA_{n} and AmA_{m} are disjoint when mnm \neq n. Let an<C,bn<C|a_{n}| < C, |b_{n}| < C for all nn. Then all private squares of points AnA_{n} lie in the square {(x,y):xC+12,yC+12}\{(x, y): |x| \leq C + \frac{1}{2}, |y| \leq C + \frac{1}{2}\} with area (2C+1)2(2C + 1)^{2}. However private squares do not intersect, and the private square of PnP_{n} has area 1n\frac{1}{n}. The series 1+12+13+1 + \frac{1}{2} + \frac{1}{3} + \cdots diverges; in particular, it contains some finite number of terms with sum greater than (2C+1)2(2C + 1)^{2}, which is impossible if the respective private square lie inside a square with area (2C+1)2(2C + 1)^{2} and do not intersect. This contradiction shows that the desired sequences (an)(a_{n}) and (bn)(b_{n}) do not exist.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.