Library / Ukrainian National Mathematical Olympiad /51 of 201

Ukrainian National Mathematical Olympiad

Combinatorics Difficulty 5.3 AIME, harder Prove it Ukraine

Let $k$ and $n$ be arbitrary natural numbers that satisfy the condition $3 \le k \le n$ . Prove that among any $n$ pairwise distinct real numbers, there are either $k$ numbers with a positive sum or $(k-1)$ numbers with a negative sum.

Solution

If there are no positive numbers in the given set, then there is at most one number that is equal to zero, and all other numbers are negative. Therefore, there are $(n-1)$ negative numbers in the set. Hence, we can take any set with $k-1 \ge 2$ numbers as the desired subset.

Otherwise, if there is at least one positive number in this set, we separate this number. Among the other $(n-1)$ numbers that remain, we take any $k-1$ numbers. If their sum is negative, then the desired subset has been found and the problem is solved. If the sum is non-negative, we add to this subset with a non-negative sum the positive number that was separated. Then we obtain the desired $k$ numbers with a positive sum.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.