Problem 1 — Visual explainer (undergrad)
========================================

Problem statement
---------------
If $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then\[N \gg 2^{n}.\]

Picture
-------
Pick A = {a1, a2, ..., an}
All subsets S ⊆ A  (there are 2^n)
Each subset gives a sum  sum(S)

      S            sum(S)
   --------        ------
    ∅               0
   {a1}            a1
   {a2}            a2
 {a1,a2}         a1+a2
      ...

Conjecture / Task: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: additive combinatorics / additive number theory.

Notation (if it appears above)
-----------------------------
- `\gg` / `>>` means "at least a constant times" (for large parameters).

Benchmarks / known results (from comments)
----------------------------------------
- The powers of $2$ show that $2^n$ would be best possible here.
- The trivial lower bound is $N \gg 2^{n}/n$, since all $2^n$ distinct subset
  sums must lie in $[0,Nn)$.
- Erd\H{o}s and Moser proved\[ N\geq
  (\tfrac{1}{4}-o(1))\frac{2^n}{\sqrt{n}}.\](In Erd\H{o}s offered \$100 for
  any improvement of the constant $1/4$ here.) A number of improvements of the
  constant have been given (see for a history), with the current record
  $\sqrt{2/\pi}$ first proved in unpublished work of Elkies and Gleason.
- Two proofs achieving this constant are provided by Dubroff, Fox, and Xu, who
  in fact prove the exact bound $N\geq \binom{n}{\lfloor n/2\rfloor}$.