Prove that in any set of 2000 distinct real numbers there exist two pairs a>b and c>d with a=c or b=d, such that c−da−b−1<1000001
Solution
For any set S of n=2000 distinct real numbers, let D1⩽D2⩽⋯⩽Dm be the distances between them, displayed with their multiplicities. Here m=n(n−1)/2. By rescaling the numbers, we may assume that the smallest distance D1 between two elements of S is D1=1. Let D1=1=y−x for x,y∈S. Evidently Dm=v−u is the difference between the largest element v and the smallest element u of S.
If Di+1/Di<1+10−5 for some i=1,2,…,m−1 then the required inequality holds, because 0⩽Di+1/Di−1<10−5. Otherwise, the reverse inequality DiDi+1⩾1+1051 holds for each i=1,2,…,m−1, and therefore v−u=Dm=D1Dm=Dm−1Dm⋯D2D3⋅D1D2⩾(1+1051)m−1 From m−1=n(n−1)/2−1=1000⋅1999−1>19⋅105, together with the fact that for all n⩾1, (1+n1)n⩾1+(1n)⋅n1=2, we get (1+1051)19⋅105=((1+1051)105)19⩾219=29⋅210>500⋅1000>2⋅105 and so v−u=Dm>2⋅105.
Since the distance of x to at least one of the numbers u,v is at least (u−v)/2>105, we have ∣x−z∣>105 for some z∈{u,v}. Since y−x=1, we have either z>y>x (if z=v) or y>x>z (if z=u). If z>y>x, selecting a=z, b=y, c=z and d=x (so that b=d), we obtain c−da−b−1=z−xz−y−1=z−xx−y=z−x1<10−5. Otherwise, if y>x>z, we may choose a=y, b=z, c=x and d=z (so that a=c), and obtain c−da−b−1=x−zy−z−1=x−zy−x=x−z1<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.