Given a set A ⊂ {1, 2, ..., 100} of ten integers. Prove that it is possible to select two disjoint non-empty subsets of A, S and T, whose members have the same sum.

Solution

Given a set A ⊂ {1, 2, ..., 100} of ten integers. Prove that it is possible to select two disjoint non-empty subsets of A, S and T, whose members have the same sum.

There are 210 = 1,024 subsets of the 10 integers, but there can be only 901 (= 955 - 55 + 1) possible sums, the number of integers between the minimum and maximum sums of ten distinct integers between 1 and 100. With more subsets than possible sums, there must exist at least one sum that corresponds to at least two subsets. Call two subsets with equal sums S' and T'.

Let C = S' ∩ T'; define S = S' - C, T = T' - C. Then S and T are disjoint, and

 sum(S) = sum(S' - C) = sum(S') - sum(C) = sum(T') - sum(C) = sum(T' - C) = sum(T).

At the req.puzzles archive site, where the problem and its solution came from, it is shown that 9 integers would suffice.

[an error occurred while processing this directive]