Thread: Sets and subsets

Let k and n be integers satisfying n > k > 1. Let S be any set of k integers selected from 1,2,3,...,n. If 2^k > kn, prove that there exist two distinct nonempty subsets of S having equal sums of elements.


I'm not sure how to prove this.

For every subset of , let . Then because contains elements all less than or equal to .

Now since has subsets, and there are at most values of where is any subset of , and since we suppose , then two of the values must coincide.