Maths Olympiad Prep

Library / /25 of 30

Combinatorics Difficulty 8.7 Shortlist Prove it Germany

Problem:

Determine the smallest real constant CC with the following property:
For any five positive real numbers a1,a2,a3,a4,a5a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, which need not necessarily be distinct, it is always possible to find pairwise distinct indices i,j,k,li, j, k, l such that
aiajakalC \left|\frac{a_{i}}{a_{j}}-\frac{a_{k}}{a_{l}}\right| \leq C
holds.

Solution

Solution:

The desired value is C=12C=\frac{1}{2}.

First we prove that C12C \leq \frac{1}{2} holds. To do this we assume without loss of generality that a1a2a3a4a5a_{1} \leq a_{2} \leq a_{3} \leq a_{4} \leq a_{5} and consider the five fractions a1a2,a3a4,a1a5,a2a3,a4a5\frac{a_{1}}{a_{2}}, \frac{a_{3}}{a_{4}}, \frac{a_{1}}{a_{5}}, \frac{a_{2}}{a_{3}}, \frac{a_{4}}{a_{5}}. By the pigeonhole principle, three distinct ones of these fractions lie in one of the intervals ]0,12]]0, \frac{1}{2}] resp. ]12,1]\left.] \frac{1}{2}, 1\right], where two of these are either directly consecutive in the listing or the first and the last fraction are among them. In any case, the positive difference of these two fractions is smaller than 12\frac{1}{2} and the four indices involved are pairwise distinct.

Now we show that C12C \geq \frac{1}{2} holds. For this we consider the example 1,2,2,2,r1, 2, 2, 2, r, where rr is meant to be a gigantic number. With these numbers one can form - ordered by size - the fractions 1r,2r,12,22,21,r2,r1\frac{1}{r}, \frac{2}{r}, \frac{1}{2}, \frac{2}{2}, \frac{2}{1}, \frac{r}{2}, \frac{r}{1}, where according to the problem statement 1r\frac{1}{r} and 2r\frac{2}{r} may not be chosen simultaneously. Therefore the smallest positive difference equals 122r\frac{1}{2}-\frac{2}{r}, and this approaches the value 12\frac{1}{2} from below arbitrarily closely as rr \rightarrow \infty. \square

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 translated into English from de; metadata (topic, difficulty) added by this project.