# 102 combinatorics/subsets.p

## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 102 combinatorics/subsets.p

Out of the set of integers 1,...,100 you are given ten different

integers. From this set, A, of ten integers you can always find two

disjoint non-empty subsets, S & T, such that the sum of elements in S

equals the sum of elements in T. Note: S union T need not be all ten

elements of A. Prove this.

combinatorics/subsets.s

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

Continue to: