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
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 subsetof
, let
. Then
because
elements all less than or equal to
.
Now sincehas
subsets, and there are at most
values of
where
is any subset of
, then two of the values
must coincide.