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 $\displaystyle A$ of $\displaystyle N=\{1,...,n\}$ , let $\displaystyle \mu(A)=\sum_{a \in A}a$. Then $\displaystyle 0 \leq\mu(A) \leq n\mid A \mid$ because $\displaystyle A$ contains $\displaystyle \mid A \mid$ elements all less than or equal to $\displaystyle n$.

Now since $\displaystyle S$ has $\displaystyle 2^k$ subsets, and there are at most $\displaystyle \mu(S) \leq kn$ values of $\displaystyle \mu (S')$ where $\displaystyle S'$ is any subset of $\displaystyle S$, and since we suppose $\displaystyle 2^k > kn$, then two of the values $\displaystyle \mu (S_1), \mu (S_2)$ must coincide.