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.

Printable View

- Dec 1st 2009, 11:17 AMcomssaSets 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. - Dec 1st 2009, 11:33 AMBruno J.
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.