Competition problem — Combinatorics

Library / /30 of 189

Combinatorics Difficulty 5.1 AIME, harder Prove it Ukraine

Given $n \ge 4$ positive numbers. Consider all $\frac{n(n-1)}{2}$ pairwise sums of these numbers.
Show that there exist two sums that differ by no more than a factor of $\sqrt[4]{2}$ .

Solution

Let the numbers be arranged in non-increasing order: $x_1 \ge x_2 \ge \dots \ge x_n$ . Consider the sums $2x_1 \ge x_1 + x_2 \ge x_1 + x_3 \ge \dots \ge x_1 + x_n > x_1$ . Therefore, some two of the sums $x_1 + x_2, x_1 + x_3, \dots, x_1 + x_n$ differ by no more than a factor of $\sqrt[4]{2}$ .

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.