distinct positive real numbers with sum are given. Prove that there are at least -tuples among these numbers such that the sum of each -tuple is at least .
Solution
Let's place these numbers around a circle and label them by respectively and let
(Numbers are considered modulo .) We claim that at least of 's have a value not less than .
Assume the contrary which means at least of these 's have a value less than . Let the indices of these 's be . Note that, by the pigeonhole principle there are two indices such that
(Because there is a total of sets of the form of (mod ), and we have chosen indices, each one exists in a set.) So we can get
Which is a contradiction. Hence the claim.
Now there is a total of ways to place these numbers around the circle. Also according to the claim, in each permutation we have at least sums satisfying the condition. Each sum exists in permutations. So there's a total of at least
ways to choose an -tuple with sum greater or equal to .