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.