Problem Statement
If $A\subseteq \{1,\ldots,N\}$ with $|A|=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$, then $N \gg 2^{n}$.
Categories:
Number Theory Additive Combinatorics
Progress
Historical Results
Erdos and Moser (1956) proved: $N \geq \left(\frac{1}{4}-o(1)\right)\frac{2^n}{\sqrt{n}}$
In 1985, Erdos offered $100 for any improvement of the constant $\frac{1}{4}$.
Current Best Bound
The current record $\sqrt{2/\pi}$ was first proved by Elkies and Gleason (unpublished). Dubroff, Fox, and Xu (2021) proved the exact bound: $N \geq \binom{n}{\lfloor n/2\rfloor}$
Related
- OEIS: A276661
- See also Problem #350
Source: erdosproblems.com/1 | Last verified: January 13, 2026