| |
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. 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.
Copyright © 1996-2009 Alexander Bogomolny
|
