There are 2^10 = 1,024 subsets of the 10 integers, but there can be only 901 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 A and B. Let C = A intersect B; define S = A - C, T = B - C. Then S is disjoint from T, and sum(S) = sum(A-C) = sum(A) - sum(C) = sum(B) - sum(C) = sum(B-C) = sum(T). QED

Addendum: 9 integers suffice. This was part of my Westinghouse project in 1981 (the above problem was in Martin Gardner's Scientific American column not long before). The argument is along the same lines, but a bit more complicated; for starters you only work with the subsets consisting of 3, 4, 5, or 6 of the 9 elements.

Let M(n) be the smallest integer such that there exists an n-element set {a1,a2,a3,...,an=M(n)} of positive integers all 2^n of whose subsums are distinct. The pigeonhole argument of subsets.s shows that M(n)>2^n/n, and it is known that M(n)>c*2^n/sqrt(n) for some c>0. It is still an unsolved problem (with an Erdos bounty) whether there is a positive constant c such that M(n)>c*2^n for all n.

--Noam D. Elkies (elkies@zariski.harvard.edu) Dept. of Mathematics, Harvard University

lib/config.php:156: Notice: Undefined variable: accept

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access