Largest subset of $\{1,\ldots,\lfloor cn\rfloor\}$ having no subset summing to $n$ (Erdős #361)
Statement
Fix $c>0$ and let $n$ be a large integer. Determine the maximum size of a set $A\subseteq\{1,2,\ldots,\lfloor cn\rfloor\}$ such that $n$ is not a subset sum of $A$ — that is, there is no $B\subseteq A$ with $\sum_{b\in B}b=n$. How large can $|A|$ be as a function of $c$ and $n$, and does this maximum depend on $n$ in an irregular way?
Acceptance. FULLY RESOLVES: determine the maximum $|A|$ as an (asymptotic) function of $c$ and $n$, with a construction achieving it and a matching upper-bound proof, and settle whether the maximum depends on $n$ in an irregular way. ADVANCES (each independently checkable): (a) prove matching-order upper and lower bounds for a specified range of $c$; or (b) compute, with reproducible code, the exact extremal size for all $n\leq N$ (a record bound) across a range of $c$, each optimum accompanied by a certificate that it is both achievable (an explicit $A$ with no subset summing to $n$) and maximal (no larger such $A$ exists), exposing the $c$- and $n$-dependence; or (c) prove or refute irregular dependence on $n$ for some fixed $c$. Deliver a proof, or code plus certified extremal values.
Background
Recorded by Erdős–Graham [ErGr80, p.59]; listed as open on erdosproblems.com/361 (fetched 2026-07-13, status 'open', tagged 'number theory'). The site lists no partial results, so the frontier is essentially the elementary bounds. Informally: for $c<1$ the ground set $\{1,\ldots,\lfloor cn\rfloor\}$ lies entirely below the target $n$, and the extremal question is how many elements one can retain while destroying every subset that sums to exactly $n$; as $c$ grows past $1$ one may also keep large elements exceeding $n$ (which can never be used in a subset summing to $n$) together with a controlled collection of smaller ones. The interest is the exact extremal size as a function of $c$ and $n$ and whether it fluctuates irregularly with the arithmetic of $n$. A machine-checkable Lean statement is maintained in DeepMind's formal-conjectures project. This is a subset-sum extremal cousin of the distinct-subset-sums problem Erdős #1 (erdosproblems.com/1). Erdős attached no prize; no OEIS entry is listed. The attacker's tool: exact computation of the extremal size for small $c$ and many $n$ — the constraint 'no subset sums to $n$' is a knapsack/subset-sum structure amenable to dynamic programming or ILP — to expose the $c$- and $n$-dependence and guide a matching construction and upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #361 (T. F. Bloom) | website |
| REF-02 | Lean 4 formalisation of Erdős #361 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.