lotus

previous page: 101 combinatorics/permutation.p
  
page up: Puzzles FAQ
  
next page: 103 combinatorics/transitions.p

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:













TOP
previous page: 101 combinatorics/permutation.p
  
page up: Puzzles FAQ
  
next page: 103 combinatorics/transitions.p