Maths Olympiad Prep

Library / /1 of 14

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it IMO

Prove that in any set of 20002000 distinct real numbers there exist two pairs a>ba > b and c>dc > d with aca \neq c or bdb \neq d, such that
abcd1<1100000 \left|\frac{a-b}{c-d}-1\right|<\frac{1}{100000}

Solution

For any set SS of n=2000n=2000 distinct real numbers, let D1D2DmD_{1} \leqslant D_{2} \leqslant \cdots \leqslant D_{m} be the distances between them, displayed with their multiplicities. Here m=n(n1)/2m = n(n-1)/2. By rescaling the numbers, we may assume that the smallest distance D1D_{1} between two elements of SS is D1=1D_{1} = 1. Let D1=1=yxD_{1} = 1 = y - x for x,ySx, y \in S. Evidently Dm=vuD_{m} = v - u is the difference between the largest element vv and the smallest element uu of SS.

If Di+1/Di<1+105D_{i+1}/D_{i} < 1 + 10^{-5} for some i=1,2,,m1i = 1, 2, \ldots, m-1 then the required inequality holds, because 0Di+1/Di1<1050 \leqslant D_{i+1}/D_{i} - 1 < 10^{-5}. Otherwise, the reverse inequality
Di+1Di1+1105 \frac{D_{i+1}}{D_{i}} \geqslant 1 + \frac{1}{10^{5}}
holds for each i=1,2,,m1i = 1, 2, \ldots, m-1, and therefore
vu=Dm=DmD1=DmDm1D3D2D2D1(1+1105)m1 v-u = D_{m} = \frac{D_{m}}{D_{1}} = \frac{D_{m}}{D_{m-1}} \cdots \frac{D_{3}}{D_{2}} \cdot \frac{D_{2}}{D_{1}} \geqslant \left(1 + \frac{1}{10^{5}}\right)^{m-1}
From m1=n(n1)/21=100019991>19105m-1 = n(n-1)/2 - 1 = 1000 \cdot 1999 - 1 > 19 \cdot 10^{5}, together with the fact that for all n1n \geqslant 1, (1+1n)n1+(n1)1n=2\left(1 + \frac{1}{n}\right)^{n} \geqslant 1 + \binom{n}{1} \cdot \frac{1}{n} = 2, we get
(1+1105)19105=((1+1105)105)19219=29210>5001000>2105 \left(1 + \frac{1}{10^{5}}\right)^{19 \cdot 10^{5}} = \left(\left(1 + \frac{1}{10^{5}}\right)^{10^{5}}\right)^{19} \geqslant 2^{19} = 2^{9} \cdot 2^{10} > 500 \cdot 1000 > 2 \cdot 10^{5}
and so vu=Dm>2105v-u = D_{m} > 2 \cdot 10^{5}.

Since the distance of xx to at least one of the numbers u,vu, v is at least (uv)/2>105(u-v)/2 > 10^{5}, we have
xz>105 |x-z| > 10^{5}
for some z{u,v}z \in \{u, v\}. Since yx=1y-x = 1, we have either z>y>xz > y > x (if z=vz = v) or y>x>zy > x > z (if z=uz = u). If z>y>xz > y > x, selecting a=za = z, b=yb = y, c=zc = z and d=xd = x (so that bdb \neq d), we obtain
abcd1=zyzx1=xyzx=1zx<105. \left|\frac{a-b}{c-d} - 1\right| = \left|\frac{z-y}{z-x} - 1\right| = \left|\frac{x-y}{z-x}\right| = \frac{1}{z-x} < 10^{-5}.
Otherwise, if y>x>zy > x > z, we may choose a=ya = y, b=zb = z, c=xc = x and d=zd = z (so that aca \neq c), and obtain
abcd1=yzxz1=yxxz=1xz<105. \left|\frac{a-b}{c-d} - 1\right| = \left|\frac{y-z}{x-z} - 1\right| = \left|\frac{y-x}{x-z}\right| = \frac{1}{x-z} < 10^{-5}.
The desired result follows.

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 and solution reproduced as published; topic and difficulty added by this site.