Math Challenge: Prove that any set of 10 distinct integers ...?

Question

Prove that any set of 10 distinct integers between 1 and 100, has two subsets with the same sum.

Answer 1

If 1 ≤ a_{1} < a_{2} < . . < a_{10} ≤ 100 then the least possible sum is 0 (empty set), the greatest is
91 + 92 + . . + 100 = 5*191 < 1024
and the subsets are 2^10 = 1024 at all. When the values are less than that, according the well-known principle there should be at least 2 subsets with the same value.

Answer 2

I'm assuming you mean "has two *disjoint, nonempty* subsets with the same sum." Otherwise the problem is trivial, just take the two subsets to be the null set.

Duke has it right. To put it a little more explicitly, we can sort every possible subset into one of 956 "pigeonholes" labeled 0 through 955. Each subset goes into the pigeonhole corresponding to its sum. For instance, the empty set goes into pigeonhole 0, the subset {12,45,67} goes into pigeonhole 12+45+67=124. Next, notice that there are a total of 2^10=1024 subsets to put into pigeonholes. Since there are more subsets than pigeonholes, there must be at least one pigeonhole that gets more than one subset. Let A and B be two subsets from such a pigeonhole. If they are disjoint, we are done; they have the same sum. If they intersect, remove from each the integers they have in common. The remaining reduced A and B still have equal sums, so we are done.

Answer 3

The principle Duke mentioned is the Pigeon Hole Principle.