Let S be a set of ten distinct positive integers, all less than 107. Prove that S has two distinct subsets that both have the same sum.
So I've been racking my mind over this and I cannot figure out how to write a proper proof for it. I was thinking the pigeon hole principle might help out somehow, but I'm not entirely sure how. I'd be rather grateful to anyone who can help point me in the right direction.
Having said that, I don't know how to tackle this question! But if I have any thoughts, I'll post them!
Maximum sum = 106 + 105 + ... + 97 = ...
Minimum sum = 1 + 2 + ... + 10 = ...
No of different sums = ...
Can you supply the rest?
PS. Sorry, that's not quite right. The minimum sum is zero - if the subset is the empty set.
So if there are 1024 possible subsets of S and the maximum sum of S is 1015 then there are fewer possible sums than possible subsets. So, by the pigeonhole principle there must be two subsets of S that have the same sum? If that is true then if two subsets have the same sum but are not distinct (non-disjoint), they can be made distinct by removing the common elements between them and thus they would still have the same sum.
Is this right?