Consider an ordered set of n integers, {M(n,i), i=1 to n}.
combinatorics/sum.distinct.sets New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Consider an ordered set of n integers, {M(n,i), i=1 to n}.
Form the sums of the 2^n subsets. What is the smallest possible
largest element M(n,n), for each n, such that the sums are all
different?
Because powers of 2 as members of such sets produce unique sums, a
potential solution is M(n,n) = 2^(n-1). However, the set {3,5,6,7}
produces unique sums.
-- Jim Skrivan <skrivan@email.msn.com>
[ Editor: lightly reworded from the original posting. ]
Show solution
> This is an old problem, which might have come from Paul Erdos. Right. It is known that M(n) < 2^(n-2) for n large enough. It is conjectured, but not known, that M(n) > c*(2^n) for some positive c (probably c>1/8); there's probably a small Erdos prize for proving or disproving this. [What's the status of all these prizes now that Erdos is no longer?] It is easy to show that M(n) > (2^n)/n using a pigeonhole argument (not a carrier pigeonhole). In particular M(10) > 100. This problem appeared in a Martin Gardner article around 1980. In my Westinghouse paper I improved thus to M(9)>100 and showed by a different method that for all n the bound M(n) > (2n)! / ((n!)^2 * (2^n)) holds; by Stirling's approximation that bound is asymptotically (2^n) / sqrt(pi*n). This was published four years later in An improved lower bound on the greatest element of a sum-distinct set of fixed order, Jour. Comb. Theory A 41 (Jan. 1986), 89--94. That may still be the best published lower bound, though Andrew Gleason in 1985 removed the factor of pi and as far as I know didn't bother to publish. -- Noam D. Elkies <elkies@math.harvard.edu> (February 1998) A recent paper by Tom Bohman (MIT) "A construction for sets of integers with distinct subset sums" gives an upper bound of 0.22002 * 2^n for large n. This appeared in the Electronic J. of Combinatorics at http://www.combinatorics.org/Volume_5/Abstracts/v5i1r3.html -- Robin Chapman <rjc@maths.exeter.ac.uk>