Competition problem — Combinatorics

Library / /10 of 45

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.

Looking for a route rather than 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.